stable_sort 在 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; 
}

输出：[1, 1] [1, 3] [2, 4] [2, 19] 预期输出：[1, 3] [1, 1] [2, 19] [2, 4]

当我们知道默认情况下对向量是根据向量的第一个元素排序时，为什么即使在应用稳定排序后对向量仍不保持相对顺序？如果我编写比较器函数，那么它可以正常工作，但当我没有定义任何比较器函数时，它就不能正常工作。为什么会这样？

Answer 1

使用的比较器在进行比较时成对使用两个值。

它按字典顺序比较 lhs 和 rhs operator<（自 C++20 起 operator<=>），即比较第一个元素，只有当它们相等时，才比较第二个元素。

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

那是因为你可能是这样实现的：

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

默认比较器的作用与此等效：

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

Answer 2

std::pair<int, int> 的 operator< 的 reference 说

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

因此，这两个元素都用于比较一个 std::pair，您看到的是一个完全排序的向量。元素的相对顺序仅在两个或多个元素可以被视为相等时才相关。由于这对的两个值都用于比较 none 可以认为它们是相等的。因此相对顺序在这里不相关。

您可以使用自定义比较器只比较第一个元素：

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

An 将看到输出

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

在这里，前两对和后两对被认为是相等的，并保持它们的相对顺序。

stable_sort 在 C++ 中没有比较器函数的情况下，按对中的第一个元素按升序排列的向量对

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

c++

vector

comparator

stable-sort

std-pair