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:

• 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 != end && it2->first == it1->first; ++it2)
  {
    // equal key value (`== it1->first`) at this level
  }
}