which std container to use in A* algorithm's openSet?

Question

I'm implementing the A* algorithm using std::priority_queue on the openSet. At some point on the algorithm, as in wikipedia pseudo-code:

else if tentative_g_score < g_score[neighbor]
    tentative_is_better := true

followed by

if tentative_is_better = true
    came_from[neighbor] := current
    g_score[neighbor] := tentative_g_score
    f_score[neighbor] := g_score[neighbor] + h_score[neighbor]

means that one has to perform a search on the priority_queue and change a value of one of their elements, which is not possible (as far as I understood).

Also, on this line:

if neighbor not in openset

one cannot search on a priority-queue and so this if cannot be implemented on a priority_queue, which I solved by creating a std::set which only tell us which elements are on the openSet (so that when I add/remove one element to the openSet, I add/remove to both std::set and std::priority_queue).

So, I wonder how can I avoid the first problem, or which std::container should one really use for this particular (yet general A*) implementation.

More generically, I wonder which is an efficient approach to A* using std containers?

Answer 1

Unfortunately, the std:: containers don't currently support the operations you require - what's really needed is an "indexed" priority queue that supports decrease/increase_key style operations.

One option is to roll your own container (based on an augmented binary heap) that does this, if this sounds like too much work, you can almost fake it by making use of an augmented std::set data structure - both options are discussed in more detail here.

As others have said, another option is to just remove the priority queue entirely and try to maintain a sorted std::vector. This approach will work for sure, and might require the least coding on your part, but it does have significant implications for the asymptotic scaling of the overall algorithm - it will no longer be possible to achieve the fast O(log(n)) updates of the queue while maintaining sorted order.

Hope this helps.