Получите обратный итератор с итератора вперед, не зная тип значения

Я пытаюсь реализовать некоторые алгоритмы сортировки в стиле STL. Прототип для std::sort выглядит примерно так (от cplusplus.com):

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

Функция обычно называется так (хотя тип контейнера может меняться):

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

Я продублировал прототип std::sort для моей собственной функции сортировки. Чтобы итерировать контейнер, подлежащий сортировке, я делаю следующее:

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

Прост достаточно. Но что, если я хочу использовать обратный итератор? Это было бы удобно в алгоритмах, сортирующих контейнер с обоих концов, например. сортировка коктейлей.

Есть ли способ получить обратный итератор из итераторов, которые передаются как параметры? Если я заранее знал тип контейнера, я мог бы сделать что-то вроде этого:

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

К сожалению, я не знаю тип контейнера. Мне действительно нужно сделать что-то вроде этого:

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

Есть ли способ сделать это без необходимости передавать обратные итераторы в качестве дополнительных параметров (что бы решить проблему, но сделать прототип функции менее интуитивным)?

Обратите внимание, что мне нужны как итераторы, так и обратные итераторы в моей реализации, поэтому вызов функции таким образом

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

не будет работать.

Ответ 1

У STL есть 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
  }
}

важное примечание:

Обратите внимание, что когда итератор обратная, обратная версия не указывать на один и тот же элемент в но до того, что предшествует ему. Это так, чтобы организовать конечный элемент диапазона: Итератор, указывающий на прошлое элемент в диапазоне, при обратном, является изменено, чтобы указать на последний элемент (а не мимо него) диапазона (это быть первым элементом диапазона, если в обратном порядке). И если итератор первый элемент в диапазоне меняется на противоположный, обратный итератор указывает на элемент перед первым элементом (это будет элементом конца прошлого диапазон, если обратный).

Ответ 2

Проверьте метод base() обратного_тератора.