INVALID HEAP при использовании STL make_heap / push_heap / pop_heap - PullRequest
Новая
       17

INVALID HEAP при использовании STL make_heap / push_heap / pop_heap

0 голосов
/ 30 ноября 2011

Я написал простую оболочку для std :: make_heap / push_heap / pop_heap: 

template <typename T, typename Cont = std::vector<T>, typename Compare = std::less<typename Cont::value_type> >  
class Heap  
{  
public:  
    inline void init() { std::make_heap(m_data.begin(), m_data.end(), Compare()); }  
    inline void push(const T & elm) { m_data.push_back(elm); std::push_heap(m_data.begin(), m_data.end(), Compare()); }  
    inline const T & top() const { return m_data.front(); }  
    inline void pop() { std::pop_heap(m_data.begin(), m_data.end(), Compare()); m_data.pop_back(); }  

private:  
    Cont m_data;  
};

, которую я использую как: 

class DeliveryComparator
{
public:
    bool operator()(Delivery * lhs, Delivery * rhs)
    {
        if(lhs->producer != rhs->producer) return *lhs->producer < *rhs->producer;  
        if(lhs->rate == rhs->rate) return lhs->diff < rhs->diff;  
        return lhs->rate < rhs->rate; 
    }
};

Heap<Delivery*, std::vector<Delivery*>, DeliveryComparator> packages;

Но иногда я получаю INVALID HEAP стандартное отладочное сообщение.Я использую кучу только через правильные методы кучи.Когда появляется сообщение, m_data не пустые.

Что может быть не так с кучей?

* Я использую MSVS2010

1 Ответ

0 голосов
/ 03 декабря 2011

После редактирования данных кучи (кроме тех, которые ожидают добавления), куча была уничтожена.Если вы используете метод push_heap () далее, это исключение будет выброшено.Вы должны использовать make_heap () вместо push_heap ().Например (кстати, следующий пример - фрагмент кода из моей программы): 

if (highHeap[0] < solvedQuestions){ 
               lowHeap[lenghOfLowHeap++] = highHeap[0]; // *It only add a new item without destroy the heap 
               highHeap[0] = solvedQuestions;
               // Update the Heap
               push_heap(lowHeap, lowHeap + lenghOfLowHeap); 
               //push_heap(highHeap, highHeap + lenghOfHighHeap, greater<int>()); // invalid heap exception. Because the heap was destroyed by "highHeap[0] = solvedQuestions;"
               make_heap(highHeap, highHeap + lenghOfHighHeap, greater<int>());
           }
...