迭代器和反向迭代器的区别

Question

下面两个代码片段有什么区别

vector<int> a;
// initialization code
sort( a.rbegin(), a.rend() );

和

vector<int> a;
// same initialization as above
sort(a.begin(), a.end(), comp);

其中comp是下面给定的布尔函数

bool comp( int i, int j)
{
    return i>j;
}

为了说明，下面的代码给出了WA，而这段代码给出了SPOJ问题XMAX的AC。AC和WA之间的唯一区别是使用sort()的版本。

Answer 1

两个函数调用NOT给出相同的答案，因为std::sort是不是一个稳定的算法，即它不保持相同元素的相对顺序。下面是std::pair<int, int>的元素按第一个元素排序的例子。使用反向比较函数进行排序和反向排序不会产生相同的序列。用std::stable_sort做同样的事情会得到相同的结果。

#include <algorithm>
#include <iostream>
#include <ios>
#include <vector>
int main()
{
    typedef std::pair<int, int> Element;
    std::vector<Element> v;
    v.push_back( Element(1,1) );
    v.push_back( Element(-1,1) );
    v.push_back( Element(1,2) );
    v.push_back( Element(-1,2) );
    v.push_back( Element(1,3) );
    v.push_back( Element(-1,3) );
    v.push_back( Element(1,4) );
    v.push_back( Element(-1,4) );
    v.push_back( Element(1,5) );
    v.push_back( Element(-1,5) );
    v.push_back( Element(1,6) );
    v.push_back( Element(-1,6) );
    v.push_back( Element(1,16) );
    v.push_back( Element(-1,16) );
    v.push_back( Element(1,22) );
    v.push_back( Element(-1,22) );
    v.push_back( Element(1,33) );
    v.push_back( Element(-1,33) );
    v.push_back( Element(1,44) );
    v.push_back( Element(-1,44) );
    v.push_back( Element(1,55) );
    v.push_back( Element(-1,55) );
    v.push_back( Element(1,66) );
    v.push_back( Element(-1,66) );
    for (auto it = v.begin(); it != v.end(); ++it) {
        std::cout << "(" << it->first << "," << it->second << ")" << " ";
    }
    std::cout << "n";
    auto w1 = v;
    std::sort(w1.begin(), w1.end(), [](Element const& e1, Element const& e2){ 
       return e1.first < e2. first;
    });
    auto w2 = v;
    std::sort(w2.rbegin(), w2.rend(), [](Element const& e1, Element const& e2) {
       return e1.first > e2.first;
    });
    std::cout << std::boolalpha << std::equal(w1.begin(), w1.end(), w2.begin()) << "n";
    auto w3 = v;
    std::stable_sort(w3.begin(), w3.end(), [](Element const& e1, Element const& e2){ 
       return e1.first < e2. first;
    });
    auto w4 = v;
    std::stable_sort(w4.rbegin(), w4.rend(), [](Element const& e1, Element const& e2) {
       return e1.first > e2.first;
    });
    std::cout << std::boolalpha << std::equal(w3.begin(), w3.end(), w4.begin()) << "n";
}

LiveWorkSpace的输出

Answer 2

反向迭代器与普通迭代器的迭代方向相反。

因此，这两个代码段都将对[first, last]范围内的所有内容按升序排序。不同之处在于，第一个函数将使用<操作符用于比较，并在第二个给定的函数。>

详细地说，第一个实际上是按非升序排序的，但由于您也反转了比较，因此它再次被反转，这抵消了效果。

注意:不能保证相互相等的元素保持原来的相对顺序。

参考文献:std::sort, std::vector::begin, std::vector::end，std::vector::rbegin,std::vector::rend

Answer 3

顾名思义，反向迭代器以相反的顺序访问集合。如果您要求STL sort()算法对从a.begin()到a.end()的范围进行排序，它将结果值放在…从a.begin()到a.end()的范围，顺序由这些迭代器定义。

那么如果你要求它对从a.rbegin()到a.rend()的范围进行排序会发生什么呢?它把结果放在……按迭代器定义的顺序，从a.rbegin()到a.rend()。

Answer 4

迭代器从第一个到最后一个，反向迭代器从最后一个到第一个。因此，sort(a.begin(), a.end())将[first, last]范围内的元素按顺序排列;sort(a.rbegin(), a.rend())将[last, first)范围内的元素按顺序排列，产生与第一个版本相反的顺序。

Answer 5

rbegin为您提供了一个指向列表末尾的迭代器，当您要求它向前移动时，它将向后移动。类似地，rend为您提供了一个指向列表开头的迭代器。

sort(a.begin(), a.end(), comp);

这里的第三个参数用于定义您自己的排序顺序。如果没有指定，则使用该对象的默认值

Answer 6

它们完成相同的事情。在第一个版本中，您颠倒了迭代器的顺序以获得从高到低排序。在第二个版本中，您颠倒了比较的意义，也获得了从高到低的排序。