如何在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似乎正是我想要的。

If this is for gaining the benefit of
  a data-structure holding arbitrary
  index types, optimized for searching
  and good at insertion then consider
  using a map.
  
  A map is an associative container that
  has performance guarantees identical
  to those of a tree: logarithmic
  searching, logarithmic insertion,
  logarithmic deletion, linear space.
  Internally they are often implemented
  as red-black trees, although that is
  not a guarantee. Still, as an STL user
  all you should care about is the
  performance guarantees of the STL
  algorithms and data-structures.
  Whether they're implemented as trees
  or little green men shouldn't matter
  to you.

我不确定是否需要地图，但谢谢我们提供的信息。我会记住，只要有可能就使用地图，而不要使用树。

解决方案

回答

你为什么想这么做？如果这是出于学习目的，那么我们可以编写自己的树数据结构。如果这样做是为了获得拥有任意索引类型的数据结构的好处，该索引结构针对搜索进行了优化并且擅长插入，则可以考虑使用映射。

地图是具有与树相同的性能保证的关联容器：对数搜索，对数插入，对数删除，线性空间。在内部，它们通常被实现为红黑树，尽管这不能保证。尽管如此，作为STL用户，我们应该关心的是STL算法和数据结构的性能保证。无论是将它们实施为树木还是矮小的绿色男人，对我们而言都无关紧要。

作为附带说明，没有root()函数之类的东西。所有STL容器都具有begin()函数，用于实现容器的概念上的开头。该函数返回的迭代器的类型取决于容器的特性。

回答

这是tree.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;
         }
      }
   }

现在有什么不同？实现更简单
将一个节点添加到树上。
尽管版本要简单得多，但是此lib的开发人员可能希望在不浏览树的情况下就可以访问一些信息，例如树的大小。

我还假设他出于性能原因不希望将根存储在所有节点上。
因此，如果我们想以自己的方式实现它，建议我们保留大部分逻辑，并在迭代器中将链接添加到父树，然后重写一下。