Re: Standard iterator model and tree<>
Le Chaud Lapin <jaibuduvin@gmail.com> wrote:
On May 6, 4:55 pm, Seungbeom Kim <musip...@bawi.org> wrote:
This might be a digression, but what's the property in your tree<> class
model that prevents its iterators from conforming to the standard iterator
model that we have now?
I have never used STL so perhaps I am wrong, but it would seem that
applying (++) or (--) to an iterator of a tree<> would not make sense.
There must have been something that the committee members could not agree on
that kept the tree from making it into the standard, but the standard itself
has nothing that keeps trees from being adopted. Map and set are internally
based on trees, already, and they support all the bidirectional iterator
operations; look at the implementation of those trees in your library, such
as _Rb_tree<> and _Rb_tree_iterator<> in the GNU ISO C++ Library, and give a
thought to why your tree<> class cannot do the similar things.
I'd be curious to know what that is. I find it strange that what is
arguably one of the most fundamental data structures used to help with
complex systems is not found in the STL.
a red black tree is one of many self balancing search trees, it
reorders the nodes so the number of generations of children from the
root is almost as small as possible, making the search of a tree with
2^n generations of children of the root take about 2n tests of operator
< to find the data if present.
For search trees iterators make sense because you can get the contents
of the container in a uniform manner.
Direct use of red black tress can be useful, but I have not found any
where the stl's associative containers are not 'good enough'.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]