Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Tiva
94 / 94 / 1
Регистрация: 25.04.2012
Сообщений: 429
#1

Контейнеры STL и виды деревьев - C++

26.12.2012, 10:20. Просмотров 1041. Ответов 2
Метки нет (Все метки)

подскажите, или покажите где есть эта информация
например я знаю, что контейнеры map и set реализованы через красно-черное дерево
через "какие" деревья\другие структуры данных реализованы остальные контейнеры? vector, string, list, etc
и по каким причинам(от деревьев и их "родных" структур данных) один контейнер лучше другого по каким-либо параметрам.
Векторы являются неэффективными для вставки элементов в любые места, кроме конца.
Такая операция имеет О(n) (см. O-нотация) сложность по сравнению с O(1) для связанных списков.
Это компенсируется скоростью доступа и скоростью удаления.
Доступ к произвольному элементу вектора имеет сложность O(1) по сравнению с О(n) для связанного
списка и O(log n) для дерева. Удаление имеет сложность O(2) (перестановка и удаление).
вот я так понимаю, эти плюсы и минусы вектора, основаны на том, на каком дереве он реализован?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.12.2012, 10:20     Контейнеры STL и виды деревьев
Посмотрите здесь:
Контейнеры STL C++
Начала STL и контейнеры C++ C++
Начала STL и контейнеры C++ C++
Контейнеры Stl, экзамен C++
Ассоциативные контейнеры STL C++
C++ STL, контейнеры классы
C++ STL. Итераторы и последовательные контейнеры
STL: контейнеры. Произвольная вставка элементов C++
Использование указателей на контейнеры STL в заголовочных файлах C++
Можно ли добавлять статические объекты классов в STL контейнеры? C++
C++ Как stl контейнеры работают с объектами различных типов данных?
C++ Как сохранить контейнеры STL в файл. И как потом их прочитать из файла

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
26.12.2012, 12:00     Контейнеры STL и виды деревьев #2
Вектор реализован с помощью динамического массива, а никак не с помощью дерева.
rangerx
1932 / 1541 / 141
Регистрация: 31.05.2009
Сообщений: 2,911
26.12.2012, 16:10     Контейнеры STL и виды деревьев #3
vector и string - динамические массивы
list- двусвязный список
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru