05.03.2011, 01:23. Просмотров 1373. Ответов 2
Решил посмотреть реализацию стандартного мап/сет и вспомогательного класса _Tree (кстати, он только в MSVS или есть везде, но по разному называется и по разному реализован?).
Реализованы они по стандарту как известно через красно-черное сбалансированное бинарное дерево (кстати, сложно-ли такое реализовать впринципе? Просто интересно стало, может надумаю как-нибудь, список и вектор реализован (без проверок почти), надо бы реализовать все).
Но главный вопрос состоит в том как они реализованы? Итеративно или же рекурсией? При самописном дереве - стек переполняется через 3+к элементов. В set/map могу вставить и 2 ляма. Кто-нибудь знает точно как там это реализовано? Ну и + если есть инфа об этом в стандарте - ссылку плиз.
И крайний вопрос - чем определяется глубина раскрутки стека для каждой машины? Вот у меня например дерево держало порядка 3к элементов, у fasked его дерево держало около 20-200к и не падало. Как определить? Оперативка влияет или все вместе взятое?
Заранее спасибо за ответы.
0
|