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

Мне нужно дерево для хранения представления иерархии.

Я с парнем, который проголосовал против «правильных» ответов, что, кажется, так; «Деревья бесполезны». Есть важные, но неясные способы использования деревьев.

Думаю, причина банальна - в стандартной библиотеке еще никто не реализовал. Как будто в стандартной библиотеке до недавнего времени не было std::unordered_map и std::unordered_set. А до этого в стандартной библиотеке вообще не было STL-контейнеров.

Мои мысли (хотя я никогда не читал соответствующий стандарт, поэтому это комментарий, а не ответ) заключаются в том, что STL не заботится о конкретных структурах данных, он заботится о спецификациях, касающихся сложности и поддерживаемых операций. Таким образом, используемая базовая структура может варьироваться в зависимости от реализации и / или целевой архитектуры, при условии, что она удовлетворяет спецификациям. Я почти уверен, что std::map и std::set будут использовать дерево в каждой реализации, но они не обязаны это делать, если некоторая не древовидная структура также соответствует спецификациям.

Обычно он использует красно-черные деревья (этого делать не обязательно).

GCC использует дерево для реализации карты. Кто-нибудь хочет посмотреть в свой каталог VC include, чтобы узнать, что использует Microsoft?

// Класс красно-черного дерева, предназначенный для использования // при реализации ассоциативных контейнеров STL (set, multiset, map и multimap). Взял это из моего файла stl_tree.h.

@ J.J. По крайней мере, в Studio 2010 он использует внутренний класс ordered red-black tree of {key, mapped} values, unique keys, определенный в <xtree>. В настоящий момент у вас нет доступа к более современной версии.

Есть много-много причин использовать дерево, даже если они самые распространенные. Самый обычный! Равный всем.

Третья основная причина, по которой нужно дерево, - это всегда отсортированный список с быстрой вставкой / удалением, но для этого есть std: multiset.

Как мы можем использовать карту для древовидной структуры данных, если мы не знаем глубины дерева?

@Durga: Не уверен, насколько важна глубина, когда вы используете карту в качестве отсортированного контейнера. Карта гарантирует вставку / удаление / поиск журнала (n) (и содержит элементы в отсортированном порядке). Это все, что карта используется и реализована (обычно) в виде красного / черного дерева. Красное / черное дерево гарантирует, что дерево сбалансировано. Таким образом, глубина дерева напрямую связана с количеством элементов в дереве.

Я не согласен с этим ответом как в 2008 году, так и сейчас. Стандартная библиотека не имеет ускорения, и наличие чего-либо в ускорении не должно быть (и не было) причиной не принимать это в стандарт. Кроме того, BGL является общим и достаточно сложным, чтобы заслужить независимые от него специализированные классы деревьев. Кроме того, тот факт, что для std :: map и std :: set требуется дерево, является, IMO, еще одним аргументом в пользу наличия stl::red_black_tree и т. д. Наконец, деревья std::map и std::set сбалансированы, а std::tree может не быть.

@einpoklum: «наличие чего-то в усилении не должно быть причиной не принимать это в стандарт» - учитывая, что один из цели повышения должен выступать в качестве испытательного полигона для полезных библиотек перед включением в стандарт, я могу только сказать «абсолютно!».

Двоичные деревья представляют собой чрезвычайно базовую функциональность и, по сути, более простую, чем другие контейнеры, поскольку такие типы, как std :: map, std :: multimap и stl :: set. Поскольку эти типы основаны на них, можно ожидать, что будет открыт базовый тип.

Я не думаю, что OP запрашивает дерево двоичный, он запрашивает дерево для хранения иерархии.

Мало того, добавление «контейнера» дерева в STL означало бы добавление множества новых концепций, например, древовидный навигатор (обобщающий итератор).

«Минимальные конструкции для создания вещей» - очень субъективное утверждение. Вы можете создавать что-то, используя необработанные концепции C++, поэтому я предполагаю, что истинным минимумом будет вообще отсутствие STL.

"... нет хорошего способа удовлетворить всех ..." За исключением того, что, поскольку stl :: map, stl :: multimap и stl :: set основаны на rb_tree stl, он должен удовлетворять такому же количеству случаев, как и эти базовые типы .

Учитывая, что нет возможности получить дочерние элементы узла std::map, я бы не стал называть эти древовидные контейнеры. Это ассоциативные контейнеры, которые обычно реализуются в виде деревьев. Большая разница.

Я согласен с Mooing Duck, как бы вы реализовали поиск в ширину на std :: map? Это будет ужасно дорого

Я начал использовать tree.hh Kasper Peeters, однако после ознакомления с условиями лицензирования GPLv3 или любой другой версии GPL это могло загрязнить наше коммерческое программное обеспечение. Я бы порекомендовал взглянуть на дерево деревьев, приведенное в комментарии @hplbsh, если вам нужна структура для коммерческих целей.

Фактически, Boost предоставляет контейнер в виде дерева. Библиотека называется Boost.PropertyTree.

В итоге я использовал datasoftsolutions.net/tree_container_library/overview.php, я пробовал treeree, но документация была скудной, и использование было очень сложным. Boost.PropertyTree хорошо работает со строками, но не видел примеров использования чего-либо еще. TCL поддерживает только заголовки, коммерческую и STL. Это хорошо работает для моих целей.

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

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

Библиотека Boost Graph предоставляет R-дерево.

Я не думаю, что он говорит о реализациях контейнеров, он говорит о самом реальном контейнере дерева.

@MooingDuck Я думаю, что Wilhelmtell имеет в виду, что стандартная библиотека C++ не определяет контейнеры на основе их базовой структуры данных; он определяет контейнеры только по их интерфейсу и наблюдаемым характеристикам, таким как асимптотическая производительность. Когда вы думаете об этом, дерево на самом деле вовсе не контейнер (как мы их знаем). У них даже нет простых end() и begin(), с помощью которых вы можете перебирать все элементы и т. д.

@JordanMelo: Ерунда по всем пунктам. Это вещь, которая содержит предметы. Очень просто создать в нем итераторы begin () и end (), а также двунаправленные итераторы для выполнения итерации. Каждый контейнер имеет разные характеристики. Было бы полезно, если бы можно было дополнительно иметь характеристики дерева. Должно быть довольно легко.

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

@JordanMelo: С этой точки зрения адаптеры, такие как очереди, стеки или очереди с приоритетом, не будут принадлежать STL (у них также нет begin() и end()). И помните, что очередь с приоритетами обычно представляет собой кучу, которая, по крайней мере, теоретически представляет собой дерево (даже при фактических реализациях). Таким образом, даже если вы реализовали дерево в качестве адаптера с использованием другой базовой структуры данных, его можно было бы включить в STL.

@andreee Конечно, никто не говорит, что только контейнеры принадлежат STL. Адаптеры контейнера не подходят для Концепция Container, и они, очевидно, находятся в STL, как вы заметили. Вы приводите priority_queue в качестве примера, но я думаю, вы согласитесь с тем, что он не предоставляет никакого древовидного поведения и использует древовидную структуру для очень конкретной цели. Но как насчет общих деревьев? Помните, что одна из наиболее важных функций древовидной структуры - моделирование отношений, которые не всегда соответствуют двоичной древовидной структуре.

Как ни странно, это единственный ответ, который действительно отвечает на исходный вопрос.

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

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

@Dan: Копирование не означает его непосредственное использование.

Древовидная структура данных может обеспечивать предварительный, неупорядоченный или постзаказный обход с помощью итераторов. Фактически это то, что делает std :: map.

Да и нет ... все зависит от того, что вы подразумеваете под «деревом». std::map внутренне реализован как btree, но внешне выглядит как отсортированная ПОСЛЕДОВАТЕЛЬНОСТЬ ПАР. Учитывая любой элемент, вы можете универсально спросить, кто до, а кто после. Общие древовидные структуры, содержащие элементы, каждый из которых содержит другие, не налагают никакой сортировки или направления. Вы можете определить итераторы, которые обходят древовидную структуру разными способами (желтый | глубокий первый | последний ...), но как только вы это сделаете, контейнер std::tree должен вернуть один из них из функции begin. И нет явных причин возвращать то или иное.

Std :: map обычно представлена ​​сбалансированным двоичным деревом поиска, а не B-деревом. Тот же аргумент, который вы сделали, можно применить к std :: unordered_set, он не имеет естественного порядка, но имеет итераторы начала и конца. Требование начала и конца состоит в том, чтобы он выполнял итерацию всех элементов в некотором детерминированном порядке, а не в естественном порядке. preorder - вполне допустимый порядок итераций для дерева.

«Std :: map обычно представляет собой сбалансированное двоичное дерево поиска, а не B-дерево.»: В какую игру вы играете? btree - это реализация двоичного дерева поиска, а map не "представлена" как таковая. он «РЕАЛИЗОВАН» как таковой. он ПРЕДСТАВЛЯЕТСЯ как отсортированная последовательность пар, которая начинается с begin () и заканчивается непосредственно перед end (). Верно, что вы можете пройти по дереву, начиная с некоторого begin () до некоторого end (), но, если не определить для него цель (как это делает map), больше нет подсказки, чем иметь элементы в списке.

Из вашего ответа следует, что нет структуры данных stl n-tree, потому что у нее нет интерфейса "последовательности". Это просто неверно.

Нет: потому что у него нет УНИКАЛЬНОГО СПОСОБА для определения интерфейса последовательности, поскольку его обычная цель - не быть простой последовательностью. Принятие одного из них как «стандартного» лишит возможности иметь такую ​​структуру, а не навязывание этого сделает конструкцию бесполезной по отношению к <algorithm>, которому соответствует любой другой контейнер. Вы всегда можете сделать это самостоятельно, но то, как вы это сделаете, будет противоречить чужому, и нет никаких технических причин отдавать предпочтение тому или иному. Так что не может быть «стандартного» способа.

@EmiloGaravaglia: Как свидетельствует std::unordered_set, у которого нет «уникального способа» итерации своих членов (на самом деле порядок итерации псевдослучайный и определен в реализации), но все же является контейнером stl - это опровергает вашу точку зрения. Итерация по каждому элементу в контейнере по-прежнему является полезной операцией, даже если порядок не определен.

Я больше не могу понять, не могу ли я объяснить или вы не хотите понимать. unordered_set не имеет уникального способа СОРТИРОВКИ, но имеет уникальный способ ХОДИТЬ: начать с begin() и закончить end(), и может быть подвержен любому <algorithm>. Но дерево с уникальным способом ХОДИТЬ бесполезно, так как цель дерева - ХОДИТЬ по крайней мере вверх и влево-вправо. Если моя манера говорить вам непонятна, прочтите это: stackoverflow.com/a/206011/924727 Это в точности моя концепция, с другой формулировкой.

Нет причин, по которым у контейнера должен быть один путь обхода, можно предлагать разные порядки итераций для разных типов пар итераторов (например, см. rbegin / rend). В std: tree может быть что-то вроде breadth_begin / breadth_end и depth_begin / depth_end для порядков вверх-вниз и влево-вправо соответственно. Ответ, на который вы ссылаетесь, правильный, это большая разница в потенциальной структуре, которая приводит к тому, что она не входит в стандартную библиотеку, но это не имеет ничего общего с «последовательностями» или «механизмом одной итерации».

Это нужно сделать, потому что они являются основной причиной такой разницы. Не стесняйтесь, не верьте этому, но позвольте мне поверить в мир с Богом!

@EmilioGaravaglia Я понимаю вашу точку зрения. Вы хотите иметь возможность выбирать стратегию итерации в контейнере дерева, потому что а) дерево семантически соответствует вашим данным б) вы хотите пройти по дереву в конкретном случае для решения проблемы. Возможное решение: std::tree имеет аргумент шаблона перечислимого тега, который сообщает порядок обхода по умолчанию, заданный функцией begin () для диапазона, скажем. По умолчанию в этом шаблоне arg указано traversal::inorder. Вы даже можете дать имена другим: template<typename NodeT> using tree_pre<NoteT> = tree<NodeT, traversal::preorder>; и т. д. Это работоспособная проблема.

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

@emsr: Хорошее предложение. Конечно, через 3 года что-то развивается, но ... на самом деле он ввел новую концепцию (диапазоны), фактически позволяющую разрушить ограничение.

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

Предлагаю вам отозвать этот ответ. Класс TreeNode является частью реализации дерева.

Если проект может разрешить сортировку дочерних элементов tree_node, то использование std :: set <> вместо std :: vector <> и последующее добавление оператора <() к объекту tree_node значительно улучшит «поисковое» выполнение Т-образного объекта.

Оказывается, они поленились и фактически создали ваш первый пример Undefined Behavior.

@Mehrdad: Я наконец решил спросить подробности вашего комментария здесь.

many of the algorithms simply don't make any sense for a hierarchy. Вопрос интерпретации. Представьте себе структуру пользователей stackoverflow, и каждый год вы хотите, чтобы те, у кого больше очков репутации, руководили теми, у кого меньше очков репутации. Таким образом, обеспечивая итератор BFS и соответствующее сравнение, вы каждый год просто запускаете std::sort(tree.begin(), tree.end()).

По тому же принципу вы можете легко построить ассоциативное дерево (для моделирования неструктурированных записей типа "ключ-значение", например, JSON), заменив vector на map в приведенном выше примере. Для полной поддержки структуры, подобной JSON, вы можете использовать variant для определения узлов.

Также тривиально легко создать собственную реализацию vector поверх new / delete, но у нас есть и почти все используют std::vector ...

Но вы можете сказать, что BFS или DFS - правильный путь. Или поддержите их обоих. Или любой другой, который вы можете себе представить. Просто скажите пользователю, что это такое.

в std :: map есть итератор дерева.

Дерево может определять свой собственный тип итератора, который проходит все узлы в порядке от одного «крайнего» к другому (то есть для любого двоичного дерева с путями 0 и 1 оно может предлагать итератор, который идет от «все 0» до «все». 1s ", и обратный итератор, который делает противоположное; например, для дерева с глубиной 3 и начальным узлом s он может перебирать узлы как s000, s00, s001, s0, s010, s01, s011, s. , s100, s10, s101, s1, s110, s11, s111 (от «крайнего левого» до «крайнего правого»); он также может использовать шаблон обхода глубины (s, s0, s1, s00, s01, s10, s11,

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

Я не понимаю, почему этот ответ был так сильно отвергнут. Это единственный ответ на вопрос. Дерево не является частью интерфейса STL (хотя оно существует внутри), поскольку дерево не является контейнером в смысле STL, то есть не является контейнером элементов с линейной итерацией. (Например, у него не будет уникальных begin() и end()). Добавление дерева в STL означало бы добавление множества новых концепций, например, древовидный навигатор (обобщающий итератор).

@alfC, что не так с определением begin() как корневого узла и end() как последнего листа?

@doc, конечно, есть много листьев, и даже если вы выберете один в качестве последнего, нет единственного способа пройти три линейно.

@alfC вы можете выбрать любую из DFS или BFS, как уже указывал tomas789. Я много раз реализовывал итераторы для своих древовидных структур.

@doc, конечно, но трансверсаль не уникальна, как в последовательности. Общий график может быть пересечен по DFS или BFS, но это еще не делает их последовательностью. Их можно рассматривать как последовательность, но это другое дело.

Библиотека @alfC std не ограничена последовательностями, std::unordered_map не является последовательностью, но уже существует в стандартной библиотеке. Не существует таких понятий, как «уникальная итерация» или «уникальный обход». Даже с массивом вы можете перебирать его любым способом. Итераторы точно решают эту проблему и предоставляют уровень абстракции, поэтому вы можете выполнять итерацию по таким структурам, как std::map. Все дело в условности.

@doc, очень хорошее замечание. Я думаю, что std::unordered_set был «сделан» последовательностью, потому что мы не знаем лучшего способа итерации по элементам, кроме как каким-то произвольным способом (внутренне заданным хеш-функцией). Я думаю, что это противоположный случай с деревом: итерация по unordered_set недооценена, теоретически нет «никакого способа» определить итерацию, кроме, возможно, «случайным образом». В случае с деревом существует множество «хороших» (неслучайных) способов. Но, опять же, ваша точка зрения верна.