<p>How do I make a tree data structure in C++ that uses iterators instead of pointers?  I couldn't find anything in the STL that can do this.  What I would like to do is to be able to create and manipulate trees like this:</p>

<pre><code>#include &lt;iostream&gt;
#include &lt;tree&gt;
using namespace std;

int main()
{
    tree&lt;int&gt; myTree;

    tree&lt;int&gt;::iterator i = myTree.root();
    *i = 42;

    tree&lt;int&gt;::iterator j = i.add_child();
    *j = 777;
    j = j.parent();

    if (i == myTree.root() &amp;&amp; i == j) cout &lt;&lt; "i and j are both pointing to the root\n";

    return 0;
}
</code></pre>

<hr>

<p>Thank you, tree.hh seems to be just what I was looking for.</p>

<blockquote>
  <p>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.</p>
  
  <p>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.</p>
</blockquote>

<p>I'm not sure if a map is what I need, but thanks for the info.  I will remember to use maps whenever possible instead of implementing trees.</p>

[{'answer_id': 19204, 'author': 'wilhelmtell', 'author_id': 456, 'author_profile': 'https://Stackoverflow.com/users/456', 'pm_score': 2, 'selected': False, 'text': "<p>Why would you want to do that?  If this is for learning purposes then you can write your own tree data structure.  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.</p>\n\n<p>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.</p>\n\n<p>As a side note, there's no such thing as a root() function.  All STL containers have the begin() function implementing the conceptual beginning of a container.  The kind of iterator returned by that function depends on the characteristics of the container.</p>\n"}, {'answer_id': 19255, 'author': 'fulmicoton', 'author_id': 446497, 'author_profile': 'https://Stackoverflow.com/users/446497', 'pm_score': 4, 'selected': True, 'text': '<p>Here is <a href="http://www.aei.mpg.de/~peekas/tree/" rel="noreferrer">tree.hh</a>  which is a bit close to what you want to do, though a bit\ndifferent.</p>\n\n<p>Here is a piece of code extracted from its website.</p>\n\n<pre><code>int main(int, char **)\n   {\n   tree&lt;string&gt; tr;\n   tree&lt;string&gt;::iterator top, one, two, loc, banana;\n\n   top=tr.begin();\n   one=tr.insert(top, "one");\n   two=tr.append_child(one, "two");\n   tr.append_child(two, "apple");\n   banana=tr.append_child(two, "banana");\n   tr.append_child(banana,"cherry");\n   tr.append_child(two, "peach");\n   tr.append_child(one,"three");\n\n   loc=find(tr.begin(), tr.end(), "two");\n   if(loc!=tr.end()) {\n      tree&lt;string&gt;::sibling_iterator sib=tr.begin(loc);\n      while(sib!=tr.end(loc)) {\n         cout &lt;&lt; (*sib) &lt;&lt; endl;\n         ++sib;\n         }\n      cout &lt;&lt; endl;\n      tree&lt;string&gt;::iterator sib2=tr.begin(loc);\n      tree&lt;string&gt;::iterator end2=tr.end(loc);\n      while(sib2!=end2) {\n         for(int i=0; i&lt;tr.depth(sib2)-2; ++i) \n            cout &lt;&lt; " ";\n         cout &lt;&lt; (*sib2) &lt;&lt; endl;\n         ++sib2;\n         }\n      }\n   }\n</code></pre>\n\n<p>Now what\'s different? Your implementation is simpler when it comes to \nappend a node to the tree. \nThough your version is indiscutably simpler, the dev of this lib probably wanted to have some info accessible without browsing the tree, such as the size of the tree for instance.</p>\n\n<p>I also assume he didn\'t want to store the root on all nodes for performance reason.\nSo if you want to implement it your way, I suggest you keep most of the logic and add the link to the parent tree in the iterator and rewrite append a bit.</p>\n'}]
['https://Stackoverflow.com/questions/19193', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/2222/']