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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
ForEveR
В астрале
Эксперт С++
7968 / 4730 / 320
Регистрация: 24.06.2010
Сообщений: 10,539
Завершенные тесты: 3
#1

Tree, set, map etc. - C++

05.03.2011, 01:23. Просмотров 1253. Ответов 2
Метки нет (Все метки)

Решил посмотреть реализацию стандартного мап/сет и вспомогательного класса _Tree (кстати, он только в MSVS или есть везде, но по разному называется и по разному реализован?).

Реализованы они по стандарту как известно через красно-черное сбалансированное бинарное дерево (кстати, сложно-ли такое реализовать впринципе? Просто интересно стало, может надумаю как-нибудь, список и вектор реализован (без проверок почти), надо бы реализовать все).

Но главный вопрос состоит в том как они реализованы? Итеративно или же рекурсией? При самописном дереве - стек переполняется через 3+к элементов. В set/map могу вставить и 2 ляма. Кто-нибудь знает точно как там это реализовано? Ну и + если есть инфа об этом в стандарте - ссылку плиз.

И крайний вопрос - чем определяется глубина раскрутки стека для каждой машины? Вот у меня например дерево держало порядка 3к элементов, у fasked его дерево держало около 20-200к и не падало. Как определить? Оперативка влияет или все вместе взятое?

Заранее спасибо за ответы.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.03.2011, 01:23     Tree, set, map etc.
Посмотрите здесь:

Map/set iterators are incompatible - C++
void Delete(int a , int b) { multiset <double> ::iterator First, Last; multiset <double> ::iterator temp; int i = 0; ...

map/set iterator not dereferencable - C++
map<string,int> optimized(map<string,int>&dict){ map<string,int>::iterator i=dict.begin(); map<string,int>::iterator j=dict.begin(); ...

Map/set!( iterator not dereferencable) - C++
Есть функция,в которой происходит поиск в map по ключу. Если по данному ключу нет значения, то необходимо провести интерполяцию двух...

Map/set iterator not dereferencable - C++
Всем доброго времени суток. Суть задания в том, чтобы удалить повторы комбинаций чисел в multimap'e. Проблема в том, что появляется данная...

Map/set iterator not dereferencable - C++
Есть два класса, первый: class AnimationManager { public: String currentAim; std::map<String, Animation> animList; ...

Expression:map/set incompatible - C++
Подскажите пожалуйста почему происходит ошибка в этом коде: set<int> S; vector<set<int>::iterator> v1; ...

Замена char на map/set - C++
Всем привет! Задача была написать программу, которая выводит слово, которое встречается чаще всего (причем КАПСом) Имеется следующий...

Expression:map/set incompatible - C++
Не могу понять почему возникает ошибка дело в том что данный код работает set<int> Multic; vector<set<int>::iterator> Posledic; ...

Найти такой подмассив, что его сумма максимальна (через контейенры map и set) - C++
Дан массив целых чисел a, состоящий из n элементов. Требуется найти такой его подотрезок, что его сумма максимальна. Входные данные...

Программа аварийно завершается с ошибкой "map/set iterators are incompatible" - C++
Добрый день! Проблема такая: в s1 и s2 рандомно добавляю числа, хочу найти объединение этих множеств. Если использовать такой код, то все в...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alex_x_x
бжни
2445 / 1650 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
05.03.2011, 02:12     Tree, set, map etc. #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от ForEveR Посмотреть сообщение
И крайний вопрос - чем определяется глубина раскрутки стека для каждой машины? Вот у меня например дерево держало порядка 3к элементов, у fasked его дерево держало около 20-200к и не падало. Как определить? Оперативка влияет или все вместе взятое?
кратко говоря: рихтер стек потока
http://wm-help.net/books-online/book/59464/59464-9.html
конечно озу рулит, но от компоновки программы и работы ос зависит не меньше

Цитата Сообщение от ForEveR Посмотреть сообщение
Решил посмотреть реализацию стандартного мап/сет и вспомогательного класса _Tree (кстати, он только в MSVS или есть везде, но по разному называется и по разному реализован?).
не знаю, тоже будет интересно узнать
вон в gcc Red Black tree
/usr/include/c++/4.4.4/bits/stl_tree.h

Bash
1
2
  // Red-black tree class, designed for use in implementing STL
  // associative containers (set, multiset, map, and multimap)
ForEveR
В астрале
Эксперт С++
7968 / 4730 / 320
Регистрация: 24.06.2010
Сообщений: 10,539
Завершенные тесты: 3
05.03.2011, 23:51  [ТС]     Tree, set, map etc. #3
MSVS 2008
Файл xtree.
C++
1
2
3
4
5
        // TEMPLATE CLASS _Tree
template<class _Traits>
    class _Tree
        : public _Tree_val<_Traits>
    {   // ordered red-black tree for [multi_]{map set}
Добавлено через 11 минут
alex_x_x, Про стек - спасибо. Интересно было почитать.

Добавлено через 21 час 17 минут
Я апну пожалуй темку, может все же кто знает ответы на вопросы, но не увидел тему.
Yandex
Объявления
05.03.2011, 23:51     Tree, set, map etc.
Ответ Создать тему
Опции темы

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