std::set и, грубо говоря, дерево бинарного поиска. Погуглив и покопавшись в исходниках пришел к выводу, что std::set реализован на основе красно-черного дерева, которое в принципе считается более шустрым, чем ДБП.
Начал делать сравнения и замеры. Сравнивал вставку int, string, object (по 100, 1000, 10000).
И не понимаю одного..
Почему при вставке int std::set работает НАМНОГО медленнее ДБП? Можете пожалуйста подсказать, кто знает? Ну или указать путь к тем, кто знает.. А то никак не могу вывод сделать и объяснить причину сего прикола.
У вас немного в терминологии проблема. Кчд это тоже дбп. Почему сортированный вектор дбп тож не оч понятно.
Сортированный вектор это просто название, на деле это просто класс Внутри которого только дбп)
Ну поиск за logN, значит дбп )
bst не даёт таких гарантий кажется
Вот, что за SORTED_VECTOR https://pastebin.com/yUv4PbD3
так а сортированный вектор то к bst каким боком?
Сбалансированное только.
дерево из одной длинной ветки это тоже bst
А при бинарном поиске при вставке ты память выделял?
Обсуждают сегодня