Changing the direction of bi-directional iterator

[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;
}

[Leor Zolman]

On Sun, 02 May 2004 02:06:53 +0200, AlesD <al****@seznam.cz> wrote:

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
return result;
}

--
Leor Zolman --- BD Software --- www.bdsoft.com
On-Site Training in C/C++, Java, Perl and Unix
C++ users: download BD Software's free STL Error Message Decryptor at:
www.bdsoft.com/tools/stlfilt.html

[AlesD]

Leor Zolman wrote:

On Sun, 02 May 2004 02:06:53 +0200, AlesD <al****@seznam.cz> wrote:

Hello,
(snip)
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.

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

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

[Leor Zolman]

On Sun, 02 May 2004 22:45:49 +0200, AlesD <al****@seznam.cz> wrote:

Leor Zolman wrote:

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));

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


Thanks again for your help

--
Leor Zolman --- BD Software --- www.bdsoft.com
On-Site Training in C/C++, Java, Perl and Unix
C++ users: download BD Software's free STL Error Message Decryptor at:
www.bdsoft.com/tools/stlfilt.html

[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

[Leor Zolman]

On 02 May 2004 23:34:47 GMT, da*********@aol.com (DaKoadMunky) wrote:

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.

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

Thanks

--
Leor Zolman --- BD Software --- www.bdsoft.com
On-Site Training in C/C++, Java, Perl and Unix
C++ users: download BD Software's free STL Error Message Decryptor at:
www.bdsoft.com/tools/stlfilt.html