Priority Queue for D* Lite

Question

So, I needed a priority queue for D* lite and I wanted to know whether this is an acceptable implementation or not.

#ifndef BCC940D8_CEDF_4B76_8CE4_D8C9A4D1A787
#define BCC940D8_CEDF_4B76_8CE4_D8C9A4D1A787
#include <queue>
#include <vector>
#include <list>
#include <functional>
#include "Node.hpp"
#include "Key.hpp"
namespace Pathfinding::Datastructures
{
 class NodeComperator
 {
 public:
 bool operator() (const Node * lhs, const Node * rhs)
 {
 return lhs->key > rhs->key;
 }
 };
 class PriorityQueue final : public std::priority_queue<Node *, std::vector<Node *>, NodeComperator>
 {
 public:
 void remove(Node *node)
 {
 auto it = std::find_if(this->c.begin(), this->c.end(), 
 
 [&node](const Node * element)
 { 
 return *element == *node; 
 });
 this->c.erase(it);
 std::make_heap(this->c.begin(), this->c.end(), this->comp);
 }
 void insert(Node *node)
 {
 this->push(node);
 }
 void reset()
 {
 c.clear();
 std::make_heap(this->c.begin(), this->c.end(), this->comp);
 }
 Key topKey() const
 {
 if (this->empty())
 {
 return Key();
 }
 return this->top()->key;
 }
 Node *popD()
 {
 auto topNode = this->top();
 pop();
 return topNode;
 }
 bool contains(const Node *node)
 {
 return std::find_if(this->c.begin(), this->c.end(), 
 [&node](const Node* input)
 { 
 return *input == *node; 
 }) != this->c.end();
 }
 private:
 using std::priority_queue<Node *, std::vector<Node *>, NodeComperator>::pop;
 };
}
#endif /* BCC940D8_CEDF_4B76_8CE4_D8C9A4D1A787 */

Nodes are sorted by key which is a tuple with two floats. "Keys are compared according to a lexicographic-ordering".

Answer 1

Unnecessary use of this->

It is almost never necessary to use this-> in C++. I recommend you remove all occurrences of it in your code.

Unnecessary call to std::make_heap()

It is not necessary to call std::make_heap() after clearing the underlying container.

Naming things

I would rename remove() to erase(), as the remove() function in STL does mean something different than erasing.

insert() is just equivalent to push(). I would recommend removing insert(), and just let the caller use push() instead, which is publicly inherited.

popD() looks weird. I would just rename this to pop(); it will give you the functionality you want, and in a way it's still compatible with the STL's pop().

Missing const

contains() does not modify the queue, so it should be made const. Furthermore, remove() doesn't modify node, so you should make that parameter a const pointer.

Use std::find() to find a specific node

You can use std::find to find a specific value without needing a lambda:

bool contains(const Node *node) const {
 return std::find(c.begin(), c.end(), node) != c.end();
}

Simplifications possible using C++20

If you can use C++20, you can simplify your code somewhat. There are std::ranges versions of some of the algorithms, and you can use std::erase() to remove an item from the underlying vector by value. So for example, you could write:

void erase(const Node *node) {
 std::erase(c, node);
 std::ranges::make_heap(c);
}

Unfortunately there is no std::contains() in C++20, and it seems there won't even be any in C++23.

• a a: Thank you for your feedback. Pseudocode of the algorithm used this naming for methods, I kept it for easier understanding. Also, I don't think I can rename popD to pop because this function is already present in the base class and since it is not virtual, it is not overwritten, but yeah, popD is a bad name.
• G. Sliepen: It will be overwritten in the derived class, and you can have the derived class call pop() of the base class by doing something like: using base = std::priority_queue<Node *, std::vector<Node *>, NodeComperator>; ...; base::pop();