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

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

Восстановить пароль Регистрация
 
Tiva
94 / 94 / 1
Регистрация: 25.04.2012
Сообщений: 429
26.12.2012, 10:20     контейнеры STL и виды деревьев #1
подскажите, или покажите где есть эта информация
например я знаю, что контейнеры 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 и виды деревьев
Посмотрите здесь:

C++ Массив: Учащиеся участвовали в посадке деревьев. Сколько деревьев было посажено
C++ STL, контейнеры классы
Ассоциативные контейнеры STL C++
Контейнеры STL C++
STL: контейнеры. Произвольная вставка элементов C++
C++ Как сохранить контейнеры STL в файл. И как потом их прочитать из файла
C++ STL. Итераторы и последовательные контейнеры
Контейнеры Stl, экзамен C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
26.12.2012, 12:00     контейнеры STL и виды деревьев #2
Вектор реализован с помощью динамического массива, а никак не с помощью дерева.
rangerx
1908 / 1517 / 139
Регистрация: 31.05.2009
Сообщений: 2,876
26.12.2012, 16:10     контейнеры STL и виды деревьев #3
vector и string - динамические массивы
list- двусвязный список
Yandex
Объявления
26.12.2012, 16:10     контейнеры STL и виды деревьев
Ответ Создать тему
Опции темы

Текущее время: 13:24. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru