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

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/

Answer 2

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 3

A map is sorted by it's keys, by definition.

The values cannot be used in the ordering predicate for a map, because the values are non-const! Changing them would invalidate the container invariants (ordering).

If you want the entries ordered by 'value', it is implicitely a key, and you likely require a

std::set<std::pair<key, value> >

Update Here is a working demo of that: https://ideone.com/SgbEN

instead. To be able to re-order by a different predicate in place, you'd need a list, vector or any other sequential container.

Edit

The list solution is far too inefficient, since I would have to sort after each insertion, and wouldn't have an effective way of keeping the keys unique.

The solution here is to use the

• std::make_heap
• std::push_heap
• and std::sort_heap

algorithms. They work well with lists (as well as vectors for cheap value_types - or using c++0x move semantics)

If you cannot afford the sort_heap step before using the list as ordered: use

insert_point = std::lower_bound(lst.begin(), lst.end(), insertee);
st.insert(insertion_point, insertee);

to insert directly in ordered position. You can expect push_heap to be faster for many insertions, and lowerbound/insert to be faster for many accesses

Answer 4

just use a map <char,int> and your keys will remain unique an pairs of <char,int> will store sorted in it.

to sort the elements based on their associated values store pair<int,char> in a set too.