Is multimap the right choice

[tiloarens]

Hi,

I require a container for (key,value)-pairs allowing two actions:

* insertion of new entries in the container,
* removing of an entry with the smallest key

Keys will not necessarily be unique.

A multimap will allow those two actions so I could use it for my purposes. My question is whether it is the most efficient container when only those two actions need to be performed? Are there other possibilities?

Thanks, Tilo

[LB]

Don't concern yourself with efficiency until you have profiled your code and found a bottleneck. Choose the method that works the best, and then later if it is the bottleneck you can replace it with something faster.

[MiiNiPaa]

What should happen if there are several elements with smallest key and you are trying to remove element with smallest key?

[tiloarens]

Anyone entry with the smallest key can be removed, this does not need to be specified.

This is about a load balancing application: The key is the load, the mapped value the number of a process. Some process with the smallest load so far should get assigned the next task.

[LB]

If the key is changing, map is the wrong container. You could remove and reinsert, but that just mitigates the problem.

[MiiNiPaa]

If a single entry from those with smallest key is needed to be removed, consider using a priority queue pair<key, valaue>. It works nicely for that.

If all entries with smallest key are needed to be deleted, use multimap. It is easier to get/erase range of elements in it.

[tiloarens]

Thanks! Of course this is exactly what is required.