以下两个代码片段有什么区别。
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 函数
bool comp( int i, int j)
{
return i>j;
}
为了说明,下面的代码给出了WA而此代码给出 AC对于 SPOJ 问题 XMAX . AC之间的唯一区别和 WA是使用的 sort() 的版本。
最佳答案
这两个函数调用不给出相同的答案,因为 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 上输出
关于c++ - 迭代器和反向迭代器的区别,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14405794/