How is the C++ multimap container implemented?

Question

The C++ standard does not define how the standard containers should be implemented, it only gives certain constraints like the one you say for vectors.

multimaps have certain runtime complexity (O(lg n) for the interesting operations) and other guarantees, and can be implemented as red-black trees. This is how they are implemented in the GNU standard C++ library.

Very often, a red-black tree. See e.g. STL's Red-Black Trees from Dr. Dobb's.

Addition to the "preferred" answer, because SO won't let me comment:

Given a key with values B, C, D, the behavior of iterators is a lot easier to implement if each element has it's own node. Find() is defined to return the first result in the series, and subsequent iteration takes you across the remaining elements. The de facto difference between a map and a multimap is that multimap is sorted using < over the entire value_type, where the map use < over only the key_type

Correction: the C++11 standard is explicit that new (key, mapping) pairs are inserted at the end of any existing values having the same key. This raises a question I hadn't considered: can a multimap contain two nodes in which both the key and the mapped target are the same. The standard doesn't seem to take a clear position on this, but it's noteworthy that no comparison operator is required on the mapped type. If you write a test program, you will find that a multimap can map X to 1, 2, 1. That is: "1" can appear multiple times as a target and the two instances will not be merged. For some algorithms that's a deficiency.

This article from Dr. Dobbs talks about the underlying rb-tree implementation that is commonly used. The main point to note is that the re-balance operation actually doesn't care about the keys at all, which is why you can build an rb-tree that admits duplicated keys.