Блог

Главная - Вопросы по программированию - какова базовая структура данных списка, вектора и набора STL?

какова базовая структура данных списка, вектора и набора STL?

#c #list #stl #vector #set

#c #Список #stl #вектор #набор

Вопрос:

какова базовая структура данных списка, вектора и набора STL?

Мое решение:

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

Верно?

Комментарии:

1. Реализация определена, но, как правило, std::vector представляет собой динамически распределяемый массив. std::list это двусвязный список (C 11 представляет std::forward_list собой односвязный список), а a set обычно основан на красно-черных деревьях , хотя все, что соответствует амортизированной сложности и требованиям к поведению интерфейсов, определенных в стандарте, являются приемлемыми реализациями.

Ответ №1:

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

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

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

Set = Красное/Черное дерево (сбалансированное бинарное дерево поиска)

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

Комментарии:

1. Обычно это верно, но обратите внимание, что это не единственный вариант (он зависит от реализации).

2. @sgusc , map — красно-черное дерево, set — нет, потому что элементы в нем не отсортированы. В чем разница между списком и связанным списком? какова структура данных «связанного списка»? список?

3. Это зависит от реализации, но сложность, которую требует стандарт, оставляет мало возможностей для кардинально меняющихся реализаций.

4. @user1002288 — std::set имеет требования к порядку. C 11 этого std::unordered_set не делает. Двусвязный список — это группа узлов, которые имеют ссылки на узел перед ним и после него (или NULL ).

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

Ответ №2:

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

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

Метки: