Является ли std::std::priority_queue стабильным?

std::priority_queue стабилен?
то есть элементы с одинаковым приоритетом извлекаются из очереди в том же порядке, в котором они были при вводе контейнера в очередь?

Нет, такой гарантии нет. Однако вы можете очень легко подражать этому самостоятельно. Оберните его типом, который прикрепляет счетчик автоматического приращения к каждому элементу. Что тогда становится частью приоритета.

freakish 17.06.2024 08:33

Порядок элементов в std::priority_queue зависит в первую очередь от функции сравнения, а не от порядка, в котором они были добавлены.

wohlstad 17.06.2024 09:30

@wohlstad вопрос в порядке элементов, эквивалентных функции сравнения

463035818_is_not_an_ai 17.06.2024 09:40

@ 463035818_is_not_an_ai Понятно. Возможно, вопрос должен быть более четким.

wohlstad 17.06.2024 09:44

Нет. Если вам нужен уникальный порядок, вам нужна функция сравнения, которая дает уникальные результаты.

Pepijn Kramer 17.06.2024 09:44

@wohlstad «одинаковый приоритет» означает, что элементы эквивалентны для функции сравнения.

463035818_is_not_an_ai 17.06.2024 09:50

@463035818_is_not_an_ai ты прав. Пропустил это. Это делает вопрос более интересным. +1.

wohlstad 17.06.2024 09:51

@KonstantinMakarov Нет, это не так. Стабильность означает сохранение порядка вставки при равенстве ключей.

user207421 17.06.2024 10:14

Насколько я вижу: timsong-cpp.github.io/cppwp/draft.pdf в std::priority_queue нет ничего, что помечено как стабильное.

Frodyne 17.06.2024 10:36
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
4
9
146
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Нет. В этом коде 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)

Код публикации неверен. Результат зависит от реализации. Отсутствие гарантии не означает, что он всегда выйдет из строя. И поэтому это заблуждение.

freakish 17.06.2024 09:35

Если условие стабильности не выполняется хотя бы на одном компиляторе, не означает ли это, что стабильности нет?

Konstantin Makarov 17.06.2024 09:42

@KonstantinMakarov, дело не в этом. Кто-то попробует этот код и может увидеть другой результат и будет сбит с толку. И задумается, ошибся ли он или этот ответ неправильный? Или, может быть, ошибка в стандарте?

freakish 17.06.2024 09:45

@freakish, Да. Возможно. Здесь нужны доказательства.

Konstantin Makarov 17.06.2024 09:51

Почему вы не использовали уникальные значения для y? Это усложняет анализ. После небольшой настройки вашего примера элементы, которые равны, похоже, сохраняют свой порядок (но это ничего не доказывает, просто ваше утверждение, основанное только на примере, недействительно). Какой компилятор вы использовали для получения такого результата? Как вы можете видеть, gcc и clang кажутся стабильными.

Marek R 17.06.2024 10:40

См. ..., (3, 7), (3, 6) в вашем результате.

Konstantin Makarov 17.06.2024 11:12

«Почему вы не использовали уникальные значения для y?» - Все люди думают по-разному. Ваш пример также показывает нестабильность.

Konstantin Makarov 17.06.2024 11:22

Другие вопросы по теме