что лежит в основе структуры данных списка STL, вектора и набора?

Question

Что лежит в основе структуры данных списка STL, вектора и набора?

Мое решение:

• vector: (динамически выделенный) массив
• список:?
• set: куча (или двоичное дерево со всемилистовые узлы расположены как можно левее и держат элемент min / max сверху)

Справа?

Answer 1

На основании комментариев, чтобы уточнить, это наиболее распространенные варианты, но в зависимости от желаемой сложности и других факторов, поддержка этих реализаций может варьироваться:

Вектор = динамическое изменение размерамассив

список = двусвязный список

набор = красное / черное дерево (сбалансированное дерево двоичного поиска)

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

Answer 2

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

Тем не менее, std::vector - это обычно динамический массив , std::list - это, вероятно, двусвязный список , а std::set чаще всего является своего рода самобалансирующееся двоичное дерево .