Get a reverse iterator from a forward iterator without knowing the value type

Question

I'm trying to implement some STL-style sorting algorithms. The prototype for std::sort looks something like this (from cplusplus.com):

template <class RandomAccessIterator> void sort ( RandomAccessIterator first, RandomAccessIterator last ); 

The function is generally called like this (although the container type can vary):

std::vector<int> myVec; // Populate myVec std::sort(myVec.begin(), myVec.end()); 

I duplicated the prototype of std::sort for my own sorting function. To iterate through the container to be sorted, I do the following:

template <class RandomAccessIterator> void mySort(RandomAccessIterator first, RandomAccessIterator last) {     RandomAccessIterator iter;   for (iter = first; iter != last; ++iter) {     // Do stuff   } } 

Easy enough. But what if I want to use a reverse iterator? This would be convenient in algorithms that sort a container from both ends, e.g. cocktail sort.

Is there any way to get a reverse iterator from the iterators that are passed in as parameters? If I knew the container type in advance, I could do something like this:

template <class RandomAccessIterator> void mySort(RandomAccessIterator first, RandomAccessIterator last) {   std::vector<int>::reverse_iterator riter(last);   std::vector<int>::reverse_iterator rend(first);   for ( ; riter != rend; ++riter) {     // Do stuff   } }     

Unfortunately, I don't know the container type. What I really need to do is something like this:

template <class RandomAccessIterator> void mySort(RandomAccessIterator first, RandomAccessIterator last) {   RandomAccessIterator riter = reverse_iterator(last);   RandomAccessIterator rend = reverse_iterator(begin);   for ( ; riter != rend; ++riter) {     // Do stuff   } } 

Is there some way to do this without having to pass in reverse iterators as additional parameters (which would solve the problem, but make the function prototype less intuitive)?

Note that I need both forward and reverse iterators in my implementation, so calling the function this way

std::vector<int> myVec; // Populate myVec mySort(myVec.rbegin(), myVec.rend()); 

will not work.

Answer 1

The STL has std::reverse_iterator<Iterator>:

template <class RandomAccessIterator> void mySort(RandomAccessIterator first, RandomAccessIterator last)  {   typedef std::reverse_iterator<RandomAccessIterator> RIter;   RIter riter(last);   RIter rend(first);   for ( ; riter != rend; ++riter) {     // Do stuff   } } 

An important note:

Notice however that when an iterator is reversed, the reversed version does not point to the same element in the range, but to the one preceding it. This is so, in order to arrange for the past-the-end element of a range: An iterator pointing to a past-the-end element in a range, when reversed, is changed to point to the last element (not past it) of the range (this would be the first element of the range if reversed). And if an iterator to the first element in a range is reversed, the reversed iterator points to the element before the first element (this would be the past-the-end element of the range if reversed).