对向量排序中的奇异行为

Question

我正在使用非负整数填充以下向量以解决代码阻塞问题：

vector<pair<int,pair<int,int> > > v;

以下排序方式导致提交失败：

sort(v.begin(),v.end(),[](auto a,auto b){
    return a.first < b.first;
});

但如果我只是按以下方式更改排序：

sort(v.begin(),v.end());

提交通过。

我用来排序的lamda函数有什么问题？

谢谢

Answer 1

lambda只考虑第一个元素，但显然一对元素由两个元素组成。对于您的lambda对，具有相同的第一个元素但不同的第二个元素将被认为是相等的。因此它们在排序后的相对顺序是未指定的。

如果要按以下方式对数据进行排序：

{1, {1, 1}},
{0, {2, 2}},
{1, {3, 3}},

则第一项和最后一项被视为相等,排序可以产生

{0, {2, 2}},
{1, {1, 1}},
{1, {3, 3}},

或

{0, {2, 2}},
{1, {3, 3}},
{1, {1, 1}},

但是std::pair的默认比较运算符比较第一个和第二个元素。