Сложность set:: insert

Я прочитал, что операция вставки в наборе занимает только log (n). Как это возможно?

Чтобы вставить, сначала мы найдем местоположение в отсортированном массиве, где должен сидеть новый элемент. Используя двоичный поиск, требуется log (n). Затем, чтобы вставить в это место, все последующие элементы должны быть сдвинуты на одно место вправо. Это занимает еще n времени.

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

Ответы

Ответ 1

std::set обычно реализуется как дерево с красным черным двоичным поиском. Вставка в эту структуру данных имеет худший вариант сложности O (log (n)), так как дерево поддерживается сбалансированным.

Ответ 2

HashSet, LinkedHashSet и EnumSet постоянная стоимость операций add(), remove() и содержит() O (1), время из-за внутренней реализации HashMap.

Для древовидной структуры TreeMap и ConcurrentSkipListMap время операций put(), get(), remove(), containsKey() равно O (log (n)).

поэтому TreeSet имеет O (log (n)) сложность времени.