How do multimaps internally handle duplicate keys?

Question

With maps, I can understand it being implemented as a binary search tree (a red/black tree, for example) and the time complexity of it.

But with multimaps, how are key collisions handled internally? Is it that a list is maintained for all the nodes with same keys? Or some other handling is undertaken. I came across a situation where I could use either a map<int,vector<strings>> or a multimap<int,string> and would like to know the tradeoffs.

Answer 1

The C++ spec doesn't give a specific implementation for std::multimap, but instead gives requirements on how fast the operations on std::multimap should be and what guarantees should hold on those operations. For example, insert on a multimap needs to insert the key/value pair into the multimap and has to do so in a way that makes it come after all existing entries with the same key. That has to work in time O(log n), and specifically amortized O(1) if the insertion occurs with a hint and the hint is the spot right before where the element should go. With just this information, the multimap could work by having a red/black tree with many nodes, one per key, or it could be an red/black tree storing a vector of values for each key. (This rules out an AVL tree, though, because the rotations involved in an AVL tree insertion don't run in amortized O(1) time. However, it also permits things like 2-3-4 trees or deterministic skiplists).

As we add more requirements, though, certain implementations get ruled out. For example, the erase operation needs to run in amortized constant time if given an iterator to the element to erase. That rules out the use of a single node with a key and a vector of values, but it doesn't rule out a single node with a key and a doubly-linked list of values. The iterator type needs to be able to dereference to a value_type, which needs to match the underlying allocator's value_type. This rules out the possibility that you could have individual nodes in a red/black tree with a single key and a linked list of values, since you couldn't obtain a reference to a value_type that way.

Overall, the restrictions are such that one permissible implementation is a red/black tree with one node per key/value pair, though others may be possible as well. Other ideas - like using an AVL tree, or coalescing values for a given key into a vector or list - aren't possible.

Hope this helps!