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

Question

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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

Вот некоторые другие общие реализации дерева:
- Дерево Каспера Петерса.хх
- Лес 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, исправление состоит в том, чтобы посмотреть СПОСОБСТВОВАТЬ РОСТУ.

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

Answer 8

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

Answer 9

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

Answer 10

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

Answer 11

ИМХО, упущение.Но я думаю, что есть веская причина не включать древовидную структуру в STL.В поддержании дерева есть много логики, которую лучше всего записать как функции-члены в базу TreeNode объект.Когда TreeNode заключен в заголовок STL, это становится еще более запутанным.

Например:

template <typename T>
struct TreeNode
{
  T* DATA ; // data of type T to be stored at this TreeNode

  vector< TreeNode<T>* > children ;

  // insertion logic for if an insert is asked of me.
  // may append to children, or may pass off to one of the child nodes
  void insert( T* newData ) ;

} ;

template <typename T>
struct Tree
{
  TreeNode<T>* root;

  // TREE LEVEL functions
  void clear() { delete root ; root=0; }

  void insert( T* data ) { if(root)root->insert(data); } 
} ;

Answer 12

Я думаю, есть несколько причин, по которым нет stl-деревьев.В первую очередь деревья — это форма рекурсивной структуры данных, которая, как и контейнер (список, вектор, набор), имеет совершенно другую тонкую структуру, что затрудняет правильный выбор.Их также очень легко создать в базовой форме с использованием STL.

Конечное корневое дерево можно рассматривать как контейнер, который имеет значение или полезную нагрузку, скажем, экземпляр класса A и, возможно, пустую коллекцию корневых (под) деревьев;деревья, лишенные поддеревьев, считаются листьями.

template<class A>
struct unordered_tree : std::set<unordered_tree>, A
{};

template<class A>
struct b_tree : std::vector<b_tree>, A
{};

template<class A>
struct planar_tree : std::list<planar_tree>, A
{};

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

Деревья играют существенную роль во многих математических структурах (см. классические статьи Бутчера, Гроссмана и Ларсена;также статьи Конна и Кримера с примерами того, как их можно объединять, и как их использовать для перечисления).Неверно думать, что их роль заключается просто в содействии некоторым другим операциям.Скорее они облегчают эти задачи из-за своей фундаментальной роли в качестве структуры данных.

Однако помимо деревьев есть еще и «содеревья»;деревья, прежде всего, обладают свойством: если вы удалите корень, вы удалите все.

Рассмотрим итераторы в дереве, возможно, они будут реализованы как простой стек итераторов для узла и его родителя...до самого корня.

template<class TREE>
struct node_iterator : std::stack<TREE::iterator>{
operator*() {return *back();}
...};

Однако вы можете иметь столько, сколько захотите;вместе они образуют «дерево», но там, где все стрелки движутся в направлении к корню, это совместное дерево может повторяться через итераторы в направлении тривиального итератора и корня;однако по нему нельзя перемещаться вдоль или вниз (другие итераторы ему неизвестны), а ансамбль итераторов нельзя удалить, кроме как путем отслеживания всех экземпляров.

Деревья невероятно полезны, у них много структур, поэтому найти окончательно правильный подход становится серьезной проблемой.На мой взгляд, именно поэтому они не реализованы в STL.Более того, в прошлом я видел, как люди становились религиозными и находили идею типа контейнера, содержащего экземпляры своего собственного типа, сложной - но им приходилось с этим сталкиваться - это то, что представляет собой тип дерева - это узел, содержащий возможно, пустая коллекция (меньших) деревьев.Текущий язык позволяет это без проблем, предоставляя конструктор по умолчанию для container<B> не выделяет место в куче (или где-либо еще) для B, и т. д.

Лично я был бы рад, если бы это в хорошей форме вошло в стандарт.

Answer 13

Все контейнеры STL можно использовать с итераторами.У вас не может быть итератора в дереве, потому что у вас нет «одного правильного» способа пройти через дерево.