Iterators and reverse iterators
 

template<class RanAccIt>
void some_algorithm(RanAccIt begin, RanAccIt end)
{
// this algorithm involves calling std::lexicographical_compare
// on range [begin, end), and on reverse of this range
// (i.e. as rbegin, rend was passed)
}

How can I call lexicographical_compare inside the function so that it
traverses the range backwards?

The ideal would be to somehow make reverse iterators from normal iterators,
but I can't see a way to do it (even though the iterators are random access,
so backwards iteration is fully supported).

The only way I see is to pass reverse iterators to the function in addition
to normal iterators. I don't want to do that, because:
(1) it is redundant - begin/end define the range perfectly
(2) it reveals internals of the algorithm to the outside - one day I will
come with an implementation that does not need reverse iterators, and I will
have to change function signature

Is there other way?

Also, if I wanted to hand-code a loop over reverse of range [begin, end),
would the below be conforming:

template<class RanAccIt>
void some_algorithm(RanAccIt begin, RanAccIt end)
{
RanAccIt rbegin = end - 1;
RanAccIt rend = begin - 1;
for (RanAccIt it = rbegin; it != rend; --it)
{
/* ... */
}
}

cheers,
M.

Re: Iterators and reverse iterators
 

Marcin Kaliciñski wrote:

> template<class RanAccIt>
> void some_algorithm(RanAccIt begin, RanAccIt end)
> {
> // this algorithm involves calling std::lexicographical_compare
> // on range [begin, end), and on reverse of this range
> // (i.e. as rbegin, rend was passed)
> }
>
> How can I call lexicographical_compare inside the function so that it
> traverses the range backwards?
>
> The ideal would be to somehow make reverse iterators from normal
> iterators, but I can't see a way to do it (even though the iterators are
> random access, so backwards iteration is fully supported).
>
> The only way I see is to pass reverse iterators to the function in
> addition to normal iterators. I don't want to do that, because:
> (1) it is redundant - begin/end define the range perfectly
> (2) it reveals internals of the algorithm to the outside - one day I will
> come with an implementation that does not need reverse iterators, and I
> will have to change function signature
>
> Is there other way?

You want to have a look at std::reverse_iterator:


#include <iterator>
#include <iostream>

template <typename RndAccIt>
void print_reversed_range ( std::ostream & out,
RndAccIt const & from,
RndAccIt const & to ) {
for ( std::reverse_iterator< RndAccIt > iter ( to );
iter != std::reverse_iterator< RndAccIt >( from );
++ iter ) {
out << *iter << ' ';
}
}

#include <vector>

int main ( void ) {
std::vector< int > i_vect;
for ( int i = 0; i < 10; ++i ) {
i_vect.push_back( i );
}
print_reversed_range( std::cout, i_vect.begin(), i_vect.end() );
}


> Also, if I wanted to hand-code a loop over reverse of range [begin, end),
> would the below be conforming:
>
> template<class RanAccIt>
> void some_algorithm(RanAccIt begin, RanAccIt end)
> {
> RanAccIt rbegin = end - 1;
> RanAccIt rend = begin - 1;

Ouch, the before-begin position is in general not a valid thing.

> for (RanAccIt it = rbegin; it != rend; --it)
> {
> /* ... */
> }
> }
>
> cheers,
> M.


Best

Kai-Uwe Bux