blocks|key|1715911|text|在某种程度上，std::map是一个树(要求它具有与平衡二叉树相同的性能特征)，但它不公开其他树功能。不包含真正的树数据结构背后可能的原因可能只是不包含stl中的所有内容。可以将stl视为一个框架，用于实现您自己的算法和数据结构。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1715912|通常，如果有您想要的基本库功能，那么修复方法就是查看BOOST。|offset|length|1715913|否则，会有一个libraries+out+there的bunch，这取决于您的树的需要。|1715914|entityMap|0|LINK|mutability|MUTABLE|url|http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/index.html|1|http://www.codeproject.com/KB/architecture/treedata_class.aspx|2|http://stlplus.sourceforge.net/stlplus/docs/ntree.html|3|http://www.scalingweb.com/bplus_tree.php|4|http://www.aei.mpg.de/~peekas/tree/^0|0|Q|5|0|0|7|9|1|H|3|2|L|5|3|R|5|4|0^^$0|@$1|2|3|4|5|6|7|X|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Y|8|@]|9|@$D|Z|E|10|1|11]]|A|$]]|$1|F|3|G|5|6|7|12|8|@]|9|@$D|13|E|14|1|15]|$D|16|E|17|1|18]|$D|19|E|1A|1|1B]|$D|1C|E|1D|1|1E]]|A|$]]|$1|H|3|-4|5|6|7|1F|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]|P|$5|K|L|M|A|$N|Q]]|R|$5|K|L|M|A|$N|S]]|T|$5|K|L|M|A|$N|U]]|V|$5|K|L|M|A|$N|W]]]]

In a way, std::map is a tree (it is required to have the same performance characteristics as a balanced binary tree) but it doesn't expose other tree functionality. The likely reasoning behind not including a real tree data structure was probably just a matter of not including everything in the stl. The stl can be looked as a framework to use in implementing your own algorithms and data structures.

In general, if there's a basic library functionality that you want, that's not in the stl, the fix is to look at <a href="http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/index.html" rel="noreferrer">BOOST</a>.

Otherwise, there's a <a href="http://www.aei.mpg.de/~peekas/tree/" rel="noreferrer">bunch</a> of <a href="http://www.codeproject.com/KB/architecture/treedata_class.aspx" rel="noreferrer">libraries</a> <a href="http://stlplus.sourceforge.net/stlplus/docs/ntree.html" rel="noreferrer">out</a> <a href="http://www.scalingweb.com/bplus_tree.php" rel="noreferrer">there</a>, depending on the needs of your tree.

blocks|key|1500855|text|map是基于red+black+tree的。您还可以使用其他containers来帮助您实现自己的树类型。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1500856|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Red-black_tree|1|http://www.cplusplus.com/reference/stl/^0|6|E|0|U|A|1|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]|$A|R|B|S|1|T]]|C|$]]|$1|D|3|-4|5|6|7|U|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]|L|$5|G|H|I|C|$J|M]]]]

the std::map is based on a <a href="http://en.wikipedia.org/wiki/Red-black_tree" rel="noreferrer">red black tree</a>. You can also use other <a href="http://www.cplusplus.com/reference/stl/" rel="noreferrer">containers</a> to help you implement your own types of trees.

blocks|key|1715960|text|因为STL不是一个“万能”的库。从本质上讲，它包含了构建东西所需的最小结构。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1715961|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Because the STL is not an "everything" library. It contains, essentially, the minimum structures needed to build things.

blocks|key|1716012|text|STL的理念是根据保证而不是容器的实现方式来选择容器。例如，您对容器的选择可能基于对快速查找的需要。不管您是否关心，容器都可以实现为单向列表--只要搜索速度非常快，您就会满意。这是因为您并没有接触到内部，而是使用迭代器或成员函数进行访问。您的代码不受容器实现方式的限制，而是取决于它的速度，或者它是否具有固定和定义的顺序，或者它在空间上是否有效，等等。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1716013|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

The STL's philosophy is that you choose a container based on guarantees and not based on how the container is implemented. For example, your choice of container may be based on a need for fast lookups. For all you care, the container may be implemented as a unidirectional list -- as long as searching is very fast you'd be happy. That's because you're not touching the internals anyhow, you're using iterators or member functions for the access. Your code is not bound to how the container is implemented but to how fast it is, or whether it has a fixed and defined ordering, or whether it is efficient on space, and so on.

blocks|key|1500969|text|如果您正在寻找RB树实现，那么stl_tree.h可能也适合您。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1500970|entityMap|0|LINK|mutability|MUTABLE|url|http://gcc.gnu.org/onlinedocs/libstdc%2B%2B/libstdc%2B%2B-html-USERS-4.1/stl__tree_8h.html^0|F|A|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

If you are looking for a RB-tree implementation, then <a href="http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.1/stl__tree_8h.html" rel="noreferrer">stl_tree.h</a> might be appropriate for you too.

blocks|key|1716109|text|这个看起来很有希望，似乎就是你想要的：http://tree.phi-sci.com/|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1716110|entityMap|0|LINK|mutability|MUTABLE|url|http://tree.phi-sci.com/^0|J|O|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

This one looks promising and seems to be what you're looking for:
<a href="http://tree.phi-sci.com/" rel="noreferrer">http://tree.phi-sci.com/</a>

blocks|key|1716122|text|所有STL容器都外部表示为具有一种迭代机制的“序列”。树不遵循这个习语。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1716123|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

All STL container are externally represented as "sequences" with one iteration mechanism.
Trees don't follow this idiom.

blocks|key|1501067|text|所有的STL容器都可以和迭代器一起使用。你不能有一个迭代器和一棵树，因为你没有“一条正确”的方法来遍历树。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1501068|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

All STL containers can be used with iterators. You can't have an iterator an a tree, because you don't have ''one right'' way do go through the tree.

blocks|key|1716215|text|我认为没有STL树有几个原因。树基本上是递归数据结构的一种形式，就像容器(列表、向量、集合)一样，具有非常不同的精细结构，这使得正确的选择变得棘手。使用STL以基本形式构建它们也非常容易。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1716216|有限根树可以被认为是一个容器，它有一个值或有效负载，比如一个类A的实例和一个可能是空的有根(子)树的集合；具有空的子树集合的树被认为是叶子。|1716217|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
{};|code-block|syntax|javascript|1716218|人们必须考虑一下迭代器设计等问题，以及允许在树之间定义和高效的产品和联积操作-原始STL必须写得很好-这样在默认情况下，空集、向量或列表容器实际上是没有任何有效负载的。|1716219|树在许多数学结构中扮演着重要的角色(参见Butcher，Grossman和Larsen的经典论文；也可以参阅Connes和Kriemer的论文，了解它们可以连接的示例，以及它们如何用于枚举)。简单地认为他们的作用是促进某些其他操作是不正确的。相反，它们简化了这些任务，因为它们是作为数据结构的基础角色。|1716220|然而，除了树之外，还有“共树”；上面的树都具有这样的属性:如果删除根，就会删除所有内容。|1716221|考虑一下树上的迭代器，它们可能会被实现为一个简单的迭代器堆栈，指向一个节点，以及它的父节点……一直到根部。|1716222|template<class+TREE>
struct+node_iterator+:+std::stack<TREE::iterator>{
operator*()+{return+*back();}
...};|1716223|但是，您可以有任意多个；它们共同形成了一棵“树”，但是所有的箭头都指向根，这个联合树可以通过迭代器向平凡的迭代器和根进行迭代；但是，它不能被遍历或向下导航(其他迭代器是未知的)，也不能删除迭代器的集合，除非跟踪所有实例。|1716224|树非常有用，它们有很多结构，这使得获得绝对正确的方法成为一个严峻的挑战。在我看来，这就是它们没有在STL中实现的原因。此外，在过去，我看到人们变得信教，发现包含自己类型的实例的容器类型的想法具有挑战性-但他们必须面对它-这就是树类型所代表的-它是一个节点，其中可能包含(较小的)树的空集合。当前的语言可以毫不费力地提供container的默认构造函数，它不会为B分配堆上(或其他任何地方)的空间，等等。|offset|length|style|CODE|1716225|作为一个人，如果这真的以一种好的形式进入标准，我会很高兴的。|1716226|entityMap^0|0|0|0|0|0|0|0|0|0|4F|C|53|1|0|0^^$0|@$1|2|3|4|5|6|7|14|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|15|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|16|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|17|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|18|8|@]|9|@]|A|$]]|$1|M|3|N|5|6|7|19|8|@]|9|@]|A|$]]|$1|O|3|P|5|6|7|1A|8|@]|9|@]|A|$]]|$1|Q|3|R|5|F|7|1B|8|@]|9|@]|A|$G|H]]|$1|S|3|T|5|6|7|1C|8|@]|9|@]|A|$]]|$1|U|3|V|5|6|7|1D|8|@$W|1E|X|1F|Y|Z]|$W|1G|X|1H|Y|Z]]|9|@]|A|$]]|$1|10|3|11|5|6|7|1I|8|@]|9|@]|A|$]]|$1|12|3|-4|5|6|7|1J|8|@]|9|@]|A|$]]]|13|$]]

I think there are several reasons why there are no STL trees. Primarily Trees are a form of recursive data structure which, like a container (list, vector, set), has very different fine structure which makes the correct choices tricky. They are also very easy to construct in basic form using the STL.

A finite rooted tree can be thought of as a container which has a value or payload, say an instance of a class A and, a possibly empty collection of rooted (sub) trees; trees with empty collection of subtrees are thought of as leaves. 

<pre><code>template&lt;class A&gt;
struct unordered_tree : std::set&lt;unordered_tree&gt;, A
{};

template&lt;class A&gt;
struct b_tree : std::vector&lt;b_tree&gt;, A
{};

template&lt;class A&gt;
struct planar_tree : std::list&lt;planar_tree&gt;, A
{};
</code></pre>

One has to think a little about iterator design etc. and which product and co-product operations one allows to define and be efficient between trees - and the original STL has to be well written - so that the empty set, vector or list container is really empty of any payload in the default case. 

Trees play an essential role in many mathematical structures (see the classical papers of Butcher, Grossman and Larsen; also the papers of Connes and Kriemer for examples of they can be joined, and how they are used to enumerate). It is not correct to think their role is simply to facilitate certain other operations. Rather they facilitate those tasks because of their fundamental role as a data structure. 

However, in addition to trees there are also "co-trees"; the trees above all have the property that if you delete the root you delete everything.

Consider iterators on the tree, probably they would be realised as a simple stack of iterators, to a node, and to its parent, ... up to the root. 

<pre><code>template&lt;class TREE&gt;
struct node_iterator : std::stack&lt;TREE::iterator&gt;{
operator*() {return *back();}
...};
</code></pre>

However, you can have as many as you like; collectively they form a "tree" but where all the arrows flow in the direction toward the root, this co-tree can be iterated through iterators towards the trivial iterator and root; however it cannot be navigated across or down (the other iterators are not known to it) nor can the ensemble of iterators be deleted except by keeping track of all the instances. 

Trees are incredibly useful, they have a lot of structure, this makes it a serious challenge to get the definitively correct approach. In my view this is why they are not implemented in the STL. Moreover, in the past, I have seen people get religious and find the idea of a type of container containing instances of its own type challenging - but they have to face it - that is what a tree type represents - it is a node containing a possibly empty collection of (smaller) trees. The current language permits it without challenge providing the default constructor for <code>container&lt;B&gt;</code> does not allocate space on the heap (or anywhere else) for an <code>B</code>, etc. 

I for one would be pleased if this did, in a good form, find its way into the standard.

blocks|key|1501192|text|通读这里的答案，常见的命名原因是不能遍历树，或者树不假定与其他STL容器类似的接口，并且不能使用具有这种树结构的STL算法。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1501193|考虑到这一点，我试图设计我自己的树形数据结构，它将提供类似STL的接口，并将尽可能与现有的STL算法一起使用。|1501194|我的想法是，树必须基于现有的STL容器，并且它不能隐藏容器，以便它可以与STL算法一起使用。|1501195|树必须提供的另一个重要特性是遍历迭代器。|1501196|下面是我所能想到的：https://github.com/cppfw/utki/blob/master/src/utki/tree.hpp|offset|length|1501197|下面是测试：https://github.com/cppfw/utki/blob/master/tests/unit/src/tree.cpp|1501198|entityMap|0|LINK|mutability|MUTABLE|url|https://github.com/cppfw/utki/blob/master/src/utki/tree.hpp|1|https://github.com/cppfw/utki/blob/master/tests/unit/src/tree.cpp^0|0|0|0|0|A|1N|0|0|6|1T|1|0^^$0|@$1|2|3|4|5|6|7|X|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Y|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|Z|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|10|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|11|8|@]|9|@$J|12|K|13|1|14]]|A|$]]|$1|L|3|M|5|6|7|15|8|@]|9|@$J|16|K|17|1|18]]|A|$]]|$1|N|3|-4|5|6|7|19|8|@]|9|@]|A|$]]]|O|$P|$5|Q|R|S|A|$T|U]]|V|$5|Q|R|S|A|$T|W]]]]

Reading through the answers here the common named reasons are that one cannot iterate through the tree or that the tree does not assume the similar interface to other STL containers and one could not use STL algorithms with such tree structure.
Having that in mind I tried to design my own tree data structure which will provide STL-like interface and will be usable with existing STL algorthims as much as possible.
My idea was that the tree must be based on the existing STL containers and that it must not hide the container, so that it will be accessible to use with STL algorithms.
The other important feature the tree must provide is the traversing iterators.
Here is what I was able to come up with: <a href="https://github.com/cppfw/utki/blob/master/src/utki/tree.hpp" rel="nofollow noreferrer">https://github.com/cppfw/utki/blob/master/src/utki/tree.hpp</a>
And here are the tests: <a href="https://github.com/cppfw/utki/blob/master/tests/unit/src/tree.cpp" rel="nofollow noreferrer">https://github.com/cppfw/utki/blob/master/tests/unit/src/tree.cpp</a>

Why does the C++ STL not provide any "tree" containers, and what's the best thing to use instead?

I want to store a hierarchy of objects as a tree, rather than use a tree as a performance enhancement...

Why does the C++ STL not provide any "tree" containers?

数据结构

容器

为什么C++ STL不提供任何“树”容器，最好的替代方法是什么？我希望将对象的层次结构存储为树，而不是使用树作为性能增强……

问为什么C++ STL不提供任何“树”容器？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问为什么C++ STL不提供任何“树”容器？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问为什么C++ STL不提供任何“树”容器？
EN