Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Free STL compatible C++ tree container
309 views
Skip to first unread message
Leigh Johnston
Aug 7, 2012, 1:14:33 PM8/7/12
to
Hi,
I present a free to use/modify C++ "tree" container that is so named
because it can represent a general hierarchical collection of elements
using a tree-like structure. Examples of things which use such general
tree-like structures include file systems, XML elements in an XML
document or the items in a GUI tree control or menu. The C++ Standard
Library includes containers which use a binary (2-ary) search tree as
their underlying data structure (std::set, std::multiset, std::map and
std::multimap) but their interfaces are designed for accessing the
elements as an ordered sequence of elements with no hierarchy and do not
provide direct access to the underlying tree data structure; tree on the
other hand provides an interface for accessing the (non-fixed-ary) tree
directly allowing siblings to be iterated, parent elements to be
determined etc.
http://i42.co.uk/stuff/tree.htm
/Leigh
I present a free to use/modify C++ "tree" container that is so named
because it can represent a general hierarchical collection of elements
using a tree-like structure. Examples of things which use such general
tree-like structures include file systems, XML elements in an XML
document or the items in a GUI tree control or menu. The C++ Standard
Library includes containers which use a binary (2-ary) search tree as
their underlying data structure (std::set, std::multiset, std::map and
std::multimap) but their interfaces are designed for accessing the
elements as an ordered sequence of elements with no hierarchy and do not
provide direct access to the underlying tree data structure; tree on the
other hand provides an interface for accessing the (non-fixed-ary) tree
directly allowing siblings to be iterated, parent elements to be
determined etc.
http://i42.co.uk/stuff/tree.htm
/Leigh
Juha Nieminen
Aug 7, 2012, 3:48:51 PM8/7/12
to
Leigh Johnston <le...@i42.co.uk> wrote:
> http://i42.co.uk/stuff/tree.htm
Btw, an optimization commonly used in STL implementations with regards
to the assign() function of most data containers (especially those that
allocate individual elements) is to reuse existing elements while
assigning, rather than first clearing the entire data container and
then inserting the elements.
In other words, when assigning (with the assign() member function),
the input values are assigned to any existing elements of the container.
If the container had less elements than what is being assigned, the rest
are then inserted to the end normally, and it had more, the extra is
removed normally.
This has the obvious advantage that the amount of allocations and
deallocations is minimized, making the assignment faster (and reducing
memory fragmentation).
> http://i42.co.uk/stuff/tree.htm
Btw, an optimization commonly used in STL implementations with regards
to the assign() function of most data containers (especially those that
allocate individual elements) is to reuse existing elements while
assigning, rather than first clearing the entire data container and
then inserting the elements.
In other words, when assigning (with the assign() member function),
the input values are assigned to any existing elements of the container.
If the container had less elements than what is being assigned, the rest
are then inserted to the end normally, and it had more, the extra is
removed normally.
This has the obvious advantage that the amount of allocations and
deallocations is minimized, making the assignment faster (and reducing
memory fragmentation).
Leigh Johnston
Aug 7, 2012, 4:06:33 PM8/7/12
to
That optimization would not be suitable (or trivial) for this tree data
structure as the common use-case would be to not have a sequential list
of elements which as far as I can tell the said optimization requires.
It would require a lot of faffing about with node pointers to work and
would not be worth the effort IMO.
/Leigh
Luca Risolia
Aug 8, 2012, 1:59:26 AM8/8/12
to
sort the contained elements. The type of the functor is a template
parameter and is std::less<T> by default, which only requires a suitable
operator<() to be defined for T, where T is the type of the elements.
With regard to your tree, not only it does not specify any template
parameter as "comparator", but, if I am not wrong, somewhere it
internally uses operator==() to compare the elements, which turns out to
be a superfluous (and maybe erroneous from the std point of view)
requirement for T, since given two elements e1, e2, then instead of (e1
== e2) you can (or should) write !(e1 < e2) && !(e2 < e1). There are
less evident reasons why the use of operator<() has been preferred to
operator==(), but is another issue.
I think you should also document what kind of guarantees the tree
iterators give to the user after the tree has been modified with one of
its operations.
Juha Nieminen
Aug 8, 2012, 12:02:08 PM8/8/12
to
Luca Risolia <luca.r...@studio.unibo.it> wrote:
> With regard to your tree, not only it does not specify any template
> parameter as "comparator", but, if I am not wrong, somewhere it
> internally uses operator==() to compare the elements, which turns out to
> be a superfluous (and maybe erroneous from the std point of view)
> requirement for T, since given two elements e1, e2, then instead of (e1
> == e2) you can (or should) write !(e1 < e2) && !(e2 < e1). There are
> less evident reasons why the use of operator<() has been preferred to
> operator==(), but is another issue.
If the data container does not require operator<() but does require
> With regard to your tree, not only it does not specify any template
> parameter as "comparator", but, if I am not wrong, somewhere it
> internally uses operator==() to compare the elements, which turns out to
> be a superfluous (and maybe erroneous from the std point of view)
> requirement for T, since given two elements e1, e2, then instead of (e1
> == e2) you can (or should) write !(e1 < e2) && !(e2 < e1). There are
> less evident reasons why the use of operator<() has been preferred to
> operator==(), but is another issue.
comparing for equality, it should definitely use operator==() instead
of operator<().
There are many data types for which there's no sensible or simple way of
implementing operator<(), but for which operator==() is trivial. (The
opposite is highly unlikely.) Requiring operator<() for anything that's
not sorted doesn't make sense.
Luca Risolia
Aug 8, 2012, 2:34:10 PM8/8/12
to
container. Standard containers do NOT require and use operator==() to
compare elements. The test that they do is:
!comp(e1, e2) && !(e2, e1) // or operator<() by default, essentially
They are based on the assumption that equivalent elements do not need to
be equal.
Using operator==() for the tree proposed by the OP to find elements, for
example, would break the semantic behind the standard. A type suitable
for standard associative containers might not work as expected with that
tree.
I also don't think that implementing operator<() is harder than
implementing operator==(). It depends on the real case. For sure, once
you provide operator<() to your type, then that type will work by
default (without any modification) with all the standard containers.
Leigh Johnston
Aug 8, 2012, 6:39:54 PM8/8/12
to
First, please try reading code properly before posting erroneous
comments about it.
Second, the container is not a *search* tree so does not have a class
template parameter for a comparator.
Third, the container has a sort member function which uses std::less as
a default comparator type so I have no idea where you are getting this
operator== nonsense from.
/Leigh
Luca Risolia
Aug 8, 2012, 9:17:42 PM8/8/12
to
> Second, the container is not a *search* tree so does not have a class
> template parameter for a comparator.
>
> Third, the container has a sort member function which uses std::less as
> a default comparator type so I have no idea where you are getting this
> operator== nonsense from.
void remove(parameter_type value, bool multiple = true)
{
for (iterator i = begin(); i != end(); )
{
if (*i == value)
^^^^^^^^^^^^^^^^
Why do you need operator==() to remove an element from a Tree?
Take std::map or std::set as examples. They provide:
size_type erase ( const key_type& x );
(which basically also removes an element from the underlying tree.)
They do not need operator==() to be defined for comparing the contained
elements.
To see what kind of problems using operator==() might give, try the
following by yourself: define a type String with both operator<(const
String&, const String&) that uses case-insensitive comparison, and
operator operator==(const String&, const String&) that uses
case-sensitive comparison as its comparison criteria. (After all, it
seems reasonable for a String.) Well, now try to insert the element
String("ELEMENT") in both a std::set and your Tree, then call erase or
remove("element") on both: the std::set will be empty while your Tree
will not.
In other words, if you claim your Tree is "STL-compatible", I also
expect that the standard semantic is preserved with regard to some basic
operations, so that any types that "work" with the standard containers
would also work with your Tree.
Juha Nieminen
Aug 9, 2012, 1:55:09 AM8/9/12
to
Luca Risolia <luca.r...@studio.unibo.it> wrote:
> The OP proposed his tree data structure as a STL- *compatible*
> container. Standard containers do NOT require and use operator==() to
> compare elements.
Can you tell me which one of the standard containers uses operator<() for
> The OP proposed his tree data structure as a STL- *compatible*
> container. Standard containers do NOT require and use operator==() to
> compare elements.
comparing for equality only, but not for ordering the elements (because
it's an unordered container)?
There aren't any.
The idea is that ordered containers (namely std::set, std::map and their
multi-variants) already require operator<() in order to function at all
because, by definition, they must be able to sort the elements. And since
operator<() can also be used for equality comparison, they use it so as
to not increase the demands for the elements. Also algorithms that require
both operator<() and comparing for equality do not require operator==()
because the latter is not needed when the former is already a requirement.
However, standard algorithms that do *not* require operator<() but *do*
require comparing for equality use operator==(). It would make no sense
for them to do otherwise. It would be nonsensical for eg. std::find() to
require operator<() when it does not work on sorted ranges. It only
requires equality comparisons, and hence operator==().
You are confusing the ideology that a container should require as little
as possible from its elements. The ordered containers and algorithms that
operate on ordered ranges only require operator<() because they need it
anyways to operate properly, and requiring operator==() in addition to
that is superfluous. However, algorithms that require only equality
comparison require operator==() and *not* operator<(), because the former
is much more common and simpler.
Requiring operator<() for equality comparison only, in an unordered data
container, is nonsensical.
Luca Risolia
Aug 9, 2012, 3:07:23 AM8/9/12
to
not talking about any algorithm. I am talking about the Tree data
structure written by the OP and its basic operations: I have given an
example to the author showing what might be the problem in one point of
the code: take a type T supporting both operator==() and operator<() and
insert the same elements of type T in both a std::set and a Tree. If you
look at the implementation of tree::remove(), you will notice it uses
operator==() to compare the elements, instead of operator<(), which is
used by set::erase(). Now try remove the same elements one by one from
both the containers. Since tree::remove() and set::erase actually have
different semantic because of the use of a different operator/criteria
for the comparison, the containers might end up containing different
elements after each removal! Sorry, but I don't think that the Tree can
be said to be "STL-compatible". I expect that removing one element will
produce the same result wherever the element is (in a set, in a map or
in a Tree..)
Leigh Johnston
Aug 9, 2012, 9:29:55 AM8/9/12
to
The container is STL compatible.
Again the container is not a *search* tree; it is an unordered container
so requiring element operator== for 'neolib::tree::remove' is correct in
the same way that 'std::list::remove' requires element operator==.
'std::set' is an ordered container so any comparisons with
'neolib::tree' are false.
I have however added a 'remove_if' member function to tree.
/Leigh
Leigh Johnston
Aug 9, 2012, 9:41:14 AM8/9/12
to
ordered container.
/Leigh
Luca Risolia
Aug 9, 2012, 9:53:13 AM8/9/12
to
iterator erase ( iterator position );
like std::list, or std:.deque
rather than
size_type erase ( const key_type& x );
(unordered_map's can have the latter because they retrieve the value in
O(C))
Luca Risolia
Aug 9, 2012, 9:59:59 AM8/9/12
to
On 09/08/2012 15:41, Leigh Johnston wrote:
>> I think you don't understand the point. Let me be more concrete. I am
>> not talking about any algorithm. I am talking about the Tree data
>> structure written by the OP and its basic operations: I have given an
>> example to the author showing what might be the problem in one point of
>> the code: take a type T supporting both operator==() and operator<() and
>> insert the same elements of type T in both a std::set and a Tree. If you
>> look at the implementation of tree::remove(), you will notice it uses
>> operator==() to compare the elements, instead of operator<(), which is
>> used by set::erase(). Now try remove the same elements one by one from
>> both the containers. Since tree::remove() and set::erase actually have
>> different semantic because of the use of a different operator/criteria
>> for the comparison, the containers might end up containing different
>> elements after each removal! Sorry, but I don't think that the Tree can
>> be said to be "STL-compatible". I expect that removing one element will
>> produce the same result wherever the element is (in a set, in a map or
>> in a Tree..)
>
> You are simply wrong; tree is an unordered container; std::set is an
> ordered container.
Then provide iterator erase ( iterator position ); instead of
>> I think you don't understand the point. Let me be more concrete. I am
>> not talking about any algorithm. I am talking about the Tree data
>> structure written by the OP and its basic operations: I have given an
>> example to the author showing what might be the problem in one point of
>> the code: take a type T supporting both operator==() and operator<() and
>> insert the same elements of type T in both a std::set and a Tree. If you
>> look at the implementation of tree::remove(), you will notice it uses
>> operator==() to compare the elements, instead of operator<(), which is
>> used by set::erase(). Now try remove the same elements one by one from
>> both the containers. Since tree::remove() and set::erase actually have
>> different semantic because of the use of a different operator/criteria
>> for the comparison, the containers might end up containing different
>> elements after each removal! Sorry, but I don't think that the Tree can
>> be said to be "STL-compatible". I expect that removing one element will
>> produce the same result wherever the element is (in a set, in a map or
>> in a Tree..)
>
> You are simply wrong; tree is an unordered container; std::set is an
> ordered container.
iterator erase ( const key_type& ); . It would be misleading.
list,deques,vectors don't have the latter for some good reasons after all.
Leigh Johnston
Aug 9, 2012, 10:03:08 AM8/9/12
to
code. The 'erase' member function of tree does take an iterator; not a
"key"; there isn't even a "key_type" typedef in the class.
THINK BEFORE POSTING.
/Leigh
Leigh Johnston
Aug 9, 2012, 10:03:36 AM8/9/12
to
Luca Risolia
Aug 9, 2012, 10:29:44 AM8/9/12
to
On 09/08/2012 16:03, Leigh Johnston wrote:
>>> I have however added a 'remove_if' member function to tree.
>>
>> For your "unordered tree" I would provide:
>>
>> iterator erase ( iterator position );
>>
>> like std::list, or std:.deque
>>
>> rather than
>>
>> size_type erase ( const key_type& x );
>>
>> like std::map, or std::set.
>>
>> (unordered_map's can have the latter because they retrieve the value in
>> O(C))
>
> Again you are posting erroneous comments without even looking at the
> code. The 'erase' member function of tree does take an iterator; not a
> "key"; there isn't even a "key_type" typedef in the class.
>
> THINK BEFORE POSTING.
I give up. I would never claim "STL-compatible" a tree which does not
>>> I have however added a 'remove_if' member function to tree.
>>
>> For your "unordered tree" I would provide:
>>
>> iterator erase ( iterator position );
>>
>> like std::list, or std:.deque
>>
>> rather than
>>
>> size_type erase ( const key_type& x );
>>
>> like std::map, or std::set.
>>
>> (unordered_map's can have the latter because they retrieve the value in
>> O(C))
>
> Again you are posting erroneous comments without even looking at the
> code. The 'erase' member function of tree does take an iterator; not a
> "key"; there isn't even a "key_type" typedef in the class.
>
> THINK BEFORE POSTING.
make clear through its interface how the elements will be inserted,
retrieved or removed.. I would never use an "unordered tree" (whatever
it means) which does not give a way to remove its elements in COSTANT
TIME via an iterator pointing to the element. I would never use a
container which provides a method to remove an element by specifying its
value in linear time. It's just misleading and non-standard: lists,
deques, and vectors don't give any way to remove an element by value for
a very obvious reason, and with regard to unordered_maps (or hash maps)
it's at least evident from the interface how they will behave and what
guarantees they can give.
Leigh Johnston
Aug 9, 2012, 11:05:26 AM8/9/12
to
takes an iterator providing constant time element removal. tree
provides 'remove' and 'remove_if' member functions just like std::list
does; presumably you never use std::list because std::list provides a
member function to remove an element by specifying its value in linear time.
Again: THINK BEFORE POSTING.
/Leigh
Luca Risolia
Aug 9, 2012, 11:26:39 AM8/9/12
to
even notice erase() as public member function. For some reasons the term
"tree" confused me from the beginning.
Now I see you said that in your page " tree *on the other hand* is an
unordered container that provides an interface for accessing the
(non-fixed-ary) tree directly allowing siblings to be iterated, parent
elements to be determined etc."
Sorry for the noise.
elements to be determined etc."
Leigh Johnston
Aug 9, 2012, 11:33:58 AM8/9/12
to
/Leigh
Message has been deleted
Leigh Johnston
Aug 9, 2012, 5:07:51 PM8/9/12
to
On 09/08/2012 21:58, TDH1978 wrote:
> Thank you for developing and sharing this code. I have one question.
> Trees are usually traversed in either pre-order, post-order, or
> in-order. During traversal, an action can be taken at each node (via
> callbacks, for example). Given your interface, how would I traverse an
> entire tree without having to write multiple nested loops?
>
> To give you an example of someone who has done similar stuff, with
> traversal iterators (supporting all three traversal methods):
> http://tree.phi-sci.com/
> http://tree.phi-sci.com/tree.pdf
>
Hi,
There are currently two iterator types: pre-order (iterator) and sibling
(sibling_iterator); so to iterate the entire tree without nested loops
use the pre-order iterators but please note 'tree' is *not* a search tree.
/Leigh
> Trees are usually traversed in either pre-order, post-order, or
> in-order. During traversal, an action can be taken at each node (via
> callbacks, for example). Given your interface, how would I traverse an
> entire tree without having to write multiple nested loops?
>
> To give you an example of someone who has done similar stuff, with
> traversal iterators (supporting all three traversal methods):
> http://tree.phi-sci.com/
> http://tree.phi-sci.com/tree.pdf
>
Hi,
There are currently two iterator types: pre-order (iterator) and sibling
(sibling_iterator); so to iterate the entire tree without nested loops
use the pre-order iterators but please note 'tree' is *not* a search tree.
/Leigh
Message has been deleted
Leigh Johnston
Aug 9, 2012, 5:27:47 PM8/9/12
to
On 09/08/2012 22:21, TDH1978 wrote:
> your tree structure is not optimized for searching?
I mean it is an unordered container not an ordered container like
std::set which is implemented using a binary search tree.
/Leigh
> On 2012-08-09 21:07:51 +0000, Leigh Johnston said:
>
>> There are currently two iterator types: pre-order (iterator) and
>> sibling (sibling_iterator); so to iterate the entire tree without
>> nested loops use the pre-order iterators but please note 'tree' is
>> *not* a search tree.
>
> Can you please tell me what you mean by "search" tree. Do you mean that
>
>> There are currently two iterator types: pre-order (iterator) and
>> sibling (sibling_iterator); so to iterate the entire tree without
>> nested loops use the pre-order iterators but please note 'tree' is
>> *not* a search tree.
>
> your tree structure is not optimized for searching?
I mean it is an unordered container not an ordered container like
std::set which is implemented using a binary search tree.
/Leigh
Message has been deleted
Luca Risolia
Aug 9, 2012, 8:37:32 PM8/9/12
to
On 09/08/2012 23:50, TDH1978 wrote:
> I will try out your code in the next project that requires a tree
> container. If by then you have not added post-order and in-order
> traversal, I will add them myself and send you the patch via your website.
If you are interested in another kind of tree or in a tree with an
in-order iterator, sometime ago I implemented a SplayTree (an ordered
container this time) offering an in-order Input, const_iterator. I used
the SplayTree as a base for a simple HashMap based on linear hashing:
http://www.linux-projects.org/listing/cpp_solutions/17.28/SplayTree.h
> I will try out your code in the next project that requires a tree
> container. If by then you have not added post-order and in-order
> traversal, I will add them myself and send you the patch via your website.
If you are interested in another kind of tree or in a tree with an
in-order iterator, sometime ago I implemented a SplayTree (an ordered
container this time) offering an in-order Input, const_iterator. I used
the SplayTree as a base for a simple HashMap based on linear hashing:
http://www.linux-projects.org/listing/cpp_solutions/17.28/SplayTree.h
Juha Nieminen
Aug 10, 2012, 1:31:26 AM8/10/12
to
Luca Risolia <luca.r...@studio.unibo.it> wrote:
> I think you don't understand the point. Let me be more concrete. I am
> not talking about any algorithm. I am talking about the Tree data
> structure written by the OP and its basic operations: I have given an
> example to the author showing what might be the problem in one point of
> the code: take a type T supporting both operator==() and operator<() and
> insert the same elements of type T in both a std::set and a Tree. If you
> look at the implementation of tree::remove(), you will notice it uses
> operator==() to compare the elements, instead of operator<(), which is
> used by set::erase(). Now try remove the same elements one by one from
> both the containers. Since tree::remove() and set::erase actually have
> different semantic because of the use of a different operator/criteria
> for the comparison, the containers might end up containing different
> elements after each removal! Sorry, but I don't think that the Tree can
> be said to be "STL-compatible". I expect that removing one element will
> produce the same result wherever the element is (in a set, in a map or
> in a Tree..)
By that rationale eg. std::list::unique should use operator<() instead of
> I think you don't understand the point. Let me be more concrete. I am
> not talking about any algorithm. I am talking about the Tree data
> structure written by the OP and its basic operations: I have given an
> example to the author showing what might be the problem in one point of
> the code: take a type T supporting both operator==() and operator<() and
> insert the same elements of type T in both a std::set and a Tree. If you
> look at the implementation of tree::remove(), you will notice it uses
> operator==() to compare the elements, instead of operator<(), which is
> used by set::erase(). Now try remove the same elements one by one from
> both the containers. Since tree::remove() and set::erase actually have
> different semantic because of the use of a different operator/criteria
> for the comparison, the containers might end up containing different
> elements after each removal! Sorry, but I don't think that the Tree can
> be said to be "STL-compatible". I expect that removing one element will
> produce the same result wherever the element is (in a set, in a map or
> in a Tree..)
operator==(). Does it? No.
If the data container is not ordered, requiring operator<() does not make
any sense.
Juha Nieminen
Aug 10, 2012, 1:34:57 AM8/10/12
to
Luca Risolia <luca.r...@studio.unibo.it> wrote:
> I give up. I would never claim "STL-compatible" a tree which does not
> make clear through its interface how the elements will be inserted,
> retrieved or removed.. I would never use an "unordered tree" (whatever
> it means)
What makes you think that tree data structures must be ordered? There's
> I give up. I would never claim "STL-compatible" a tree which does not
> make clear through its interface how the elements will be inserted,
> retrieved or removed.. I would never use an "unordered tree" (whatever
> it means)
nothing in the concept of a tree that requires ordering.
An ordered search tree is a *special case* of a tree data structure.
It's not the norm.
Tobias Müller
Aug 10, 2012, 2:05:28 AM8/10/12
to
TDH1978 <thedeerh...@movie.uni> wrote:
> I will try out your code in the next project that requires a tree
> container. If by then you have not added post-order and in-order
> traversal, I will add them myself and send you the patch via your website.
How would you define in-order traversal on a unordered non-binary tree?
> I will try out your code in the next project that requires a tree
> container. If by then you have not added post-order and in-order
> traversal, I will add them myself and send you the patch via your website.
/Tobi
Melzzzzz
Aug 10, 2012, 2:17:49 PM8/10/12
to
On Thu, 9 Aug 2012 17:21:25 -0400
TDH1978 <thedeerh...@movie.uni> wrote:
> On 2012-08-09 21:07:51 +0000, Leigh Johnston said:
>
TDH1978 <thedeerh...@movie.uni> wrote:
> On 2012-08-09 21:07:51 +0000, Leigh Johnston said:
>
> > There are currently two iterator types: pre-order (iterator) and
> > sibling (sibling_iterator); so to iterate the entire tree without
> > nested loops use the pre-order iterators but please note 'tree' is
> > *not* a search tree.
>
> > sibling (sibling_iterator); so to iterate the entire tree without
> > nested loops use the pre-order iterators but please note 'tree' is
> > *not* a search tree.
>
> Can you please tell me what you mean by "search" tree. Do you mean
> that your tree structure is not optimized for searching?
>
I think he means that tree is not sorted.
> that your tree structure is not optimized for searching?
>
Message has been deleted
Luca Risolia
Aug 11, 2012, 6:22:04 AM8/11/12
to
On 10/08/2012 07:34, Juha Nieminen wrote:
> Luca Risolia <luca.r...@studio.unibo.it> wrote:
>> I give up. I would never claim "STL-compatible" a tree which does not
>> make clear through its interface how the elements will be inserted,
>> retrieved or removed.. I would never use an "unordered tree" (whatever
>> it means)
>
> What makes you think that tree data structures must be ordered? There's
> nothing in the concept of a tree that requires ordering.
Yes, you are correct.
> Luca Risolia <luca.r...@studio.unibo.it> wrote:
>> I give up. I would never claim "STL-compatible" a tree which does not
>> make clear through its interface how the elements will be inserted,
>> retrieved or removed.. I would never use an "unordered tree" (whatever
>> it means)
>
> What makes you think that tree data structures must be ordered? There's
> nothing in the concept of a tree that requires ordering.
Ansel
Aug 15, 2012, 6:12:16 AM8/15/12
to
Leigh Johnston wrote:
> Hi,
on the following webpage (?):
http://en.wikipedia.org/wiki/List_of_data_structures
> The C++
> Standard Library includes containers which use a binary (2-ary)
> search tree as their underlying data structure (std::set,
> std::multiset, std::map and std::multimap) but their interfaces are
> designed for accessing the elements as an ordered sequence of
> elements with no hierarchy and do not provide direct access to the
> underlying tree data structure; tree on the other hand provides an
> interface for accessing the (non-fixed-ary) tree directly allowing
> siblings to be iterated, parent elements to be determined etc.
>
> http://i42.co.uk/stuff/tree.htm
>
> /Leigh
> Hi,
>
> I present a free to use/modify C++ "tree" container that is so named
> because it can represent a general hierarchical collection of elements
> using a tree-like structure. Examples of things which use such
> general tree-like structures include file systems, XML elements in an
> XML document or the items in a GUI tree control or menu.
Or the Windows registry? What is the name for such a data structure? Is it
> I present a free to use/modify C++ "tree" container that is so named
> because it can represent a general hierarchical collection of elements
> using a tree-like structure. Examples of things which use such
> general tree-like structures include file systems, XML elements in an
> XML document or the items in a GUI tree control or menu.
on the following webpage (?):
http://en.wikipedia.org/wiki/List_of_data_structures
> The C++
> Standard Library includes containers which use a binary (2-ary)
> search tree as their underlying data structure (std::set,
> std::multiset, std::map and std::multimap) but their interfaces are
> designed for accessing the elements as an ordered sequence of
> elements with no hierarchy and do not provide direct access to the
> underlying tree data structure; tree on the other hand provides an
> interface for accessing the (non-fixed-ary) tree directly allowing
> siblings to be iterated, parent elements to be determined etc.
>
>
> /Leigh
Juha Nieminen
Aug 16, 2012, 1:21:11 AM8/16/12
to
A tree.
0 new messages