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).