在不知道值类型的情况下从前向迭代器获取反向迭代器

Get a reverse iterator from a forward iterator without knowing the value type(在不知道值类型的情况下从前向迭代器获取反向迭代器)

问题描述

我正在尝试实现一些 STL 风格的排序算法.std::sort 的原型看起来像这样(来自 cplusplus.com):

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());

我为自己的排序功能复制了 std::sort 的原型.要遍历要排序的容器，我执行以下操作:

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());

不会工作.

推荐答案

STL有std::reverse_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
  }
}