stable_sort on a vector of pairs by first element in pair in increasing order without comparator function in C++

Question

#include <bits/stdc++.h> 
using namespace std; 

int main() 
{ 

    vector<pair<int,int>>v;
    v.push_back(make_pair(1,3));
    v.push_back(make_pair(1,1));
    v.push_back(make_pair(2,19));
    v.push_back(make_pair(2,4));

    int n = 4; 

    stable_sort(v.begin(),v.end()); 

    for (int i = 0; i < n; i++) 
        cout << "[" << v[i].first << ", " << v[i].second 
             << "] "; 

    return 0; 
}

Output : [1, 1] [1, 3] [2, 4] [2, 19] Expected Output : [1, 3] [1, 1] [2, 19] [2, 4]

Why does the vector of pairs not maintain the relative ordering even after applying stable sort, when we know that by default the vector of pairs is sorted on the basis of first element of the vector? If I write the comparator function, then it is working properly but not when I don't define any comparator function. Why is it so?

My guess: https://en.cppreference.com/w/cpp/utility/pair/operator_cmp — JVApen, May 03 '20 at 07:10
[Why should I not #include ?](https://stackoverflow.com/q/31816095/5910058) — Jesper Juhl, May 03 '20 at 07:12

Ted Lyngmo · Answer 1 · 2020-05-03T07:38:25.087

The comparator used uses both values in the pairs when doing the comparison.

It compares lhs and rhs lexicographically by operator< (operator<=> since C++20), that is, compares the first elements and only if they are equivalent, compares the second elements.

If I write the comparator function, then it is working properly

That's because you've probably implemented it like this:

[](const auto& lhs, const auto& rhs) {
    return lhs.first < rhs.first;
}

The default comparator does something equivalent to this:

[](const auto& lhs, const auto& rhs) {
    return lhs.first == rhs.first ? lhs.second < rhs.second : lhs.first < rhs.first;
}

score 2 · Accepted Answer · answered May 03 '20 at 07:27

The reference for operator< of std::pair<int, int> says that it

Compares lhs and rhs lexicographically by operator<, that is, compares the first elements and only if they are equivalent, compares the second elements.

So both elements are used to compare a std::pairand what you see is a fully sorted vector. Relative order of elements would only be relevant when two or more elements can be considered equal. Since both values of the pairs are used for comparison none of them can be considered equal. Thus relative order is not relevant here.

You can use a custom comparator to only compare the first element:

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

An will see the output

[1, 3] [1, 1] [2, 19] [2, 4]

Here the first two and last two pairs are considered equal and keep their relative order.

stable_sort on a vector of pairs by first element in pair in increasing order without comparator function in C++

2 Answers2