排序pair类型向量时自定义Lambda引发的异常行为问题排查

嘿，我来帮你捋清楚为啥自定义lambda会提交失败——核心原因是你的比较函数只处理了first元素不同的情况，完全没管first相等时的排序逻辑，但CodeJam的测试用例里肯定存在first相同的元素，这就导致你的排序结果和题目预期的不一致啦！

咱们先回忆下C++里pair的默认排序规则：默认是字典序排序——

• 先比较两个pair的第一个元素，谁小谁排前面；
• 如果第一个元素相等，就比较第二个元素（这里你的第二个元素又是个pair<int,int>，那继续按字典序：先比这个子pair的第一个元素，再比第二个）。

而你的lambda函数[](auto a,auto b){ return a.first < b.first; }只做了第一步：当a.first < b.first时返回true，可当a.first == b.first时，不管两个元素的second部分有啥区别，这个lambda都会返回false。这就违反了C++ sort要求的严格弱序规则：对于任意两个元素x和y，必须明确x<y、y<x，或者两者等价（即既不x<y也不y<x）。但你的逻辑里，当x.first等于y.first时，comp(x,y)和comp(y,x)都返回false，sort会认为这两个元素是等价的，但实际上题目可能需要它们按second的字典序排列，这就导致你的输出和测试用例的预期结果不符，自然提交失败了。

怎么修正？ #

你只需要把lambda的逻辑补全，和默认排序的行为保持一致就行：

sort(v.begin(), v.end(), [](const auto& a, const auto& b) {
    // 先比first
    if (a.first != b.first) {
        return a.first < b.first;
    }
    // first相等时，比较第二个pair的first
    if (a.second.first != b.second.first) {
        return a.second.first < b.second.first;
    }
    // 最后比较第二个pair的second
    return a.second.second < b.second.second;
});

或者更简洁的写法，因为pair本身支持直接比较，所以可以直接写成和默认排序完全一样的逻辑：

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

另外提个小优化：把参数从auto a改成const auto& a，避免不必要的拷贝，虽然这不是导致提交失败的原因，但能让代码更高效~

内容的提问来源于stack exchange，提问作者dev35