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

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

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

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

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

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

    • std::map
    • std::set

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

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

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

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

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

    Вот некоторые другие общие реализации дерева:
    – Дерево Kasper Peeters.hh
    – лес Adobe
    – core :: tree

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

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

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

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

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

     template< typename T > void tree_node::walk_depth_first() const { cout< 

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

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

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

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

    В общем, если есть основная функциональность библиотеки, которую вы хотите, это не в stl, исправление – посмотреть BOOST .

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

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

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

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

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

    Например:

     template  struct TreeNode { T* DATA ; // data of type T to be stored at this TreeNode vector< TreeNode* > 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  struct Tree { TreeNode* root; // TREE LEVEL functions void clear() { delete root ; root=0; } void insert( T* data ) { if(root)root->insert(data); } } ; 

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

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

     template struct unordered_tree : std::set, A {}; template struct b_tree : std::vector, A {}; template struct planar_tree : std::list, A {}; 

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

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

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

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

     template struct node_iterator : std::stack{ operator*() {return *back();} ...}; 

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

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

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

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

    Давайте будем гением компьютера.