La file d'attente de priorité de bibliothèque de modèles standard C++ renvoie une exception avec le message "Heap invalide"

Question

En utilisant le priority_queue STL, j'obtiens l'erreur "tas invalide" dès que j'essaie d'utiliser pop(). Je peux pousser mes valeurs dans la file d'attente, le top() de la file d'attente est ce que je m'attendais et accessible. pop(), quand il va re-tas, semble avoir un problème.

Je stocke des pointeurs vers une classe basée sur un modèle dans la file d'attente. Je le comparision surchargé:

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(); 
     } 
    } 
}; 

Le priority_queue est membre privé d'une classe:

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

Les travaux de surcharge de la façon qu'il le fait, car une distance négative est considéré comme infini, toujours plus grand que n'importe quoi d'autre; pour représenter l'infini, les distances sont initialisées à -1. La file d'attente doit garder le plus petit, mais non négatif au sommet.

Je déréférence les pointeurs dans la surcharge, est ce que je fais là permise? Et, y a-t-il un autre opérateur que je dois surcharger?

Je voudrais joindre le code, mais il semble que si je le fais, il effraie les gens. Demande d'en voir plus et je vais attacher à un autre message. Je déclare dynamiquement un tableau de pointeurs sur des pointeurs, ceux-ci sont poussés, car je suppose que priority_queue stocke par référence, donc si je mets juste un pointeur déclaré dans la boucle dans la file, ce pointeur sort de la portée. Ces pointeurs pointent vers le bon Vertex<type>, et existent tout au long de la fonction.

Visual Studio 2008 débogueur me prend en ligne 'stdthrow.cpp' 24.

Answer 1

Où appelez cette fonction vous? Je suppose que le tas invalide est un pointeur que vous passez dans la fonction à partir du code "this caller". Ou peut-être que vous sortez des limites lorsque vous prenez le sommet de votre vecteur.

Je ne vois rien de mal avec cette fonction.

S'il vous plaît fournir la trace de la pile

Answer 2

Sans callstack, il sera un peu difficile de déterminer quel est le problème, mais vous êtes soit ne pas attribuer correctement le Vertex<...>, en essayant de libérer Vertex<...> de la pile, ou non initialisation du Vertex<...>* à des valeurs valides.

Answer 3

C'est probablement votre fonction de comparaison. Pour tester, le remplacer par une version simple qui compare simplement les pointeurs:

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

Si le problème ne se produit alors le problème était votre fonction de comparaison était invalide. Votre comparateur doit définir un "strict-weak ordering". Je ne suis pas assez homme pour le montrer, mais je parie que c'est tout.

Answer 4

La fonction de comparaison semble bien, si la valeur d'un objets getDistanceFromSource() ne change pas, alors que cet objet est dans la file d'attente. Est-ce assuré? Ou y a-t-il peut-être des modifications apportées aux objets, qui influencent getDistanceFromSource(), alors qu'ils sont dans la file d'attente ou que la file d'attente est initialement remplie?

Answer 5

Ce bit me fait peur:

Je déclare dynamiquement un tableau de pointeurs de pointeurs, ce sont ce que sont poussés, parce que je suppose que magasins priority par référence, donc si je mets juste un pointeur déclaré dans la boucle dans la file d'attente, ce pointeur sort de la portée. Ces pointeurs pointent vers le sommet correct et existent dans toute la fonction.

Il n'est pas clair comment vous remplissez la file d'attente. Vous devez créer des objets Vertex et ils doivent rester en mémoire et renvoyer la même distance tout le temps qu'ils sont dans la file d'attente.

La file d'attente ne stocke pas par référence, elle stocke des copies - mais dans ce cas, ce que vous placez sont des pointeurs, donc elle copie le pointeur, qui pointera toujours vers les objets originaux que vous avez alloués.

Je pense que nous aurons besoin d'un exemple complet court pour aller plus loin.