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

Tree, set, map etc. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7933 / 4715 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
05.03.2011, 01:23     Tree, set, map etc. #1
Решил посмотреть реализацию стандартного мап/сет и вспомогательного класса _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.
Посмотрите здесь:

C++ поменять в настройке Character Set на Use Multy-Byte Character Set
C++ map/set iterator not dereferencable
C++ Map/set iterator not dereferencable
C++ Map/set iterator not dereferencable
Map/set!( iterator not dereferencable) C++
C++ Expression:map/set incompatible
Expression:map/set incompatible C++
C++ Map/set iterators are incompatible
C++ Tree of expressions
C++ Программа аварийно завершается с ошибкой "map/set iterators are incompatible"
Замена char на map/set C++
Найти такой подмассив, что его сумма максимальна (через контейенры map и set) C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
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
Модератор
Эксперт С++
 Аватар для ForEveR
7933 / 4715 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 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.
Ответ Создать тему
Опции темы

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