Iterators and reverse iterators

[Marcin Kaliciñski]

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.

 

[Kai-Uwe Bux]

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:stream & 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