Почему для очереди приоритета требуется front(), pop_back() из базового контейнера вместо back(), pop_back()?
Из C++ Primer, а также https://en.cppreference.com/w/cpp/container/priority_queue, я знаю:
Priority_queue требует произвольного доступа в дополнение к фронту, push_back и pop_back;
Я также прочитал это сообщение в блоге от Google и знаю:
- push: добавьте новый элемент в очередь,
- pop: удалить самый большой элемент очереди,
- top: доступ к самому большому элементу очереди.
push должен быть реализован push_back, без проблем. И pop и top похоже, работают на одном элементе. Один из них - доступ к нему, другой - его удаление. Поэтому я думаю, что эти две операции должны быть реализованы с помощью pop_front() и front() или pop_back() и back().
Поэтому я смущен, почему требования front() и pop_back()?
Пусть, например, предположим, что основной контейнер представляет собой vector а некоторые элементы int позволяют сказать 1,2,3,4,5,6. Как интерфейс адаптера " pop(), top() " работает с базовыми " front(), pop_back() "?
Ответы
Ответ 1
Хотя pop() на priority_queue в конечном счете удаляет верхний элемент, он должен поддерживать инвариант, которого не было бы, если бы все элементы просто переместились. Таким образом, он работает, заменяя верхнее значение с front() на back() и pop_back() и затем заменяя смещенное значение одним из своих дочерних элементов до восстановления инварианта.
Аналогично, push() вызывает push_back() а затем выполняет серию свопов, хотя и в другом направлении.
Примечание: поскольку C++ использует максимальную кучу (в отличие от обычного соглашения), инвариант состоит в том, что любой элемент должен быть больше, чем оба его дочерних элемента (если они существуют). Поскольку большинство полезных проблем связаны с мини-кучей, вы почти всегда должны указывать std::greater<> в качестве аргумента Compare template.
