How is the C++ multimap container implemented?

c++ multimap
user656925 picture user656925 · Jun 6, 2011 · Viewed 14k times · Source

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?

Answer

Magnus Hoff picture Magnus Hoff · Jun 6, 2011

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.

Related questions

What's the difference between std::multimap<key, value> and std::map<key, std::set<value> >

I found that they have one key and multiple values which is unique.

Read More
stl::multimap - how do i get groups of data?

Multimap essentially has groups of data sorted by the key. I want a method by which I could access these individual groups and get their aggregate values. For example, in a std::multimap< string, int > I store {"Group1", 1}, {"…

Read More
How can I get all the unique keys in a multimap

I have a multimap and I want get all the unique keys in it to be stored in a vector. multimap<char,int> mymm; multimap<char,int>::iterator it; char c; mymm.insert(pair<char,…

Read More