对成对向量进行排序时的奇怪行为

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's default comparison operator比较第一个和第二个元素。

strange behavior while sorting vector of pairs