How is the C++ multimap container implemented?

Question

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 1

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.

Answer 2

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

Answer 3

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.

Answer 4

The multimap just like it's simpler version i.e the std::map, is mostly built using red black trees. C++ standard itself does not specify the implementation. But in most of the cases ( I personally checked SGI STL) red black trees are used. Red Black trees are height balanced trees and hence fetch / read operation on them is always guaranteed to be O(log(n)) time. But if you are wondering on how values of the key are stored. each key->pair is saved as a separate node in the red black tree ( Even though the same key might appear multiple times just like in the case of key 'b' below). Key is used to lookup/ search the rb-tree. Once the key is found, it's value stored in the node is returned.

  std::multimap<char,int> mmp;

  mmp.insert(std::pair<char,int>('a',10));
  mmp.insert(std::pair<char,int>('b',20));
  mmp.insert(std::pair<char,int>('b',10));
  mmp.insert(std::pair<char,int>('b',15));
  mmp.insert(std::pair<char,int>('b',20));
  mmp.insert(std::pair<char,int>('c',25));
  mmp.insert(std::pair<char,int>('a',15));
  mmp.insert(std::pair<char,int>('a',7));


for (std::multimap<char,int>::iterator it=mmp.begin(); it!=mmp.end(); ++it){

    std::cout << (*it).first << " => "  << (*it).second << " . Address of (*it).second = " << &((*it).second) << '\n';
}

Output :

a => 10 . Address of (*it).second = 0x96cca24
a => 15 . Address of (*it).second = 0x96ccae4
a => 7 . Address of (*it).second = 0x96ccb04
b => 20 . Address of (*it).second = 0x96cca44
b => 10 . Address of (*it).second = 0x96cca64
b => 15 . Address of (*it).second = 0x96cca84
b => 20 . Address of (*it).second = 0x96ccaa4
c => 25 . Address of (*it).second = 0x96ccac4

Initially I thought the values of a single key like 'b' might be stored in a std::vector .

template <class K, class V>
struct Node {
  K key;
  std::vector<V> values; 
  struct Node* left;
  struct Node* right;
}

But later I realized that would violate the guaranteed fetch time of O(log(n)). Moreover, printing out the addresses of the values confirms that values with a common key are not contiguous.

They keys are inserted using operator<, so values with the same keys are stored in the order in which they are inserted.

So if we insert first (key = 'b', value = 20) and then (key = 'b', value = 10) The insertion is done using operator< , since the second 'b' is NOT lesser than the first inserted 'b', it is inserted in the 'right branch of a binary tree'.

The compiler I have used is gcc-5.1 ( C++14).