Quote: Original post by NotAYakk
Kylotan, adding to the middle of a vector or deque is an O(n) operation. Horridly expensive.
The STL uses a heap to implement it's priority queue -- O(lg n) sorted insert.
Wouldn't it be a good idea to at least get the A* algorithm working using a priority queue, and then speed up the "get next" and "add" abstractions?
The point I was making is that big-O notation is only a guide and is not the only consideration in algorithm performance. Sometimes the less intuitive approach works better because it is simpler and makes better use of the hardware.
Bear in mind that multiple consecutive vector or deque insertions can potentially be as efficient as a single one, if what you're inserting is contiguous. This is actually quite common in A* when you come to add several sibling nodes. Or add them to the end and perform a linear search - this is typically nowhere near as bad as you may expect if your node structure is compact and your comparison criteria is simple.
I know how the STL (typically) implements its priority queue - it implements it in a way that is fairly good if you don't ever want to traverse that structure (which you almost always do) and don't want to remove elements from the structure (which you usually do).
You perhaps also forget that while finding the best element is constant time, actually popping it is done in logarithmic time. Using std::priority_queue does not allow any practical optimisation of that operation.
I tend to start off with quite naive implementations and then tune them up as I go; unfortunately the priority queue adapter limits your options somewhat.
