Insertion sort of a map

Question

I have a map (for example, of character to integer). I insert values into this map one by one. For example, here are four insertions:

1: A -> 1
2: B -> 2
3: C -> 3
4: D -> 1

I would like to sort the map keys based on their associated values. So, at each insertion, I would have the sorted output:

1: A(1)
2: B(2), A(1)
3: C(3), B(2), A(1)
4: C(3), B(2), A(1), D(1)

Furthermore, I would like to be able to overwrite existing mappings to keep the keys (characters) unique. So a fifth insertion:

5: A -> 27

Would cause the sorted output to be:

5: A(27), C(3), B(2), D(1)

One way I can do this is using a multimap. The key of the multimap would be the integer, and the values would be the characters. Each insertion into the multimap would first need to check if the character is already present in the multimap, and remove that mapping before performing the insertion. The multimap keeps the keys ordered, so that takes care of the sorting.

Is there a faster way to do this? Is there a different, more efficient container that I should be using?

EDIT

Here's the C++ STL multimap I'm using. It's handy because it keeps its elements internally ordered.

Here's a related question. I'm trying to avoid doing what's suggested in the accepted solution: creating another map.

Answer 1

What I would have done would be something like this. Imagine your map maps x to y. I would create a struct (class, whatever):

struct element
{
    map_this_t x;
    to_this_t  y;
    bool operator < (element &rhs)
    {
        return y < rhs.y;       // sorted based on y
    }
};

Then create a set<element> and insert into that. If you iterate over all the data in the set, you well get the data in the order you want. When inserting, first search and see if an element with x value as the one you want exists. If so, just update the y, otherwise insert a new element.

Answer 2

Generally a map is a shuffled data structure (at least for the associated values). So, sorting elements of a map is meaningless.

Therefore you should use something like list or array to keep elements sorted.

I think the best solution for your issue is the simplest way: Store the elements in a list and sort it. Or you can use heaps.

UPDATE:

Maps are a kind of associative container that stores elements formed by the combination of a key value and a mapped value.

In a map, the key value is generally used to uniquely identify the element, while the mapped value is some sort of value associated to this key. Types of key and mapped value may differ. For example, a typical example of a map is a telephone guide where the name is the key and the telephone number is the mapped value.

Internally, the elements in the map are sorted from lower to higher key value following a specific strict weak ordering criterion set on construction.

As associative containers, they are especially designed to be efficient accessing its elements by their key (unlike sequence containers, which are more efficient accessing elements by their relative or absolute position) [1].

[1] http://www.cplusplus.com/reference/stl/map/