Changing the direction of bi-directional iterator

A

AlesD

Hello,

could you please help me with following problem:

I have reversible container which holds (unsorted) instances of objects
with common base class. From time to time I need to search for last
occurance of instance meeting some criteria. When I find it I need to
move all folowing instances ("tail") into different cointainer (of same
type) while preserving their order.

I'm using find_if with container's reverse_iterators for the search, but
don't know how to preform the movement. If I use container constructor
with reverse_iterators the order of items in new container would be
reversed. This can be solved by reversing the container, but it might
take time if the tail has many items.

So my question is: "Is there any way how to do this (except own
implementation of course)?" Or more generally: "Is there any way how to
create normal (forward) iterator from reverse_iterator?"

Thanks in advance, Ales

----- ilustrative code -----

class base_t;

class container_t: list<base_t>

bool test(base_t& item);

container_t tail(container_t& c)
{
c::reverse_iterator found = find_if(c.rbegin(), c.rend(), test);
if (found == c.rend())
return container_t();
container_t result(c.rbegin(), found); // this is reversed tail
reverse(result.begin(), result.end()); // this takes time
return result;
}
 
L

Leor Zolman

Hello,

could you please help me with following problem:

I have reversible container which holds (unsorted) instances of objects
with common base class. From time to time I need to search for last
occurance of instance meeting some criteria. When I find it I need to
move all folowing instances ("tail") into different cointainer (of same
type) while preserving their order.

I'm using find_if with container's reverse_iterators for the search, but
don't know how to preform the movement. If I use container constructor
with reverse_iterators the order of items in new container would be
reversed. This can be solved by reversing the container, but it might
take time if the tail has many items.

So my question is: "Is there any way how to do this (except own
implementation of course)?" Or more generally: "Is there any way how to
create normal (forward) iterator from reverse_iterator?"

Yes, apply the base() member function to the reverse iterator. I've shown a
way you can apply it in your code below.
Thanks in advance, Ales

----- ilustrative code -----

class base_t;

class container_t: list<base_t>

bool test(base_t& item);

container_t tail(container_t& c)
{
c::reverse_iterator found = find_if(c.rbegin(), c.rend(), test);
if (found == c.rend())
return container_t();

Replace this:
container_t result(c.rbegin(), found); // this is reversed tail
reverse(result.begin(), result.end()); // this takes time

with:
container_t result;
copy(found.base(), c.end(), back_inserter(result));

This is assuming all the other issues in the code you've shown are
resolved; I'm going under the assumption you weren't interested in comments
on other issues and just wanted to see how to deal with the issue at hand.
HTH,
-leor
 
A

AlesD

Leor said:
(snip)



Yes, apply the base() member function to the reverse iterator. I've shown a
way you can apply it in your code below.

Replace this:


with:
container_t result;
copy(found.base(), c.end(), back_inserter(result));

This is assuming all the other issues in the code you've shown are
resolved; I'm going under the assumption you weren't interested in comments
on other issues and just wanted to see how to deal with the issue at hand.
HTH,
-leor

Thank you very much for your advice. I would just like to add what I
discovered later in case someone follows this thread:

----------
reverse_bidirectional_iterator must meat following requierements:

reverse_bidirectional_iterator(i).base() == i
&*ri == &*(--ri.base())
----------

Note the decrement in second reqirement! Although it seems strange that
ri and ri.base() does not point to same thing it has it's reason which
is reversing of ranges. If [rbegin(), rend()) is valid range then
[rend().base(), rbegin().base()) is also valid range.


Thanks again for your help
 
L

Leor Zolman

Leor Zolman wrote:
Thank you very much for your advice. I would just like to add what I
discovered later in case someone follows this thread:

----------
reverse_bidirectional_iterator must meat following requierements:

reverse_bidirectional_iterator(i).base() == i
&*ri == &*(--ri.base())
----------

Note the decrement in second reqirement! Although it seems strange that
ri and ri.base() does not point to same thing it has it's reason which
is reversing of ranges. If [rbegin(), rend()) is valid range then
[rend().base(), rbegin().base()) is also valid range.

Yes, it is a bit mind-bending when you start thinking about the
relationship of iterators to reverse_iterators. I didn't broach the subject
in my post because the only real pitfall, attempting to invoke base() upon
an "rend()" iterator, wasn't going to happen (you'd already special-cased
that scenario).

But as long as we're following up, I might also mention that my replacement
code above can combined with the return statement and further reduced to
one simple line:

return container_t(found.base(), c.end());

However, this does require a constructor (in this case, I used a template)
in the container_t class of the form:

template<typename iter>
container_t(iter beg, iter end) : list<base_t>(beg, end) {}

as well as support for member function templates (which you should have
with any compiler in modern use other than MSVC 6).
-leor
 
D

DaKoadMunky

the only real pitfall, attempting to invoke base() upon an "rend()" iterator

Could you please explain why that is a pitfall?

Given the following implementation from vector<T> on my system...

reverse_iterator rend()
{
return (reverse_iterator(begin()));
}

....it seems that retrieving the base iterator from the reverse_iterator would
not in and of itself be a pitfall.

Thanks
 
L

Leor Zolman

Could you please explain why that is a pitfall?

Given the following implementation from vector<T> on my system...

reverse_iterator rend()
{
return (reverse_iterator(begin()));
}

...it seems that retrieving the base iterator from the reverse_iterator would
not in and of itself be a pitfall.

I'm sorry, you're right. I was confusing the application of base() to a
reverse_iterator with the process of obtaining an iterator that points to
the same element as its corresponding reverse_iterator (by decrementing the
iterator). There's no iterator that corresponds to rend().
-leor
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
474,167
Messages
2,570,913
Members
47,455
Latest member
Delilah Code

Latest Threads

Top