Iterator和反向迭代器之间的区别

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

这两个函数调用不会给出相同的答案,因为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上的输出