Как получить неконстантный верхний элемент из priority_queue с определенными пользователем объектами?

Question

Как получить неконстантный верхний элемент из priority_queue с определенными пользователем объектами?

станд :: priority_queue :: топ возвращает постоянное значение. Однако я хотел бы удалить верхний элемент из приоритетной очереди и иметь возможность изменить его где-нибудь еще.

priority_queue<SomeClass, vector<SomeClass>, SomeClassCompare > pQueue;
...
SomeClass *toBeModified = &(pQueue.top());
pQueue.pop();
toBeModified->setMember(3); // I would like to do this

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

11

c++c++11 const pop priority-queue

Решение

Другие решения

Я не думаю, что семантика значения играет здесь наименьшую роль. Все остальные контейнеры имеют одинаковую семантику значений, и почти все они обеспечивают front() с изменяемой ссылкой.

Есть одна точная причина, почему priority_queue запрещает модификацию top() элемент: это потому, что конкретный элемент находится на вершине, потому что он был соответствующим образом квалифицирован в соответствии с его текущей стоимостью. Элементы в очереди приоритетов всегда сортируется в соответствии с критериями сравнения, настроенными для очереди (оператор < по умолчанию). Изменяя элемент, вы можете потенциально разрушить это условие и заставить все операции, использующие отсортированное предварительное условие, вызывать неопределенное поведение.

Короче, причина почему priority_queue не позволяет изменять содержащиеся элементы точно так же, как в случае set и ключи для map,

Я понимаю, что у вас может быть какой-то специальный метод сравнения, вы используете поле, которое содержит значение для сравнения, и вы собираетесь изменить любое содержимое объекта, кроме этого самого поля. Таким образом, вы не нарушаете требование отсортированного заказа. Вы можете сделать две вещи:

Сделайте части вашего класса, которые должны быть изменены как mutable, Таким образом, вы можете получить элемент по top() и измените изменяемое содержимое, даже если это const.
Создайте свой собственный класс очереди приоритетов, выведя std::priority_queue, Имеет поле с именем c (в защищенный раздел), который содержит ссылку на нижележащий контейнер, а нижележащий контейнер всегда имеет front() метод, который обращается к тому же элементу, что и top() в priority_queue, Для вашей же безопасности, вы должны сделать свое ключевое поле const, так что он устанавливается во время строительства и никогда не изменяется — просто чтобы минимизировать риск.

Ах, и эту проблему также нельзя решить с помощью указателей — заостренные объекты будут точно такой же константой. Эта «ссылочная семантика» также никоим образом не поможет вам, потому что, если вы хотите иметь выделенный метод сравнения, ему придется изучить содержимое объектов, и в этом случае у вас будет точно такая же проблема. Это помогло бы вам, если бы вы полагались на простое сравнение значений указателей, но я бы скорее сомневался, что это может быть решением для 99% случаев.

1

Источник

Accepted Answer

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

Даже если top() вернет вам ссылку наconstэта ссылка станет висящей, как только вы удалите элемент из очереди, а разыменование приведет к неопределенному поведению.

Это сказал, std::priority_queue возвращает вам ссылку на const чтобы вы не мешали (намеренно или непреднамеренно) внутреннему упорядочению — это почти та же причина, по которой ключ ассоциативных контейнеров, таких как std::map а также std::set является const,

Вместо этого вы можете построить копия значения, возвращаемого top(), измените эту копию, удалите оригинал и поместите копию в очередь:

SomeClass obj = pQueue.top();
pQueue.pop();
obj.setMember(42);
pQueue.push(std::move(obj)); // You can move obj into the queue if you no more need it

Если тебе надо семантика ссылок, с другой стороны, тогда вам придется подтолкнуть указатели в очередь (возможно, умные указатели, в зависимости от вашего варианта использования) и предоставьте соответствующий пользовательский критерий упорядочения, который упорядочит эти указатели на основе свойств объектов, на которые они указывают.

В этом случае будьте осторожны, чтобы не изменять эти свойства во время выполнения так, чтобы их порядок изменился. Это будет считатьсявозиться с внутренним заказом контейнера«и приведет к неопределенному поведению.

14