Сортировка вектора с 2 парами внутри

Question

Ну, у меня есть вектор, пара>, и мне интересно, как он делает сортировку? с сортировкой (v.begin (), v.end ());

using namespace std;

int main(){
   int n; cin >> n;
   vector<pair<pair<int,int>, pair<int,int>>> v;
   for(int i=0;i<n;i++){
      long long x1,y1,x2,y2;
      cin>>x1>>y1>>x2>>y2;
      v.push_back(make_pair(make_pair(x1,y1),make_pair(x2,y2)));
   }   
   sort(v.begin(),v.end());
   for(auto& p : v){
      cout<<p.first.first<<" "<<p.first.second<<" "<<p.second.first<<" "<<p.second.second<<"\n";
  }
   return 0;
}

ввод:

4   
5 19 8 17
5 15 15 5
0 20 20 0
8 10 10 8

Выход:

0 20 20 0
5 15 15 5
5 19 8 17
8 10 10 8

Answer 1

Для класса std::pair определен оператор

template<class T1, class T2>
constexpr bool operator< (const pair<T1, T2>&, const pair<T1, T2>&);

, который действует следующим образом

Возвращает: x.first

Так, например, для двух пар типа std::pair<std::pair<int, int>, std::pair<int, int>>

{ { 5, 19 }, { 8, 17 } }
  ^^^^^^^^^

и

{ { 5, 15 }, { 15, 5 } }
  ^^^^^^^^^

сначала пары { 5, 19 } и { 5, 15 } сравниваются с использованием одного и того же operator <.

Поскольку вторая пара меньше первой пары, чем втораяпара будет предшествовать первой паре в векторе результатов.

Если они (первые пары) были равны друг другу, как, например,

{ { 5, 15 }, { 8, 17 } }
  ^^^^^^^^^

и

{ { 5, 15 }, { 15, 5 } }
  ^^^^^^^^^

, тогдавторые пары сравнивались.Поскольку пара { 8, 17 } меньше { 15, 5 }, то первая пара меньше второй пары.

Пары { 8, 17 } и { 15, 5 } сравниваются по одному и тому же шаблону operator <.

Answer 2

std::pair определяет operator<, если содержащиеся типы поддерживают сравнение через operator<, а вы используете int, поэтому он предоставляется по умолчанию.

std::sort использует это operator< для сортировки элементов лексикографически .

Если вы использовали произвольный тип без определения operator<, вам необходимо указатьваш собственный компаратор к std::sort