How do i sort a STL Map?

[Jimmy_Dog]

I have an STL map using int key and int value. How do i sort the map from smallest to largest based on it's value without losing the associated key. Then return the keys in that order? ( i want to then push the keys onto a queue).

[Lindley]

Maps are automatically sorted by key. If your primary need is to be able to sort by value, then you should consider whether you've defined the map backwards.

If you need at various times to view the objects in both orderings, then you should consider a data structure which captures this relation a bit better than a std::map. The most trivial example of such would be a class simply wrapping both a map<A,B> and a map<B,A>, which contain identical pairs of data at all times. Another approach would be to use a boost::bimap.

[Jimmy_Dog]

I have solved the problem. A multimap (instead of a map) resolved the issues of having duplicate keys. Like you said Lindley, I inversed the elements in the multimap (i.e. put the values that required sorting into the key, and put the keys as values). That way when the container is sorted via its keys, then i can then simply push my values (which are the indexes that i am after), back onto the queue.

For curiousities sake, this seems to be an effective and efficient way of prioritising a pending list based on their cost for pathfinding purposes (which is where i have applied the multimap).

[Lindley]

Priority queues (and there's one in the STL, by the way) are usually based on heaps rather than trees, since a full sort is not required. The difference in efficiency is minor but present.