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

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

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

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

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

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

Контейнеры STL - C++
Кто знает где найти информацию по поводу стандартных контейнеров STL? Интересует не то, как их применять, а основы реализации. Может быть...

STL, контейнеры классы - C++
Ребят, помогите кто чем сможет, а то уже мозг не варит за целый день, в общем, вот задание: Первый контейнер - Вектор, Второй - Стэк, Тип...

Контейнеры Stl, экзамен - C++
Очень прошу помочь на экзамене! Написать программу: в контейнере имеется некоторый набор чисел, скопировать элементы, которые встречаются...

Ассоциативные контейнеры STL - C++
Везде сказано: set - упорядоченное множество уникальных элементов. (есть куча примеров и уроков) multiset - то же что и set, но...

Начала STL и контейнеры C++ - C++
Вот такой вот простенький текст предлагается "Начала STL и контейнеры C++". Скачать свободно можете здесь - и короткие главки (их 21 на...

Начала STL и контейнеры C++ - C++
Многие улучшения, сделанные из C в C++ вызывают сомнения и вопросы... Именно поэтому, наверное, при любви к C++ вузовских пЫдагогов, в...

2
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
26.12.2012, 12:00 #2
Вектор реализован с помощью динамического массива, а никак не с помощью дерева.
0
rangerx
1935 / 1544 / 141
Регистрация: 31.05.2009
Сообщений: 2,913
26.12.2012, 16:10 #3
vector и string - динамические массивы
list- двусвязный список
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.12.2012, 16:10
Привет! Вот еще темы с ответами:

STL. Итераторы и последовательные контейнеры - C++
Немогу решить эти задачки: 1 Написать экземпляр класса queue на основе элементов типа string. 2.Написаты программу, которая использует...

STL: контейнеры. Произвольная вставка элементов - C++
Доброго времени суток! Можно ли вставить элемент в контейнер STL (не важно какой) в произвольное место? Имеется в виду, в случаи...

Использование указателей на контейнеры STL в заголовочных файлах - C++
Для использования указателей на I/O классы достаточно включить <iosfwd> который содержит опережающие объявления и таким образом появляется...

Можно ли добавлять статические объекты классов в STL контейнеры? - C++
Или обязательно добавлять ссылки на них в контейнер? Нигде не могу найти ответа.


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

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