Почему C ++ STL не предоставляет никаких «древовидных» контейнеров?

Question

Почему C ++ STL не предоставляет никаких «древовидных» контейнеров, и что лучше вместо этого использовать?

Я хочу хранить иерархию объектов в виде дерева, а не использовать дерево для повышения производительности ...

Answer 1

Существует две причины, по которым вы можете использовать дерево:

Вы хотите отразить проблему, используя древовидную структуру:
Для этого у нас есть библиотека графов повышения

Или вам нужен контейнер с древовидными характеристиками доступа Для этого у нас есть

• std::map (и std::multimap)
• std::set (и std::multiset)

В основном характеристики этих двух контейнеров таковы, что они практически должны быть реализованы с использованием деревьев (хотя на самом деле это не является обязательным требованием).

Смотрите также этот вопрос: C tree Реализация

Answer 2

Вероятно, по той же причине, что в boost нет контейнера с деревом. Есть много способов реализовать такой контейнер, и нет хорошего способа удовлетворить всех, кто будет его использовать.

Некоторые вопросы для рассмотрения:
- Является ли число дочерних элементов для узла фиксированным или переменным?
Сколько накладных расходов на узел? - вам нужны родительские указатели, указатели братьев и сестер и т. д.
- Какие алгоритмы предоставить? - разные итераторы, алгоритмы поиска и т. д.

В конце концов, проблема заключается в том, что контейнер дерева, который был бы достаточно полезен для всех, был бы слишком тяжелым, чтобы удовлетворить большинство людей, использующих его. Если вы ищете что-то мощное, Boost Graph Library , по сути, является расширенным набором того, для чего может быть использована древовидная библиотека.

Вот некоторые другие реализации родового дерева:
- Дерево Каспера Питерса.hh
- Лес Adobe
- ядро ​​:: дерево

Answer 3

Философия STL заключается в том, что вы выбираете контейнер на основе гарантий, а не на основе того, как контейнер реализован. Например, ваш выбор контейнера может быть основан на необходимости быстрого поиска. Как ни крути, контейнер может быть реализован как однонаправленный список - если поиск очень быстрый, вы будете счастливы. Это потому, что вы все равно не касаетесь внутренних органов, вы используете итераторы или функции-члены для доступа. Ваш код связан не с тем, как реализован контейнер, а с тем, насколько он быстр, или имеет ли он фиксированный и определенный порядок, или эффективен ли он в пространстве и т. Д.

Answer 4

«Я хочу сохранить иерархию объектов в виде дерева»

C ++ 11 пришел и ушел, и они все еще не видели необходимости предоставлять std::tree, хотя идея все же пришла (см. здесь ). Возможно, причина, по которой они не добавили это, состоит в том, что легко построить свой собственный поверх существующих контейнеров. Например ...

template< typename T >
struct tree_node
   {
   T t;
   std::vector<tree_node> children;
   };

Простой обход будет использовать рекурсию ...

template< typename T >
void tree_node<T>::walk_depth_first() const
   {
   cout<<t;
   for ( auto & n: children ) n.walk_depth_first();
   }

Если вы хотите поддерживать иерархию и , которую вы хотите, чтобы она работала с алгоритмами STL , то все может быть сложно. Вы можете создать свои собственные итераторы и достичь некоторой совместимости, однако многие алгоритмы просто не имеют никакого смысла для иерархии (например, всего, что изменяет порядок диапазона). Даже определение диапазона в иерархии может быть грязным делом.

Answer 5

Если вы ищете реализацию дерева RB, тогда stl_tree.h также может подойти вам.

Answer 6

std :: map основана на красном черном дереве . Вы также можете использовать другие контейнеры , чтобы помочь вам реализовать свои собственные типы деревьев.

Answer 7

В некотором смысле, std :: map - это дерево (оно должно иметь те же характеристики производительности, что и сбалансированное двоичное дерево), но оно не предоставляет другие функциональные возможности дерева. Вероятная причина, по которой не была включена структура данных реального дерева, была, вероятно, просто вопросом не включения всего в stl. Stl можно рассматривать как основу для реализации собственных алгоритмов и структур данных.

В общем, если вам нужна базовая функциональность библиотеки, которой нет в stl, исправление должно выглядеть на BOOST .

В противном случае есть связка из библиотек out там , в зависимости от потребностей вашего дерева.

Answer 8

Все контейнеры STL внешне представлены как «последовательности» с одним итерационным механизмом. Деревья не следуют этой идиоме.

Answer 9

Это выглядит многообещающе и кажется, что вы ищете: http://tree.phi -sci.com /

Answer 10

Потому что STL не является библиотекой "всего". Он содержит, по сути, минимальные структуры, необходимые для построения вещей.