В астрале
Эксперт С++
8045 / 4802 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
1

Tree, set, map etc.

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

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

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

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

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

Заранее спасибо за ответы.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.03.2011, 01:23
Ответы с готовыми решениями:

Замена char на map/set
Всем привет! Задача была написать программу, которая выводит слово, которое встречается чаще всего...

Map/set iterator not dereferencable
Есть два класса, первый: class AnimationManager { public: String currentAim;...

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

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

2
бжни
2473 / 1684 / 135
Регистрация: 14.05.2009
Сообщений: 7,162
05.03.2011, 02:12 2
Лучший ответ Сообщение было отмечено ForEveR как решение

Решение

Цитата Сообщение от ForEveR Посмотреть сообщение
И крайний вопрос - чем определяется глубина раскрутки стека для каждой машины? Вот у меня например дерево держало порядка 3к элементов, у fasked его дерево держало около 20-200к и не падало. Как определить? Оперативка влияет или все вместе взятое?
кратко говоря: рихтер стек потока
http://wm-help.net/books-onlin... 464-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)
1
В астрале
Эксперт С++
8045 / 4802 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
05.03.2011, 23:51  [ТС] 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 минут
Я апну пожалуй темку, может все же кто знает ответы на вопросы, но не увидел тему.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.03.2011, 23:51
Помогаю со студенческими работами здесь

Map/set iterators are incompatible
void Delete(int a , int b) { multiset &lt;double&gt; ::iterator First, Last; multiset &lt;double&gt;...

map/set iterator not dereferencable
map&lt;string,int&gt; optimized(map&lt;string,int&gt;&amp;dict){ map&lt;string,int&gt;::iterator i=dict.begin();...

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru