4

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

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() 版本。

4

6 回答 6

7

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

于 2013-01-18T19:31:23.873 回答
3

反向迭代器简单地在正常迭代器的相反方向上进行迭代。

因此，两个片段都会按升序对范围 [first, last] 内的所有内容进行排序。不同之处在于第一个它将使用 < 运算符进行比较，第二个是您给定的函数。

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

注意：相互比较相等的元素不能保证保持它们原来的相对顺序。

有用的参考资料：std::sort, std::vector::begin, std::vector::end, std::vector::rbegin, std::vector::rend

于 2013-01-18T19:17:22.373 回答
1

顾名思义，反向迭代器以相反的顺序访问集合。如果您要求 STLsort()算法对 from a.begin()to的范围进行排序a.end()，它会将结果值按照这些迭代器定义的顺序放置在...范围 from a.begin()to中。a.end()

那么如果你要求它对范围从a.rbegin()to进行排序会发生什么a.rend()？它将结果按照这些迭代器定义的顺序放在...范围 from a.rbegin()to中。a.rend()

于 2013-01-18T19:07:00.750 回答
1

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

于 2013-01-18T19:08:24.853 回答
0

rbegin为您提供一个指向列表末尾的迭代器，并在您要求它向前移动时向后移动。同样， rend为您提供列表开头的迭代器。

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

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

于 2013-01-18T19:07:04.727 回答
0

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

于 2013-01-18T19:07:31.603 回答