I am implementing the A* path finding routines against a sparsely populated graph object. The algorithm appears to be fairly straight forward to implement. My question for the group though is how to implement the open and closed lists - specifically the open list.
In the implementation the open list needs to satisfy the following functionality: Find (and remove) the node with the most minimum F-Cost value stored in the list; be able to re-order the list in case an existing node's F-Cost changes (i.e. a new route to the same node is cheaper); and, be able to find a specific node by name or ID value or whatever.
I have been reading up on the different structures and it seems that perhaps the STL data structure that most closely matches my needs is the Map. However, before I start coding, I wanted to ask the group here if there was perhaps a different data structure that they would recommend.
You can do this with map or multimap containers, or you can creat your own container if you know somethink about OOP and templates :) it is fun and when you end container you will be pround :) but faster way is use one of containers from STL