Разве любая реализация stl :: set не использует красно-чёрное дерево?
Кто-нибудь видел реализацию STL, где stl :: set не реализован как красно-черное дерево?
Причина, по которой я спрашиваю, состоит в том, что в моих экспериментах деревья B-2B превосходят stl :: set (и другие реализации красно-черного дерева) в 2-4 раза в зависимости от значения B. Мне любопытно, если есть веская причина использовать красно-черные деревья, когда кажется, что структуры данных быстрее.
Решение
Некоторые люди в Google на самом деле построили Реализация контейнеров стандартной библиотеки C ++ на основе B-дерева. Похоже, они имеют гораздо лучшую производительность, чем стандартные реализации двоичного дерева.
Однако есть одна загвоздка. Стандарт C ++ гарантирует, что удаление элемента из карты или набора делает недействительными только другие итераторы, указывающие на тот же элемент в карте или наборе. В реализации на основе B-дерева из-за разбиения и объединения узлов функции-члены стирания в этих новых структурах могут сделать недействительными итераторы для других элементов в дереве. В результате эти реализации не являются идеальной заменой стандартным реализациям и не могут быть использованы в соответствующей реализации.
Надеюсь это поможет!
Другие решения
Есть хотя бы одна реализация основанный на деревьях AVL вместо красно-черных деревьев.
Я не пытался проверить соответствие этой реализации, но, по крайней мере (в отличие от реализации на основе B-дерева), это как минимум мог быть написано, чтобы идеально соответствовать требованиям стандарта.