Как наборы, мультимножества, карты и мультикарты работают внутри

Question

Как работают мультимножества? Если набор не может иметь значение, сопоставленное с ключом, он содержит только ключи?

Кроме того, как работают ассоциативные контейнеры? Я имею в виду, что вектор и deque в памяти расположены последовательно, это означает, что удаление / удаление (за исключением начала [deque] и конца [vector, deque]) происходит медленно, если они большие.

И список - это набор указателей, которые не располагаются последовательно в памяти, что приводит к более длительному поиску, но ускоряет удаление / удаление.

Как хранятся наборы, карты, мультимножества и мультикарты и как они работают?

Answer 1

Эти 4 контейнера, как правило, все реализованы с использованием "узлов". Узел - это объект, который хранит один элемент. В случае [multi] set элемент является просто значением; в случае [multi] map каждый узел хранит один ключ и соответствующее ему значение. Узел также хранит несколько указателей на другие узлы. В отличие от списка, узлы в наборах и картах образуют дерево. Обычно вы располагаете его так, чтобы ветви слева от определенного узла имели значения меньше этого узла, а ветви справа от определенного узла имели значения выше этого узла.

Операции, такие как поиск ключа / заданного значения карты, теперь выполняются довольно быстро. Начните с корневого узла дерева. Если это соответствует, вы сделали. Если корень больше, ищите в левой ветке. Если корень меньше, чем искомое значение, следуйте указателю на правую ветвь. Повторяйте, пока не найдете значение или пустую ветвь.

Вставка элемента выполняется путем создания нового узла, поиска местоположения в дереве, в котором он должен быть размещен, а затем вставки узла в него путем корректировки указателей вокруг него. Наконец, есть операция «перебалансировки», чтобы предотвратить потерю баланса вашего дерева. В идеале каждая правая и левая ветви имеют примерно одинаковый размер. Изменение баланса работает путем смещения некоторых узлов слева направо или наоборот. Например. если у вас есть значения {1 2 3} и ваш корневой узел будет 1, у вас будет 2 и 3 в левой ветви и пустая правая ветвь:

1
 \
  2
   \
    3

Это сбалансировано путем выбора 2 в качестве нового корневого узла:

  2
 / \
1   3

Контейнеры STL используют более умную и быструю методику восстановления баланса, но этот уровень детализации не должен иметь значения. В стандарте даже не указано, какую лучшую технику следует использовать, чтобы реализации могли отличаться.

Answer 2

Все ассоциированные классы контейнеров (map, multi-map, set, multi-set) реализованы с помощью дерева Red and Black (R-B Tree) Таким образом, реализация дерева R-B может быть похожа на это: -

struct Rb_node {
    int value;
    struct node *left, *right;
    int color;
    int size;
};

Answer 3

Может быть любая реализация, если они соответствуют стандартным спецификациям для этих контейнеров.

AFAIK, ассоциативные контейнеры реализованы в виде бинарных деревьев (красно-черные). Подробнее ... в зависимости от реализации.