title: How to make a tree in C++?
body: <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>