How sets,multisets,maps and multimaps works internally

Question

Hello, I have few questions regarding this topic. How does multiset works? I mean if set cant have value mapped to a key and it only holds keys? Also how all of these associative containers works? I mean vector and deque in the memory is hold sequentially it means that deleting/removing(except beggining(deque) and end(vector,deque) is slow if they are large. And list is a set of pointers which is not sequentially hold in the memory which causes longer search but faster delete/remove. So how does set,map,multiset and multimap are stored and works? Thank you in advance!

Answer 1

There can be any implementation, as long as they match the standard specifications for those containers.

AFAIK, the associative containers are implemented as binary trees (red-black). More details... depending on the implementation.

Answer 2

There is a very good document which describes which container to use in which case. Follow this link. The table in there is most valuable. Print it and attach it to your favorite C++ book.

Answer 3

These 4 containers are typically all implemented using "nodes". A node is an object that stores one element. In the [multi]set case, the element is just the value; in the [multi]map case each node stores one key and its associated value. A node also stores multiple pointers to other nodes. Unlike a list, the nodes in sets and maps form a tree. You'd typically arrange it such that branches on the "left" of a certain node have values less than that node, while branches on the "right" of a certain node have values higher than that node.

Operations like finding a map key/set value are now quite fast. Start at the root node of the tree. If that matches, you're done. If the root is larger, search in the left branch. If the root is smaller than the value you're looking for, follow the pointer to the right branch. Repeat until you find a value or an empty branch.

Inserting an element is done by creating a new node, finding the location in the tree where it should be placed, and then inserting the node there by adjusting the pointers around it. Finally, there is a "rebalancing" operation to prevent your tree from ending up all out of balance. Ideally each right and left branch is about the same size. Rebalancing works by shifting some nodes from the left to the right or vice versa. E.g. if you have values {1 2 3} and your root node would be 1, you'd have 2 and 3 on the left branch and an empty right branch:

1
 \
  2
   \
    3

This is rebalanced by picking 2 as the new root node:

  2
 / \
1   3

The STL containers use a smarter, faster rebalancing technique but that level of detail should not matter. It's not even specified in the standard which better technique should be used so implementations can differ.

Answer 4

Good resource on that subject is Introduction to Algorithms. It is quite comprehensive in my opinion.