Does Each Element of a multimap Contain Both the K

问题:

I can't imagine this hasn't been asked, but I'm not having any luck finding it.

Does each element of a multimap contain its value and its key?

That is does the internal structure of a multimap look like more like this:

map<key, vector<value>>

Or more like this:

vector<pair<key, value>>

回答1:

Each element contains both its key and value.

You can tell because iteration returns a stable non-allocating reference to std::pair<Key const, Value>.

What more, Keys can compare equal but be different. A multimap permits you to store "extra data" in that Key that isn't part of the ordering, and you'll get it back afterwards and it will be associated with that Value.

Implementing a multimap as a std::map<Key, std::vector<Value>> is an option that is sometimes better than using a std::multimap<Key,Value>. Especially with many-values per key, it will be more memory efficient, have better locality, etc. Iterating over it can be trickier if you want to do so uniformly, but if you want to iterate over things clumped by key it is easier.