стабильная_сортировка вектора пар по первому элементу в паре в порядке возрастания без функции сравнения в C++

#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]

Почему вектор пар не поддерживает относительный порядок даже после применения стабильной сортировки, когда мы знаем, что по умолчанию вектор пар сортируется на основе первого элемента вектора? Если я пишу функцию сравнения, то она работает правильно, но не тогда, когда я не определяю функцию сравнения. Почему это так?


c++ vector stable-sort comparator std-pair
person Community    schedule 03.05.2020    source источник
comment
Мое предположение: en.cppreference.com/w/cpp/utility/pair/operator_cmp   -  person JVApen    schedule 03.05.2020
comment
Почему я не должен #include ‹bits/stdc++.h›?   -  person Jesper Juhl    schedule 03.05.2020

Ответы (2)


arrow_upward
2
arrow_downward

ссылка для operator< из std::pair<int, int> говорит, что это

Сравнивает левый и правый элементы лексикографически с помощью оператора‹, то есть сравнивает первые элементы и, только если они эквивалентны, сравнивает вторые элементы.

Таким образом, оба элемента используются для сравнения std::pair, и вы видите полностью отсортированный вектор. Относительный порядок элементов будет иметь значение только тогда, когда два или более элемента можно считать равными. Поскольку для сравнения используются оба значения пар, ни одно из них нельзя считать равным. Таким образом, относительный порядок здесь не имеет значения.

Вы можете использовать собственный компаратор для сравнения только первого элемента:

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]

Здесь первые две и последние две пары считаются равными и сохраняют свой относительный порядок.

person churill    schedule 03.05.2020

arrow_upward
4
arrow_downward

Используемый компаратор использует оба значения в парах при сравнении.

Он сравнивает левое и правое положение лексикографически по operator< (operator<=> начиная с C++20), то есть сравнивает первые элементы и, только если они эквивалентны, сравнивает вторые элементы.

Если я пишу функцию сравнения, то она работает правильно

Это потому, что вы, вероятно, реализовали это так:

[](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;
}
person Ted Lyngmo    schedule 03.05.2020