39

It seems that I can sort a std::vector<std::pair<int, std::string>>, and it will sort based on the int value. Is this a well defined thing to do?

Does std::pair have a default ordering based on its elements?

melpomene
  • 84,125
  • 8
  • 85
  • 148
Meh
  • 7,016
  • 10
  • 53
  • 76

4 Answers4

60

std::pair uses lexicographic comparison: It will compare based on the first element. If the values of the first elements are equal, it will then compare based on the second element.

The definition in the C++03 standard (section 20.2.2) is:

template <class T1, class T2>
bool operator<(const pair<T1, T2>& x, const pair<T1, T2>& y);

Returns: x.first < y.first || (!(y.first < x.first) && x.second < y.second).
interjay
  • 107,303
  • 21
  • 270
  • 254
  • 1
    Why they don't use a simpler (y.first >= x.first) instead of less + negation ? – Patrick Roncagliolo Apr 14 '20 at 15:21
  • 1
    @PatrickRoncagliolo This way only requires user-defined types to implement `operator<` to support ordering. Otherwise they'd need to support more ordering operators, and ensure the relations between them (e.g. `>=` is the negation of `<`). – interjay Apr 15 '20 at 17:22
  • So it is not an optimization trick of some sort related to the efficiency of < vs <=. Good to know. Thank you. – Patrick Roncagliolo Apr 16 '20 at 10:46
10

According to my copy of the C++0x standard, section 20.3.3.26, std::pair has an operator< defined such that for two pairs x and y, it returns

x.first < y.first || (!(y.first < x.first) && x.second < y.second)

I'm not certain if this is part of the 2003 standard as well. I should also note that this won't compile if the elements themselves are not LessThanComparable.

Michael Kristofik
  • 34,290
  • 15
  • 75
  • 125
2

Documentation from SGI

The comparison operator. It uses lexicographic comparison: the return value is true if the first element of x is less than the first element of y, and false if the first element of y is less than the first element of x. If neither of these is the case, then operator< returns the result of comparing the second elements of x and y. This operator may only be used if both T1 and T2 are LessThanComparable. This is a global function, not a member function.

Looks like it's actually a combination of both elements.

Chris H
  • 6,433
  • 5
  • 33
  • 51
2

Yes. operator<() is defined for std::pair<T1, T2>, assuming that both T1 and T2 are themselves comparable.

Dima
  • 38,860
  • 14
  • 75
  • 115