题
如何在 C++ 中创建使用迭代器而不是指针的树数据结构?我在 STL 中找不到任何可以做到这一点的东西。我想做的是能够像这样创建和操作树:
#include <iostream>
#include <tree>
using namespace std;
int main()
{
tree<int> myTree;
tree<int>::iterator i = myTree.root();
*i = 42;
tree<int>::iterator j = i.add_child();
*j = 777;
j = j.parent();
if (i == myTree.root() && i == j) cout << "i and j are both pointing to the root\n";
return 0;
}
谢谢你,tree.hh 似乎正是我一直在寻找的东西。
如果这是为了获得保存任意索引类型的数据结构的好处,该类型已优化用于搜索和插入,请考虑使用地图。
地图是一个具有性能的关联容器,可以保证与树的相同:对数搜索,对数插入,对数删除,线性空间。在内部,它们通常被用作红黑树,尽管这不是保证。尽管如此,作为STL用户,您应关心的只是STL算法和数据结构的性能保证。他们是用作树木还是小绿人对您无关紧要。
我不确定地图是否是我需要的,但感谢您提供的信息。我会记住尽可能使用地图而不是实现树。
解决方案
这是 树.hh 尽管有些不同,但它与您想做的事情有点接近。
这是从其网站上提取的一段代码。
int main(int, char **)
{
tree<string> tr;
tree<string>::iterator top, one, two, loc, banana;
top=tr.begin();
one=tr.insert(top, "one");
two=tr.append_child(one, "two");
tr.append_child(two, "apple");
banana=tr.append_child(two, "banana");
tr.append_child(banana,"cherry");
tr.append_child(two, "peach");
tr.append_child(one,"three");
loc=find(tr.begin(), tr.end(), "two");
if(loc!=tr.end()) {
tree<string>::sibling_iterator sib=tr.begin(loc);
while(sib!=tr.end(loc)) {
cout << (*sib) << endl;
++sib;
}
cout << endl;
tree<string>::iterator sib2=tr.begin(loc);
tree<string>::iterator end2=tr.end(loc);
while(sib2!=end2) {
for(int i=0; i<tr.depth(sib2)-2; ++i)
cout << " ";
cout << (*sib2) << endl;
++sib2;
}
}
}
现在有什么不同吗?在附加到树节点时,您的实现更简单。尽管您的版本无疑更简单,但该库的开发人员可能希望在不浏览树的情况下访问一些信息,例如树的大小。
我还假设出于性能原因,他不想将根存储在所有节点上。因此,如果您想按照自己的方式实现它,我建议您保留大部分逻辑,并在迭代器中添加到父树的链接,并稍微重写一下append。
其他提示
你为什么想这么做?如果这是出于学习目的,那么您可以编写自己的树数据结构。如果这是为了获得保存任意索引类型的数据结构的好处,针对搜索进行优化并擅长插入,那么请考虑使用映射。
映射是一种关联容器,其性能保证与树相同:对数搜索、对数插入、对数删除、线性空间。在内部,它们通常被实现为红黑树,尽管这并不能保证。尽管如此,作为 STL 用户,您应该关心的是 STL 算法和数据结构的性能保证。无论它们是被实现为树木还是小绿人,对你来说都不重要。
顺便说一句,不存在 root() 函数这样的东西。所有 STL 容器都有 begin() 函数来实现容器的概念开始。该函数返回的迭代器类型取决于容器的特性。