История изменений

Структура данных не поддерживает операции «следующий» (в порядке сортировки) и «предыдущий», поэтому её можно заменить хэш-таблицей. Будет быстрее. По памяти — тоже можно лучше (sparse_hash_map (вот это действительно от Google) имеет оверхед в 4 бита на элемент).

Амортизированное время вставки/удаления/поиска O(\log N)

Это враньё. Для поиска нет никакого амортизированного времени, потому что искать можно либо один и тот же, либо разные, элементы. Если искать один и тот же, то время на M поисков в худшем случае будет O(M (\log N)^2).

Для удаления нужно сначала найти, т.е. тоже O((\log N)^2). Можно возразить, что, мол, один раз удалённый нельзя ещё раз удалить, но дело в том, что там есть элементы (не один элемент!), которые искать сложнее, чем за логарифм. Если в нужном порядке удалять такие элементы, мы снова получаем O(M (\log N)^2) на M удалений в худшем случае.

Если используется как set, а не multiset, то для вставки тоже нужно сначала найти (чтобы не вставить вторую копию).

Прибавьте к этому постоянные затыки у branch predictor’а и prefetcher'а с бинарным поиском.

Массивы под капотом: данные лежат рядом, что улучшает кэшируемость процессором и скорость обхода/доступа к данным

Так ты ж по ним бинарный поиск делаешь, дядя! Какая кэшируемость? Какая скорость обхода/доступа?

---

Зачем оно нужно? Оно хуже, чем хэш-таблица, оно хуже, чем RB trees, AVL trees, B-trees, и так далее. И в теории, и на практике.

Структура данных не поддерживает операции «следующий» и «предыдущий», поэтому её можно заменить хэш-таблицей. Будет быстрее. По памяти — тоже можно лучше (sparse_hash_map (вот это действительно от Google) имеет оверхед в 4 бита на элемент).

Амортизированное время вставки/удаления/поиска O(\log N)

Это враньё. Для поиска нет никакого амортизированного времени, потому что искать можно либо один и тот же, либо разные, элементы. Если искать один и тот же, то время на M поисков в худшем случае будет O(M (\log N)^2).

Для удаления нужно сначала найти, т.е. тоже O((\log N)^2). Можно возразить, что, мол, один раз удалённый нельзя ещё раз удалить, но дело в том, что там есть элементы (не один элемент!), которые искать сложнее, чем за логарифм. Если в нужном порядке удалять такие элементы, мы снова получаем O(M (\log N)^2) на M удалений в худшем случае.

Если используется как set, а не multiset, то для вставки тоже нужно сначала найти (чтобы не вставить вторую копию).

Прибавьте к этому постоянные затыки у branch predictor’а и prefetcher'а с бинарным поиском.

Массивы под капотом: данные лежат рядом, что улучшает кэшируемость процессором и скорость обхода/доступа к данным

Так ты ж по ним бинарный поиск делаешь, дядя! Какая кэшируемость? Какая скорость обхода/доступа?

---

Зачем оно нужно? Оно хуже, чем хэш-таблица, оно хуже, чем RB trees, AVL trees, B-trees, и так далее. И в теории, и на практике.