multimap的每个元素是否包含键与值？其内部结构是哪种？

Great question! Let's break this down clearly for you:

Do multimap elements contain both key and value? #

Absolutely. Every element in a multimap is a pair<const Key, T>—exactly the same element type as a regular map. The only difference between map and multimap is that map enforces unique keys, while multimap allows duplicate keys to coexist. So each entry in the multimap is a standalone key-value pair, no exceptions.

Is its internal structure closer to map<key, vector<value>> or vector<pair<key, value>>? #

First, it's worth noting that the C++ standard doesn't mandate a specific implementation for multimap, but all major STL implementations (like libstdc++, libc++, and MSVC's STL) use a balanced binary search tree (typically a red-black tree) under the hood.

With that context:

• It is not similar to map<key, vector<value>>. That structure would group all values for a single key into a single vector stored in one tree node. In contrast, multimap stores every key-value pair as a separate tree node—duplicate keys just mean multiple nodes with the same key value, arranged consecutively in the tree's ordered structure.
• Its logical behavior is far closer to an ordered vector<pair<key, value>>. When you iterate through a multimap, elements are sorted by key, and all entries with the same key appear consecutively—just like a sorted vector of pairs. The key difference is performance: the tree structure gives multimap O(log n) time complexity for insertions, deletions, and lookups, whereas a vector would have O(n) complexity for those operations.

As a quick example: if you insert three entries {1, "a"}, {1, "b"}, {2, "c"} into a multimap, the internal structure will have three separate nodes, each holding one of those pairs, ordered by key. When you call equal_range(1), you'll get an iterator range pointing directly to the first two nodes—no need to unpack a nested vector.

内容的提问来源于stack exchange，提问作者Jonathan Mee