c++ set versus vector + heap operations for an A* priority queue

Question

When is using a std::set more efficient (w.r.t. time) than using a std::vector along with make_heap/push_/pop_ for the priority queue in an A* operation? My guess is that if the vertices in the open list are small, using a vector is a better option. But does anyone have experience with this?

Answer 1

If i had to venture a guess? I'd guess that the vector version is probably a good choice because once it grows to a certain size, there won't be very many allocs.

But I don't like guessing. I prefer hard numbers. Try both, profile!

Answer 2

I don't think a vector based data structure for a priority queue for an A* search is a good idea because you're going to be constantly adding a single element somewhere in the list. If the fringe (I assume this is how you're doing it) is large and the element is to be added in the middle, this is highly inefficient.

When I implemented A* in Java a few weeks ago, I used the Java PriorityQueue which apparently is based on a priority heap, and that seems like a good way to do it. I recommend using set in C++.

EDIT: thanks Niki. I now understand how binary heaps are implemented (with an array), and I understand what you're actually asking in your question. I suspect a priority_queue is the best option, although (as Igor said) it wouldn't be hard to swap it over to a set to check the performance of that. I'm guessing there's a reason why priority queues (in Java and C++ at least) are implemented using binary heaps.

Answer 3

If you're doing A* pathfinding work, check out the articles in AI Wisdom by Dan Higgins. In there is a description of how to get data structures fast. He mentions a "cheap list" which is like having a hot cache for recent nodes and avoiding a lot of the penalties for pathfinding data structures.

http://introgamedev.com/resource_aiwisdom.html

Answer 4

1. For A* search, I would go with a std::vector-based priority queue.
2. However, the change in the implementation from std::vector to another STL container should be quite trivial, so I would experiment with different versions and see how does it affect the algorithm performance. In addition to stl::map, I would definitely try stl::deque.

Answer 5

Use a priority queue. A binary heap based one is fine (like the vector based std priority queue). You can build the heap in O(n) time and all relevent operations take O(logn). In addition to that you can implement the decrease key operation which is useful for a*. It might be tricky to implement for the std queue however. The only way to do that with a set is to remove the element and reinsert it with a different priority.

Edit: you might want to look into using

std::make_heap

(and related functions). That way you get access to the vector and can easily implement decrease_key.

Edit 2: I see that you were intending on using make heap, so all you'd have to do is implement decrease key.