std::sort如何对pair列表进行排序？

Question

为什么这个链接和it技术有关？

#include <iostream>
#include <string>
#include <vector>                                                             
#include <algorithm>

using namespace std;

vector<pair<int, string>> list;

int main() {
    int one = 1, two = 2, three =3, five =5, six = 6;
    string bla = "bla";

    list.push_back( pair<int, string>(two, bla));
    list.push_back( pair<int, string>(one, bla));
    list.push_back( pair<int, string>(two, bla));
    list.push_back( pair<int, string>(six, bla));
    list.push_back( pair<int, string>(five, bla));

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

    for(auto item : list) {
        cout << item.first << endl;
    }
}

正常工作了吗？输出结果是：

1
2
2
5
6

std::sort是如何对我的int-string对进行排序的？如何使其对我的类作为一对first进行排序？是否有一种方法可以使用std::sort按second进行排序？

- DuckQueen

---

std::pair有一个operator<。如果你想让std::sort排序方式不同，给它一个比较器。 - chris

http://en.cppreference.com/w/cpp/utility/pair/operator_cmp - bolov

你可以为bool operator<int, string><(const& std::pair<int, string> op1,const& std::pair<int, string> op2)函数提供一种专门化，并将其传递给排序。 - πάντα ῥεῖ

请查看此SO帖子的被接受答案 - https://dev59.com/SHE85IYBdhLWcg3wXCIv - R Sahu

@MarkRansom 他有一个名为list的vector。由于需要RandomAccessIterators，因此std::sort无法与std::list一起使用。 - Praetorian

@Praetorian 我以为std::sort使用双向迭代器的降序状态下也能工作。我一定想到了其他的东西，可能是lower_bound。 - Mark Ransom

Answer 1

由于operator<已经为std::pair定义，并且它是基于std::pair::first和std::pair::second（按字典顺序）排序的，因此您的代码按照标准工作。要根据std::pair的第二部分进行排序，可以尝试使用以下方法：

std::sort(list.begin(), list.end(), [](const std::pair<int, string> &x,
                                       const std::pair<int, string> &y)
{
    return x.second < y.second;
});

- masoud

Answer 2

各组件的排序导致了一种“明显”的产品类型排序，即词典排序：

(a, b) < (c, d)  <=>  a < c || (a == c && b < d)

这是std::pair的operator<使用的排序方式。在您的示例中，由于所有第一个组件都不同，因此排序恰好等于第一个组件的排序。如果第一个组件中有多个相同值，则使用第二个组件来打破平局会更有趣。

您只需要为您的类型定义operator<即可实现。但请记住，如有必要，第二个组件将被考虑在内，您可能不希望增加这种开销。

是的，只需使用自定义比较器函数即可按second排序。如果您不想使用默认的operator<进行排序，您总是可以这样做。

- Niklas B.