BST реализации в STL

Question

C ++ STL "set" и "map" поддерживают логарифмическое время наихудшего случая для вставки, стереть и найти операции. Следовательно, базовая реализация Двоичное дерево поиска. Важным вопросом при реализации набора и карты является обеспечение поддержки класса итератора. Конечно, внутренне Итератор поддерживает указатель на «текущий» узел в итераторе. Трудная точка эффективно продвигается к следующему узлу.

Мой вопрос

1. если "set" и "map" реализуют двоичное дерево поиска, как мы продвигаемся к следующему узлу, используя класс итератора, т. Е. Что мы возвращаем ++ или - т.е. это левое поддерево или правое поддерево?

2. В целом, как реализовано большинство реализаций STL BST и как реализован ++ или - итератор?

спасибо!

Answer 1

1. В спецификации C ++ нет ничего, что требует использования двоичного дерева. Из-за этого ++ и - определены в терминах последовательности элементов. map и set хранят последовательность упорядоченных элементов. Поэтому ++ перейдет к следующему элементу, а - перейдет к предыдущему элементу. Следующие и предыдущие элементы определяются порядком элементов.

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

2. Как правило, они используют некоторые из Красно-черного самобалансирующегося двоичного дерева .

Answer 2

Это в основном зависит от конкретной реализации.Один способ (только мое описание: не обязательно тот, который у вас есть) может быть следующим:

узел имеет 3 указателя: влево , вправо и до один.++ делает:

• если есть «право», идите направо, затем идите как можно глубже влево.
• В противном случае поднимайтесь вверх, пока мы не придем справа, и вверхеще раз.

что -- делает его в точности наоборот.

Answer 3

Помимо наихудших операционных сложностей, и map & set (и все ассоциативные контейнеры Orderer / Sorted в стандартной библиотеке C ++) обладают очень важным свойством: их элементы всегда сортируются в порядке по ключу (согласно компаратору).
Самобалансирующееся дерево бинарного поиска удовлетворяет сложностям работы, и единственный обход, который даст вам элементы в отсортированном порядке, это, как вы уже догадались, в порядке единица.
NicolОтвет Боласа дает вам более подробную информацию об обычной реализации.Если вам интересно увидеть такую ​​реализацию, вы можете взглянуть на реализацию RDE STL .Это намного легче читать, чем то, что вы найдете в своей обычной реализации стандартной библиотеки C ++.В качестве примечания, обе реализации set и map в RDESTL имеют только прямой итератор (не двунаправленный, как гласит стандарт), но разобраться с частью - довольно просто.