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

Ответ 1

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

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

Это означает, что 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

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

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

Ответ 2

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

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

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

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

• Сделайте части вашего класса, которые следует изменить как mutable. Таким образом, вы можете получить элемент top() и изменить изменяемое содержимое, даже если это const.

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

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