How does std::multimap store its elements?

Question

Possible Duplicate:
How is a C++ multimap implemented?

Multimaps are typically implemented as binary search trees.

But what is their typical internal representation? Is it like std::map<Key, std::list<Value> > or similar? My concern is complexity of insertion and iteration over a set of elements with the same key.

That is an implementation detail, not specified by the standard. As such, it would be good to know why you want to know this in order to be able to give a helpful answer. What do you hope to achieve? — Magnus Hoff, Jan 29 '13 at 10:41
don't listen to Cplusplus.com: http://stackroulette.com/programmers/88241/whats-wrong-with-cplusplus-com ! — SirDarius, Jan 29 '13 at 10:41
An implementation using `std::set` would not allow for duplicate values. Also, the ordering of values wit the same key has been made more restricted in C++11, see [here](http://en.cppreference.com/w/cpp/container/multimap). — juanchopanza, Jan 29 '13 at 10:46
also check this answer:http://stackoverflow.com/a/6258434/134713 — Vijay, Jan 29 '13 at 10:52
A typical solution (e.g. employed by libstdc++) is to have a single red-black tree structure, and use that for sets, multisets, maps and multimaps. For the multi-versions, you just need to modify a small amount of the logic, and the heart of the binary search tree logic can be reused. — Kerrek SB, Jan 29 '13 at 10:57
@SirDarius I'm not going to protect cplusplus.com, but many problems described from the link you gave was revised (maybe thanks to that question and answers at SO) — borisbn, Jan 29 '13 at 11:02
Isn't one of the beauties of OOP not having to worry about that stuff? — ChiefTwoPencils, Jan 29 '13 at 11:06
@borisbn good thing, however I think people need to be aware of the fact that cplusplus.com is not the 'official' C++ reference, as a google search would tend to imply — SirDarius, Jan 29 '13 at 11:13
@C.Lang That has nothing to do with OOP. In C, it's not too hard to program a multimap while hiding the implementation from the client; the hard part is making it generic, but generic programming != OOP. — Fred Foo, Jan 29 '13 at 11:53
@larsmans: Hmm, a short intro to a chapt. on OOP in my data structures book says, "Typically one programming team designs and implements a class, while other programmers use the class. Programmers that *use* the class have no knowledge of *how* the class is implemented. It further summarizes the paragraph with "emphasize what work is done rather than how the work is done". This theme carries throughout, so am I just bleeding design fundamentals with OOP? Objects are instances of classes. — ChiefTwoPencils, Jan 29 '13 at 18:48
@C.Lang: as I was taught OOP, but maybe it's just one particular definition, it refers to the combination of encapsulation and inheritance, and when either of those two is missing, there's no OOP. — Fred Foo, Jan 30 '13 at 00:41

score 1 · Answer 1 · answered Jan 29 '13 at 12:17

If you want to know the complexity of specific operations, you need look no further than to the standard. The standard has guarantees on the complexity, but implementations are free to satisfy those guarantees any way they wish.

For insertion the complexity is O(lg n), unless you specify an optimal hint every time, in which case the complexity is O(1) amortized. (See details here: http://en.cppreference.com/w/cpp/container/multimap/insert)

For iteration over a set of elements with the same key, the complexity is the same as iteration from any iterator to another. Given that you have already found the iterators, the iteration is linear in the count of items you are iterating over. (Sorry, unable to find a reference for this right now)

How does std::multimap store its elements?

1 Answers1