为什么c++ STL不提供任何“树”容器,用什么代替最好?
我想将对象的层次结构存储为树,而不是使用树来增强性能……
为什么c++ STL不提供任何“树”容器,用什么代替最好?
我想将对象的层次结构存储为树,而不是使用树来增强性能……
当前回答
这一个看起来很有前途,似乎是你正在寻找的: http://tree.phi-sci.com/
其他回答
std::map基于红黑树。您还可以使用其他容器来帮助您实现自己的树类型。
通读这里的答案,常见的命名原因是不能遍历树,或者树没有假设与其他STL容器类似的接口,以及不能使用具有这种树结构的STL算法。
考虑到这一点,我尝试设计自己的树形数据结构,它将提供类似STL的接口,并将尽可能多地与现有的STL算法可用。
我的想法是树必须基于现有的STL容器,并且它不能隐藏容器,这样它就可以与STL算法一起使用。
树必须提供的另一个重要特性是遍历迭代器。
这是我能想到的:https://github.com/cppfw/utki/blob/master/src/utki/tree.hpp
下面是测试:https://github.com/cppfw/utki/blob/master/tests/unit/src/tree.cpp
因为STL不是一个“万能”库。本质上,它包含了建造东西所需的最小结构。
如果您正在寻找一个rb树实现,那么stl_tree.h可能也适合您。
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.