stable_sort для вектора пар по первому элементу в паре в порядке возрастания без функции компаратора в C ++ - PullRequest
Новая
       103

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

2 голосов
/ 03 мая 2020 
#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]

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

Ответы [ 2 ]

4 голосов
/ 03 мая 2020

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

Он сравнивает lhs и rhs лексикографически на 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;
}
2 голосов
/ 03 мая 2020

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

Сравнивает lhs и rhs лексикографически оператором <, то есть сравнивает первые элементы и только если они эквивалентны, сравнивают вторые элементы. </p>

Таким образом, оба элемента используются для сравнения 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]

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

...