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

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

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

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

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

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

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

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

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

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

Некоторые вопросы для рассмотрения:

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

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

Вот некоторые другие реализации общего дерева:

• Kasper Peeters 'tree.hh
• Adobe лес
• Ядро :: дерево

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

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

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 , то все может быть сложно. Вы можете создать свои собственные итераторы и достичь некоторой совместимости, однако многие алгоритмы просто не имеют никакого смысла для иерархии (например, всего, что изменяет порядок диапазона). Даже определение диапазона в иерархии может быть грязным делом.

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

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

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

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

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

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

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

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

ИМО, упущение. Но я думаю, что есть веская причина не включать древовидную структуру в 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); } 
} ;

Я думаю, что есть несколько причин, почему нет деревьев 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т. Д.

Я, например, был бы рад, если бы это в хорошей форме нашло свое отражение в стандарте.

При чтении ответов здесь часто встречаются названные причины: нельзя перебирать дерево или что дерево не принимает интерфейс, аналогичный другим контейнерам STL, и нельзя использовать алгоритмы STL с такой структурой дерева.

Имея это в виду, я попытался спроектировать свою собственную древовидную структуру данных, которая обеспечит STL-подобный интерфейс и будет максимально использоваться с существующими алгоритмами STL.

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

Другая важная особенность, которую должно обеспечить дерево, это итераторы обхода.

Вот что я смог придумать: https://github.com/igagis/utki/blob/master/src/utki/tree.hpp

И вот тесты: https://github.com/igagis/utki/blob/master/tests/tree/tests.cpp

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