Take the 2-minute tour ×

For example a C++ vector is implemented using a dynamic array where each element uses consecutive memory spaces.

I know that a C++ multimap is a one to many relationship but what is the internal structure?

share|improve this question

2 Answers 2

up vote 13 down vote accepted

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.

share|improve this answer
And also Dinkumware's STL, and therefore almost every commercial C++ compiler's standard library, including VC. –  Simon Buchan Jun 6 '11 at 21:51
What about the elements. Suppose Key A has B,C,D,E. Are these elements searchable or are they clumped together as a node in the Tree –  user656925 Jun 6 '11 at 23:13
@Chris: I haven't given it much thought, but I think B, C, D and E could either be clumped on one node or represented as individual nodes. I don't know what you mean by "searchable", though. You can iterate over them, but since they have the same key you can not choose one of them directly (by any property of the value). A multimap only offers lookup by key. –  Magnus Hoff Jun 7 '11 at 8:06
@Chris: I recently had a look at GCC's implementation, and found that elements with the same key were in separate nodes. I don't think there's any reason why other implementations might not choose to cluster them, though. –  Mike Seymour Jun 7 '11 at 10:34
@MikeSeymour: It's tricky to implement an iterator that dereferences to references of key/value pairs unless each node has it's own key. This also explains lower_bound/upper_bound. –  Mooing Duck Dec 17 '11 at 1:41

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

share|improve this answer
+1 if you'd emphasised [and explained] "very often" a bit more. There's clearly a misunderstanding to be rectified in this question! –  Lightness Races in Orbit Jun 6 '11 at 22:27
@Tomalak: Not sure I follow? I hesitate to say "always" (if that's what you're hinting at), because the standard doesn't mandate it, and I don't know of all STL implementations! –  Oli Charlesworth Jun 6 '11 at 22:37
No no, exactly. The OP doesn't seem to realise that this is not a standard-mandated thing. I just feel that your answer could make more of that (like Magnus's did). :) (And, ahem, cough stdlib!) –  Lightness Races in Orbit Jun 6 '11 at 22:47
@Tomalak: Ah, I see! Good point. Well, I won't steal Magnus' thunder... –  Oli Charlesworth Jun 6 '11 at 22:48
Fair enough; it would probably be largely pointless attempting to steal thunder from someone who sounds like he might be Thor's secret identity :P –  Lightness Races in Orbit Jun 6 '11 at 22:49

Your Answer

