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

Leigh Johnston <leigh@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).

On 07/08/2012 20:48, Juha Nieminen wrote:
> Leigh Johnston <leigh@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).

Thanks for you comment.

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

On 07/08/2012 19:14, Leigh Johnston wrote:
> 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.

Standard containers usually need a comparison function or a functor 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.

Luca Risolia <luca.risolia@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
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.

On 08/08/2012 18:02, Juha Nieminen wrote:
> Luca Risolia <luca.risolia@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
> 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.

The OP proposed his tree data structure as a STL- *compatible* 
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.

On 08/08/2012 06:59, Luca Risolia wrote:
> On 07/08/2012 19:14, Leigh Johnston wrote:
>> 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.
>
> Standard containers usually need a comparison function or a functor 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.

Hi,

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

On 09/08/2012 00:39, Leigh Johnston wrote:
> On 08/08/2012 06:59, Luca Risolia wrote:
>> On 07/08/2012 19:14, Leigh Johnston wrote:
>>> 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.
>>
>> Standard containers usually need a comparison function or a functor 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.
>
> Hi,
>
> First, please try reading code properly before posting erroneous
> comments about it.

I have read it. I have tried it as well.

> 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.

Here is one requirement for operator==() in your code:

		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.

Luca Risolia <luca.risolia@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
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.

On 09/08/2012 07:55, Juha Nieminen wrote:
> Luca Risolia <luca.risolia@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
> 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.

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..)

On 09/08/2012 02:17, Luca Risolia wrote:
> On 09/08/2012 00:39, Leigh Johnston wrote:
>> On 08/08/2012 06:59, Luca Risolia wrote:
>>> On 07/08/2012 19:14, Leigh Johnston wrote:
>>>> 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.
>>>
>>> Standard containers usually need a comparison function or a functor 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.
>>
>> Hi,
>>
>> First, please try reading code properly before posting erroneous
>> comments about it.
>
> I have read it. I have tried it as well.
>
>> 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.
>
> Here is one requirement for operator==() in your code:
>
>          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.

You did not read my reply.

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

On 09/08/2012 08:07, Luca Risolia wrote:
> On 09/08/2012 07:55, Juha Nieminen wrote:
>> Luca Risolia <luca.risolia@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
>> 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.
>
> 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.

/Leigh

On 09/08/2012 15:29, Leigh Johnston wrote:
> On 09/08/2012 02:17, Luca Risolia wrote:
>> On 09/08/2012 00:39, Leigh Johnston wrote:
>>> On 08/08/2012 06:59, Luca Risolia wrote:
>>>> On 07/08/2012 19:14, Leigh Johnston wrote:
>>>>> 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.
>>>>
>>>> Standard containers usually need a comparison function or a functor 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.
>>>
>>> Hi,
>>>
>>> First, please try reading code properly before posting erroneous
>>> comments about it.
>>
>> I have read it. I have tried it as well.
>>
>>> 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.
>>
>> Here is one requirement for operator==() in your code:
>>
>>          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.
>
> You did not read my reply.
>
> 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.

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))

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
iterator erase ( const key_type& ); . It would be misleading. 
list,deques,vectors don't have the latter for some good reasons after all.

On 09/08/2012 14:53, Luca Risolia wrote:
> On 09/08/2012 15:29, Leigh Johnston wrote:
>> On 09/08/2012 02:17, Luca Risolia wrote:
>>> On 09/08/2012 00:39, Leigh Johnston wrote:
>>>> On 08/08/2012 06:59, Luca Risolia wrote:
>>>>> On 07/08/2012 19:14, Leigh Johnston wrote:
>>>>>> 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.
>>>>>
>>>>> Standard containers usually need a comparison function or a functor 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.
>>>>
>>>> Hi,
>>>>
>>>> First, please try reading code properly before posting erroneous
>>>> comments about it.
>>>
>>> I have read it. I have tried it as well.
>>>
>>>> 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.
>>>
>>> Here is one requirement for operator==() in your code:
>>>
>>>          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.
>>
>> You did not read my reply.
>>
>> 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.
>
> 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.

/Leigh

On 09/08/2012 14:59, Luca Risolia wrote:
> 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
> iterator erase ( const key_type& ); . It would be misleading.
> list,deques,vectors don't have the latter for some good reasons after all.

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.

/Leigh

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 
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.

On 09/08/2012 15:29, Luca Risolia wrote:
> 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
> 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.

Again you are wrong.  tree provides an 'erase' member function that 
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

On 09/08/2012 17:05, Leigh Johnston wrote:
> On 09/08/2012 15:29, Luca Risolia wrote:
>> 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
>> 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.
>
> Again you are wrong.  tree provides an 'erase' member function that
> 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.

Okay. My fault, At first I read your code too much quickly and did not 
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.

On 09/08/2012 16:26, Luca Risolia wrote:
> On 09/08/2012 17:05, Leigh Johnston wrote:
>> On 09/08/2012 15:29, Luca Risolia wrote:
>>> 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
>>> 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.
>>
>> Again you are wrong.  tree provides an 'erase' member function that
>> 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.
>
> Okay. My fault, At first I read your code too much quickly and did not
> 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.

I'm glad we got there in the end. :D

/Leigh

On 2012-08-07 17:14:33 +0000, Leigh Johnston said:

> 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.

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

On 09/08/2012 21:58, TDH1978 wrote:
> On 2012-08-07 17:14:33 +0000, Leigh Johnston said:
>
>> 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.
>
> 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

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 your tree structure is not optimized for searching?

On 09/08/2012 22:21, TDH1978 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.
>
> Can you please tell me what you mean by "search" tree.  Do you mean that
> 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:27:47 +0000, Leigh Johnston said:

> I mean it is an unordered container not an ordered container like 
> std::set which is implemented using a binary search tree.

Understood.  About twenty years ago, I had to write my own tree 
container.  At the time, STL did not exist and RogueWave was the C++ 
library king.  RogueWave did not have a tree container but they did 
have dictionaries (similar to STL's map).  To get around the slow tree 
search, I used my tree container in combination with a dictionary.  The 
dictionary would contain the actual node payload and pointers to the 
nodes in the tree.  The tree would contain the relationhip information 
(root, parents, children, siblings) and pointers back to the dictionary 
elements.  The disadvantage of this approach was that the two 
structures had to be kept in sync (making inserts and deletes slower).

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.

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

Luca Risolia <luca.risolia@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
operator==(). Does it? No.

If the data container is not ordered, requiring operator<() does not make
any sense.

Luca Risolia <luca.risolia@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.

An ordered search tree is a *special case* of a tree data structure.
It's not the norm.

On Thu, 9 Aug 2012 17:21:25 -0400
TDH1978 <thedeerhunter1978@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.
> 
> 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.

On 2012-08-10 06:05:28 +0000, Tobias M�ller said:

> How would you define in-order traversal on a unordered non-binary tree?

It's awkward for non-binary trees.  I used to use 
firstchild-parent-child-child-child...

On 10/08/2012 07:34, Juha Nieminen wrote:
> Luca Risolia <luca.risolia@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.

Leigh Johnston wrote:
> 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 
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 

Ansel <tinker454@trytospammenowloser.com> wrote:
> What is the name for such a data structure?

A tree.