сортировка контейнера STL с парой пар

Question

Я впервые использую C ++ STL priority_queue(), и я немного озадачен этим конкретным фрагментом кода, с которым я столкнулся (но я считаю, что это не имеет ничего общего с pq, и это должно быть применимо ко всем контейнерам (вектор, наборы и т. д.)):

priority_queue<pair<int, pair<int, int> >,
            vector<pair<int, pair<int, int> > >,
            greater<pair<int, pair<int, int> > > > pq;

Допустим, у меня есть pq.push_back(make_pair(a,make_pair(b,c))).В случае столкновения a правило сравнения будет распространяться на вторую пару, а сортировка будет выполняться на основе b, а затем c?

Answer 1

Вопрос в основном сводится к следующему: как сортируются std::pair, то есть каков результат a > b для двух пар (обратите внимание, что std::greater просто вызывает operator>).

С cppreference на std::pair::operator>:

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

И это естественно распространяется на вложенные пары. Следовательно ...

Допустим, у меня есть pq.push_back (make_pair (a, make_pair (b, c))). В случае есть столкновение, тогда правило сравнения будет распространяться на вторая пара и сортировка будет производиться на основе b, а затем c?

Да. Если два элемента имеют равные a, тогда будет сравниваться second самой внешней пары (то есть (b,c)).

Answer 2

В случае столкновения a, тогда правило сравнения распространяется на вторую пару, и сортировка будет выполняться на основе b, а затем c?

Точно. std::greater по умолчанию operator >, что, в случае std::pair, осуществляет лексикографическое сравнение - то есть сравнивает первое и, если первое совпадает, сравнивает второе.

Answer 3

Вы правы: пары пар отсортированы в лексикографическом порядке по (a, b, c). Взгляните на std :: большее , которое на самом деле вызывает std :: pair :: operator> .

Answer 4

Класс priority_queue нуждается в методе сравнения. По умолчанию будет использоваться std::less, но вы можете переопределить его.

Использование std::pair подразумевает использование сравнения по умолчанию, используемого std :: pair: http://www.cplusplus.com/reference/utility/pair/operators/

Я думаю, что это должно ответить на ваш вопрос.