从前向迭代器获取反向迭代器而不知道值类型

Question

我正在尝试实现一些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());

不管用.

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

一个重要的说明:

但是请注意,当反转迭代器时,反转版本不会指向范围内的相同元素,而是指向它之前的元素.这样,为了安排范围的过去元素:指向范围中的过去元素的迭代器,当被反转时,被更改为指向最后一个元素(不是通过它) )范围(如果反转,这将是范围的第一个元素).如果一个范围中第一个元素的迭代器被反转,则反转的迭代器指向第一个元素之前的元素(如果反转,这将是范围的过去元素).