How does std :: sort work for a list of pairs?

Question

Why this :

#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; } } 

working as intended? output:

 1 2 2 5 6 

How does std::sort get a way to sort my int-string pairs? How to do this for my class as a first pair? Is there a way to sort by second using std::sort ?

Answer 1

Since operator< defined for std::pair , and it is based on std::pair::first and then std::pair::second (lexicographic), so your code works like a standard. To sort it by the second part of std::pair , you can try the following:

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

Answer 2

There is one “obvious” order of product types caused by the corresponding orderings of the components, and this is the lexicographic order :

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

This is the order used by operator< of std::pair . In your example, since all of the first components are different, the ordering is equal to the order of the first component. This becomes more interesting if you have multiple occurrences of the same value in the first component, in which the second component is used to break the links.

How to do this for my class as the first?

You just need to define operator< for your type. But keep in mind that the second component will be considered if necessary, and you may not need overhead.

Is there a way to sort by second using std::sort ?

Yes, just use a custom comparator functor . You can always do this if you do not want to use the default sort operator< for sorting.