Очередь приоритетов стандартной библиотеки шаблонов C ++ выдает исключение с сообщением «Invalid Heap»

Question

Используя STL priority_queue, я получаю ошибку "недопустимая куча", как только я пытаюсь использовать pop(). Я могу поместить свои значения в очередь, top() очереди - это то, что я ожидаю и доступно. pop(), когда он переходит в кучу, кажется, есть проблема.

Я храню указатели на шаблонный класс в очереди. У меня перегружено сравнение:

template <class type>
class vertexPriorityCompare
{
public:
   bool operator()(Vertex<type>* leftVertex, Vertex<type>* rightVertex) const
   {
      if(leftVertex->getDistanceFromSource() < 0 && rightVertex->getDistanceFromSource() < 0)
      {
         return false;
      }
      else if(leftVertex->getDistanceFromSource() < 0)
      {
         return true;
      }
      else if(rightVertex->getDistanceFromSource() < 0)
      {
         return false;
      }
      else
      {
         return leftVertex->getDistanceFromSource() > rightVertex->getDistanceFromSource();
      }
   }
};

priority_queue является приватным членом класса:

priority_queue< Vertex<type>*, vector< Vertex<type>* >, vertexPriorityCompare<type> > Q;

Перегрузка работает так, как она работает, потому что отрицательное расстояние считается бесконечностью, всегда больше, чем все остальное; чтобы представить бесконечность, расстояния инициализируются до -1. Очередь должна быть наименьшей, но неотрицательной наверху.

Я разыменую указатели в перегрузке, допустимо ли то, что я там делаю? И есть ли другой оператор, который мне нужен для перегрузки?

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

Я динамически объявляю массив указателей на указатели, это то, что запихивается, потому что я предполагаю, что priority_queue хранится по ссылке, поэтому, если я просто помещу указатель, объявленный в цикле, в очередь, этот указатель выходит из области видимости , Эти указатели указывают на правильный Vertex<type> и существуют во всей функции.

Отладчик Visual Studio 2008 переводит меня в строку 24 stdthrow.cpp.

Answer 1

Функция сравнения выглядит отлично, , если , значение объекта getDistanceFromSource() не изменяется, пока этот объект находится в очереди. Это гарантировано? Или могут быть изменения, внесенные в объекты, которые влияют на getDistanceFromSource(), пока они находятся в очереди или когда очередь изначально заполнена?

Answer 2

Это, вероятно, ваша функция сравнения. Чтобы проверить, замените его простой версией, которая просто сравнивает указатели:

bool operator()(...)
{
  return leftVertex<rightVertex;
}

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

Answer 3

Этот бит пугает меня:

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

Не совсем понятно, как вы заполняете очередь. Вы должны создать объекты Vertex, и они должны оставаться в памяти и возвращать одинаковое расстояние все время, пока они находятся в очереди.

Очередь не хранится по ссылке, она хранит копии - но в этом случае вы вставляете указатели, поэтому копирует указатель, который все равно будет указывать на исходные объекты, которые вы выделили.

Я думаю, нам понадобится короткий законченный пример, чтобы продолжить.

Answer 4

Без стека вызовов будет немного трудно определить, в чем проблема, но вы либо неправильно распределяете Vertex<...>, пытаетесь освободить Vertex<...> из стека или не инициализируете Vertex<...>* для действительные значения.

Answer 5

Откуда вы вызываете эту функцию?

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

Я не вижу ничего плохого в этой функции.

Пожалуйста, укажите трассировку стека