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

Question

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

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

Answer 1

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

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

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