C++ освобождает память в priority_queue

Question

У меня есть

priority_queue<node*, std::vector<node*>, CompareNodes> heap;

Допустим, узел состоит из:

class node {
public:
    int value;
    int key;
    int order = 1000000;
};  

Как мне освободить память после того, как я закончу с очередью приоритетов? Мой подход, похоже, не работает:

while (heap.top()) {

        node * t = heap.top();
        heap.pop();
        delete t;
    }

Answer 1

Похоже, вы захотите сделать что-то более похожее на это:

while (!heap.empty())
{ /* the rest ... */ }

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

Кроме того, если доступно, вы должны использовать

priority_queue<std::unique_ptr<node>, std::vector<std::unique_ptr<node>>, CompareNodes> heap;

так что вам не нужно беспокоиться об очистке памяти самостоятельно.

Answer 2

Как и большинство std:: Containers, память может или не может быть освобождена, когда вы этого хотите. Память обычно хранится в течение более длительного времени, поэтому при выполнении команды heap.push или аналогичной операции память не нужно выделять снова.

Подумайте о std::vector, который должен выделять новый набор памяти для всего вектора каждый раз, когда он растет (векторные данные должны быть смежными в памяти). Для std::vector более эффективно выполнять одноразовое большое выделение и сохранять память таким образом, чтобы операция роста не снижала производительность - а) выделять достаточно много нового пространства, б) копировать все содержимое существующего вектора в новое векторное пространство, c) удалить старое векторное пространство.

Суть в том, что вы не можете заставить его освободить память для отдельных предметов.