Tree, set, map etc.

@ForEveR · Регистрация: 24.06.2010

Author24 — интернет-сервис помощи студентам

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

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

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

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

Заранее спасибо за ответы.

@alex_x_x · 05.03.2011, 02:12

Сообщение от 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)

@ForEveR · 05.03.2011, 23:51 **[ТС]**

MSVS 2008
Файл xtree.

C++

        // 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 минут
Я апну пожалуй темку, может все же кто знает ответы на вопросы, но не увидел тему.

Новые блоги и статьи
Счётчик на базе сумматоров + регистров и генератора сигналов согласования. Hrethgir 07.01.2025 Создан с целью проверки скорости асинхронной логики: ранее описанного сумматора и предополагаемых fast регистров. Регистры созданы на базе ранее описанного, предполагаемого fast триггера. То-есть. . .	Как перейти с Options API на Composition API в Vue.js BasicMan 06.01.2025 Почему переход на Composition API актуален В мире современной веб-разработки фреймворк Vue. js продолжает эволюционировать, предлагая разработчикам все более совершенные инструменты для создания. . .	Архитектура современных процессоров inter-admin 06.01.2025 Процессор (центральный процессор, ЦП) является основным вычислительным устройством компьютера, которое выполняет обработку данных и управляет работой всех остальных компонентов системы. Архитектура. . .	История создания реляционной модели баз данных, правила Кодда Programming 06.01.2025 Предпосылки создания реляционной модели В конце 1960-х годов компьютерная индустрия столкнулась с серьезными проблемами в области управления данными. Существовавшие на тот момент модели данных -. . .	Полезные поделки на Arduino, которые можно сделать самому raxper 06.01.2025 Arduino как платформа для творчества Arduino представляет собой удивительную платформу для технического творчества, которая открывает безграничные возможности для создания уникальных проектов. Эта. . .	Подборка решений задач на Python IT_Exp 06.01.2025 Целью данной подборки является предоставление возможности ознакомиться с различными задачами и их решениями на Python, что может быть полезно как для начинающих, так и для опытных программистов. . . .
С чего начать программировать микроконтроллеры raxper 06.01.2025 Введение в мир микроконтроллеров Микроконтроллеры стали неотъемлемой частью современного мира, окружая нас повсюду: от простых бытовых приборов до сложных промышленных систем. Эти маленькие. . .	Из чего собрать игровой компьютер inter-admin 06.01.2025 Сборка игрового компьютера требует особого внимания к выбору комплектующих и их совместимости. Правильно собранный игровой ПК не только обеспечивает комфортный геймплей в современных играх, но и. . .	Обновление сайта www.historian.by Reglage 05.01.2025 Обещал подвести итоги 2024 года для сайта. Однако начну с того, что изменилось за неделю. Добавил краткий урок по последовательности действий при анализе вредоносных файлов и значительно улучшил урок. . .	Как использовать GraphQL в C# с HotChocolate Programming 05.01.2025 GraphQL — это современный подход к разработке API, который позволяет клиентам запрашивать только те данные, которые им необходимы. Это делает взаимодействие с API более гибким и эффективным по. . .	Модель полного двоичного сумматора с помощью логических операций (python) AlexSky-coder 04.01.2025 def binSum(x:list, y:list): s=^y] p=x and y for i in range(1,len(x)): s. append((x^y)^p) p=(x and y)or(p and (x or y)) return s x=list() y=list()	Это мы не проходили, это нам не задавали...(асихронный счётчик с управляющим сигналом зад Hrethgir 04.01.2025 Асинхронный счётчик на сумматорах (шестиразрядный по числу диодов на плате, но наверное разрядов будет больше - восемь или шестнадцать, а диоды на старшие), так как триггеры прошли тестирование и. . .

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
		1
	Tree, set, map etc. 05.03.2011, 01:23. Показов 2820. Ответов 2 Метки нет (Все метки) Решил посмотреть реализацию стандартного мап/сет и вспомогательного класса _Tree (кстати, он только в MSVS или есть везде, но по разному называется и по разному реализован?). Реализованы они по стандарту как известно через красно-черное сбалансированное бинарное дерево (кстати, сложно-ли такое реализовать впринципе? Просто интересно стало, может надумаю как-нибудь, список и вектор реализован (без проверок почти), надо бы реализовать все). Но главный вопрос состоит в том как они реализованы? Итеративно или же рекурсией? При самописном дереве - стек переполняется через 3+к элементов. В set/map могу вставить и 2 ляма. Кто-нибудь знает точно как там это реализовано? Ну и + если есть инфа об этом в стандарте - ссылку плиз. И крайний вопрос - чем определяется глубина раскрутки стека для каждой машины? Вот у меня например дерево держало порядка 3к элементов, у fasked его дерево держало около 20-200к и не падало. Как определить? Оперативка влияет или все вместе взятое? Заранее спасибо за ответы. 0

	05.03.2011, 23:51

Tree, set, map etc.

Решение