从前向迭代器获取反向迭代器，而不知道值类型 [英] 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< 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
  }
}

重要说明：

注意，当迭代器
颠倒时，颠倒的版本不会指向
元素在
范围内，而是前面的一个。
这样，为了安排
一个范围的过去的元素：
指向范围内的过去的结束
元素的迭代器，当反向时，
改变为指向范围的最后一个元素
（不是通过它）（如果
反转，则这将是范围的第一个元素）。如果一个范围中的
第一个元素的迭代器被颠倒，则
反向迭代器指向第一个元素之前的
元素（这个
将是过去的，
的结束元素，如果相反，则为范围）。

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

这篇关于从前向迭代器获取反向迭代器，而不知道值类型的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！