C++ Priority queue of object pointers at runtime error as invalid heap

Question

I have been trying to implement a priority queue in c++ for about 5 hours now.

I dont believe my comparator functor is doing what it should be but for the life of me I can't work out why.

At the bottom of my Node class I have a struct CompareNode, the Node class has a function to return an int member variable.

 class Node
 {
 public:
     Node();
     ~Node();
     Node(const Node &obj);

     int GetX() const { return x; }
     int GetY() const { return y; }
     int GetG() const { return g; }
     int GetH() const { return h; }
     int GetF() const { return f; }
     int GetTerrainPenalty() const { return terrainPenalty; }
     bool GetOpenList() const { return openList; }
     bool GetClosedList() const { return closedList; }
     Node* GetParentNode() const { return parentNode; }
     std::vector<Node*> const GetNeighbours() { return neighbours; }

     void SetX(int x) { this->x = x; }
     void SetY(int y) { this->y = y; }
     void SetG(int g) { this->g = g; }
     void SetH(int h) { this->h = h; }
     void SetF(int f) { this->f = f; }
     void SetTerrainPenalty(int t) { this->terrainPenalty = t; }
     void SetOpenList(bool b) { this->openList = b; }
     void SetClosedList(bool b) { this->closedList = b; }
     void SetParentNode(Node* n) { this->parentNode = n; }
     void SetNeighbours(std::vector<Node*> n) { this->neighbours = n; }

     void AddNeighbour(Node* n) { neighbours.push_back(n); }

     // Manahattan Distance
     void CalculateH(Node* end);
     void CalculateF();

 private:
     int x;
     int y;
     int g;
     int h;
     int f;
     int terrainPenalty;
     bool openList;
     bool closedList;
     Node* parentNode;
     std::vector<Node*> neighbours;

 };

 struct CompareNode
 {
     bool operator()(const Node* lhs, const Node* rhs) const
     {
         return lhs->GetF() < rhs->GetF();
     }
 };

In my main.cpp I declare the priority queue.

 std::priority_queue<Node*, std::vector<Node*>, CompareNode> openList;

I get a Debug Assertion Failed error, Invalid Heap.

When debugging it seems that when I call openList.top() it doesn't return the correct Node.

Any ideas what I am doing wrong?

Shouldn't it be priority_queue<Node, vector<Node>, CompareNode> if CompareNode gets two const Node* ? — tgmath
– tgmath, Commented Mar 25, 2014 at 17:23
Without priority_queue<Node*, vector<Node*>, CompareNode> I couldn't push a pointer object to the queue. For example Node* n; openList.push(n); — kev3kev3
– kev3kev3, Commented Mar 25, 2014 at 17:32
why do you need c++ for doing your task? looks like you don't have time to really learn it. if you don't really learn c++ you in trouble. try python (or java or c#) instead. — lowtech
– lowtech, Commented Mar 25, 2014 at 17:33
ok, if you really have to do what you are doing post all code, including main and any other functions. then I (or somebody else) will have a chance to help you. — lowtech
– lowtech, Commented Mar 25, 2014 at 17:51

Mark B · Accepted Answer · 2014-03-25 17:22:09Z

1

My psychic debugging powers tell me that since you didn't implement a copy constructor for your Node, that you're accidentally copying it somewhere resulting in a double delete.

answered Mar 25, 2014 at 17:22

Mark B

96.5k10 gold badges113 silver badges198 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

kev3kev3 Over a year ago

Will put a copy constructor in, and let you know if it solves this.

CPlusPlus OOA and D Over a year ago

I agree that without a copy constructor and having two internal data members that involve pointers, the default copy constructor is going to cause problems every time.

kev3kev3 Over a year ago

I implemented the copy constructor but I am still getting the same Debug Assertion invalid heap error.

CPlusPlus OOA and D Over a year ago

@kev3kev3 Sounds like the copy constructor body is not executing a deep copy.

CPlusPlus OOA and D Over a year ago

@kev3kev3 When using Standard Library containers (e.g. vector, map, list, queue, etc.), it is a good practice to always implement the == and < operators for the object stored inside a container. Storing pointers inside a container becomes more involved to properly release the memory before the container is destroyed. The container destructor does not invoke each element's destructor, when the element is a pointer. As lowtech says above, all of the implementation details are needed in order to continue assisting.

|

Collectives™ on Stack Overflow

C++ Priority queue of object pointers at runtime error as invalid heap

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related