Как наборы, мультимножества, карты и мультикарты работают внутренне
32-разрядные целые числа являются способом пойти - пока Вы не начинаете иметь дело с 128-разрядными адресами IPv6.
2 ответа
Эти 4 контейнера обычно реализуются с использованием «узлов». Узел - это объект, в котором хранится один элемент. В случае [multi] set элемент - это просто значение; в случае [мульти] карты каждый узел хранит один ключ и связанное с ним значение. Узел также хранит несколько указателей на другие узлы. В отличие от списка, узлы в наборах и картах образуют дерево. Обычно вы располагаете его так, чтобы ветви слева от определенного узла имели значения меньше, чем этот узел, а ветви справа от определенного узла имели значения выше, чем этот узел.
Такие операции, как поиск ключа / заданного значения карты, теперь выполняются довольно быстро. Начните с корневого узла дерева. Если это совпадает, все готово. Если корень больше, ищите в левой ветви. Если корень меньше искомого значения, следуйте указателю на правую ветку. Повторяйте до тех пор, пока не найдете значение или пустую ветвь.
Вставка элемента выполняется путем создания нового узла, нахождения места в дереве, где он должен быть размещен, а затем вставки туда узла путем корректировки указателей вокруг него. Наконец, есть операция "ребалансировки", чтобы предотвратить полное нарушение баланса вашего дерева. В идеале каждая правая и левая ветка примерно одинакового размера. Ребалансировка работает путем смещения некоторых узлов слева направо или наоборот. Например, если у вас есть значения {1 2 3} и ваш корневой узел будет 1, у вас будут 2 и 3 в левой ветви и пустая правая ветвь:
1
\
2
\
3
Это перебалансируется путем выбора 2 в качестве нового корневого узла:
2
/ \
1 3
Контейнеры STL используют более умную и быструю технику перебалансировки, но такой уровень детализации не имеет значения. Это'
. Может быть любая реализация, если они соответствуют стандартным спецификациям для эти контейнеры.
AFAIK, ассоциативные контейнеры реализованы как двоичные деревья (красно-черные). Подробнее ... в зависимости от реализации.