Как std :: sort определяет основу сортировки? - PullRequest
Новая
       44

Как std :: sort определяет основу сортировки?

2 голосов
/ 19 января 2020

У меня есть следующий код 

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

int main () {
  pair<int, int> p[4];
  p[0] = pair<int, int>(5, 2); 
  p[1] = pair<int, int>(40, -2);
  p[2] = pair<int, int>(-3, 2); 
  p[3] = pair<int, int>(4, 45);

  auto print_pairii = [](pair<int, int> pp[]) {
    for (int i = 0; i < 4; i++) {
      cout << pp[i].first << " ";
    }   
    cout << endl;
  };  


  print_pairii(p);

  sort(p, p + 4); 

  print_pairii(p);
  return 0;
}

Первый print_pairii показывает 5 40 -3 4. После сортировки массива пары, print_pairii показывает -3 4 5 40, что означает, что сортировка была выполнена на основе первого элемента пары.

Почему это происходит вместо основания второго элемент? Как сортировка работает в этом смысле?

Ответы [ 3 ]

3 голосов
/ 19 января 2020

Поскольку при использовании std::sort без указания компаратора элементы сравниваются с использованием operator<.

1) Элементы сравниваются с использованием operator<.

И перегруженный operator< для std::pair сначала сравнивает 1-й элемент, а затем 2-й элемент, если 1-е элементы равны.

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

1 голос
/ 19 января 2020

Почему это происходит вместо основы второго элемента? Как работает сортировка в этом смысле?

Поскольку по умолчанию std::sort будет сортировать std::pair::first, тогда std::pair::second.

Если вы хотите отсортировать по второму элементу, вы должны предоставить пользовательский оператор сравнения. Что-то вроде: 

  sort(p, p + 4,
       [](const std::pair<int, int> &x, const std::pair<int, int> &y) {
           return x.second < y.second;
       });
0 голосов
/ 19 января 2020

Полезно разбить это на составляющие.

std::pair сравнивает лексикографически, как вы только что видели: https://en.cppreference.com/w/cpp/utility/pair. std::sort сравнивает (все типы), используя operator< по умолчанию: https://en.cppreference.com/w/cpp/algorithm/sort. Соедините их вместе, и вы отсортируете пары в порядке возрастания первых, а затем вторых элементов.

...