When does using a std::multimap make sense?

It's hard to tell whether your benchmark is doing the right thing, so I can't comment on the numbers. However, a few general points.

It's hard to tell whether your benchmark is doing the right thing, so I can't comment on the numbers. However, a few general points: Why multimap rather than map of vectors: Maps, multimaps, sets and multisets are all essentially the same data structure, and once you have one, it's trivial to just spell out all four. So the first answer is, "why not have it"?

How is it useful: Multimaps are one of those things that you need rarely, but when you need them, you really need them. Why not roll my own solution? As I said, I'm not sure about those benchmarks, but even if you could make something else that isn't worse than the standard container (which I question), then you should consider the overall burden of getting it right, testing it and maintaining it.

Imagine a world in which you would be taxed for every line of code you wrote (that's Stepanov's suggestion). Re-use industry-standard components whenever possible. Finally, here's the typical way you iterate a multimap: for (auto it1 = m.cbegin(), it2 = it1, end = m.cend(); it1!

= end; it1 = it2) { // unique key values at this level for ( ; it2->first == it1->first; ++it2) { // equal key value (`== it1->first`) at this level } }.

You have forgotten one very important alternative: not all sequences are created equal. Especially, why a vector and not a deque or a list? Using list A std::map > should perform roughly equivalently to a std::multimap since list is node based as well.

Using deque A deque is the default container to use when you don't know for which to go and do not have any special requirement. With regard to the vector, you trade up some read speed (not much) for faster push and pop operations. Using a deque instead, and some obvious optimizations, I get: const uint32_t num_partitions = 100000; const size_t num_elements = 500000; Filling std::multimap: 360000 ticks Filling MyMumap: 530000 ticks Reading std::multimap: 70000 ticks (0) Reading MyMumap: 30000 ticks (0) Or in the "bad" case: const uint32_t num_partitions = 100000; const size_t num_elements = 200000; Filling std::multimap: 100000 ticks Filling MyMumap: 240000 ticks Reading std::multimap: 30000 ticks (0) Reading MyMumap: 10000 ticks (0) Thus reading is unconditionally faster, but filling is also way slower.

A map of vectors comes with the memory overhead for the capacity of each vector. Std::vector typically allocates space for more elements than you actually have. It may not be a big deal for your application, but it's another tradeoff you haven't considered.

If you're doing a lot of reads, then the O(1) lookup time of unordered_multimap might be a better choice. If you have a reasonably modern compiler (and given the presence of the auto keyword, you do) then in general you're going to have a difficult time beating the standard containers in terms of performance and reliability. The people who wrote them are experts.

I would always start with the standard container that most easily expresses what you want to do. Profile your code early and often, and if it's not running fast enough, then look for ways to improve it (e.g. , using the unordered_ containers when doing mostly reads). So, to answer your original question, if you need an associative array of values where those values won't be unique, then using std::multimap definitely makes sense.

Yes, using unordered_ type containers would most likely be the biggest possible improvement, because we hardly ever use the ordering we get by the ordered containers. However I am not sure if these containers are available with the STL version we are using, yet. – LiKao Dec 1 '11 at 15:31 @LiKao, you might have them in the std::tr1 namespace if your compiler supplies it.

– Kristo Dec 1 '11 at 15:49.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.