std::priority_queue
стабилен?
то есть элементы с одинаковым приоритетом извлекаются из очереди в том же порядке, в котором они были при вводе контейнера в очередь?
Порядок элементов в std::priority_queue
зависит в первую очередь от функции сравнения, а не от порядка, в котором они были добавлены.
@wohlstad вопрос в порядке элементов, эквивалентных функции сравнения
@ 463035818_is_not_an_ai Понятно. Возможно, вопрос должен быть более четким.
Нет. Если вам нужен уникальный порядок, вам нужна функция сравнения, которая дает уникальные результаты.
@wohlstad «одинаковый приоритет» означает, что элементы эквивалентны для функции сравнения.
@463035818_is_not_an_ai ты прав. Пропустил это. Это делает вопрос более интересным. +1.
@KonstantinMakarov Нет, это не так. Стабильность означает сохранение порядка вставки при равенстве ключей.
Насколько я вижу: timsong-cpp.github.io/cppwp/draft.pdf в std::priority_queue
нет ничего, что помечено как стабильное.
Нет. В этом коде priority_queue
заполнен структурами из двух полей. Поле x
указывает приоритет. Поле y
предназначено для проверки стабильности. Обратите внимание, что элементы с приоритетом 1 содержат поля y
в следующем порядке: 1, 2, 3, 2, 1
. Если очередь стабильна, то этот порядок не изменится.
#include <iostream>
#include <queue>
int main() {
struct s { int x, y; };
auto cmp = [](const s& s1, const s& s2) { return s1.x > s2.x; };
std::priority_queue<s, std::vector<s>, decltype(cmp)> q;
q.push({ 2, 1 });
q.push({ 1, 1 });
q.push({ 1, 2 });
q.push({ 1, 3 });
q.push({ 1, 2 });
q.push({ 1, 1 });
for (; !q.empty(); q.pop())
std::cout << std::format("({}, {})\n", q.top().x, q.top().y);
}
Но результат показывает обратное:
(1, 1)
(1, 2)
(1, 1)
(1, 2)
(1, 3)
(2, 1)
Код публикации неверен. Результат зависит от реализации. Отсутствие гарантии не означает, что он всегда выйдет из строя. И поэтому это заблуждение.
Если условие стабильности не выполняется хотя бы на одном компиляторе, не означает ли это, что стабильности нет?
@KonstantinMakarov, дело не в этом. Кто-то попробует этот код и может увидеть другой результат и будет сбит с толку. И задумается, ошибся ли он или этот ответ неправильный? Или, может быть, ошибка в стандарте?
@freakish, Да. Возможно. Здесь нужны доказательства.
Почему вы не использовали уникальные значения для y
? Это усложняет анализ. После небольшой настройки вашего примера элементы, которые равны, похоже, сохраняют свой порядок (но это ничего не доказывает, просто ваше утверждение, основанное только на примере, недействительно). Какой компилятор вы использовали для получения такого результата? Как вы можете видеть, gcc и clang кажутся стабильными.
См. ..., (3, 7), (3, 6)
в вашем результате.
«Почему вы не использовали уникальные значения для y
?» - Все люди думают по-разному. Ваш пример также показывает нестабильность.
Нет, такой гарантии нет. Однако вы можете очень легко подражать этому самостоятельно. Оберните его типом, который прикрепляет счетчик автоматического приращения к каждому элементу. Что тогда становится частью приоритета.