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.

Woodhouse

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

Unciform

I saw this in the docs earlier but gave up on it when I couldn't get anything with reverse_iterator<IteratorType> to compile. The problem: I forgot to add std:: (doh!) Thanks for the answer! – Woodhouse

The important note is indeed important. riter will physically point to the element after last (in a forward iterating sense). However, somewhat counterintuitively, *riter does point to the same element as last. – Svelte

When you assign riter and rend, you use reverse_iterator. What is this? Is it std::reverse_iterator? The latter is a class, and you have to provide a template parameter, so the code is invalid as is. Or is it a function defined by you? – Oloroso

It's a typo. Fixed now! – Unciform

I'm assuming that you meant the parameter first to be begin? – Logic

Answer 2

Since C++14, we have access to std::make_reverse_iterator, which will convert the (bidirectional) iterator it receives as a parameter to a std::reverse_iterator. Also note that as rlbond explains in their answer, the newly created std::reverse_iterator will point to the preceding element of the range. Here's a link to the cppreference page.

Example usage & comparison with manual creation is demonstrated below:

std::vector<int> a = {1, 2, 3, 4, 5, 6};

auto two_pos = std::begin(a)+1;
auto five_pos = std::end(a)-2;
std::for_each(two_pos, five_pos, [](int x) { std::cout << x << ','; });

std::cout << '\n';

auto reverse_two_pos = std::make_reverse_iterator(two_pos);
auto automatic_reverse_five_pos = std::make_reverse_iterator(five_pos);
std::reverse_iterator<decltype(five_pos)> manual_reverse_five_pos(five_pos);

std::for_each(automatic_reverse_five_pos, reverse_two_pos, [](int x) { std::cout << x << ','; });
std::cout << '\n';
std::for_each(manual_reverse_five_pos, reverse_two_pos, [](int x) { std::cout << x << ','; });

Output:

2,3,4,
4,3,2,
4,3,2,

Cheeseparing

Answer 3

Check out the base() method of reverse_iterator.

Lacombe

That gets you the forward iterator (the reverse of what this question is asking) – Svelte