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

2022-01-10 00:00:00 sorting iterator c++

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

重要提示:

但请注意，当迭代器是颠倒的，颠倒的版本确实不指向同一个元素范围，但到它前面的那个.就是这样，为了安排范围的结束元素:一个指向过去的迭代器范围内的元素，当反转时，是改为指向最后一个元素(不超过它)的范围(这将成为范围的第一个元素 if反转).如果一个迭代器范围内的第一个元素被反转，反向迭代器指向第一个元素之前的元素(这个将是过去的结束元素范围(如果反转).

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

相关文章