Re: Free STL compatible C++ tree container

Discussion in 'C++' started by Luca Risolia, Aug 8, 2012.

  1. Luca Risolia

    Luca Risolia Guest

    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, Aug 8, 2012
    #1
    1. Advertising

  2. Luca Risolia <> 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.
    Juha Nieminen, Aug 8, 2012
    #2
    1. Advertising

  3. Luca Risolia

    Luca Risolia Guest

    On 08/08/2012 18:02, Juha Nieminen wrote:
    > Luca Risolia <> 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.
    Luca Risolia, Aug 8, 2012
    #3
  4. Luca Risolia

    Luca Risolia Guest

    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, Aug 9, 2012
    #4
  5. Luca Risolia <> 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.
    Juha Nieminen, Aug 9, 2012
    #5
  6. Luca Risolia

    Luca Risolia Guest

    On 09/08/2012 07:55, Juha Nieminen wrote:
    > Luca Risolia <> 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..)
    Luca Risolia, Aug 9, 2012
    #6
  7. Luca Risolia

    Luca Risolia Guest

    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))
    Luca Risolia, Aug 9, 2012
    #7
  8. Luca Risolia

    Luca Risolia Guest

    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.
    Luca Risolia, Aug 9, 2012
    #8
  9. Luca Risolia

    Luca Risolia Guest

    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.
    Luca Risolia, Aug 9, 2012
    #9
  10. Luca Risolia

    Luca Risolia Guest

    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.
    Luca Risolia, Aug 9, 2012
    #10
  11. Luca Risolia <> 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.
    Juha Nieminen, Aug 10, 2012
    #11
  12. Luca Risolia <> 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.
    Juha Nieminen, Aug 10, 2012
    #12
  13. Luca Risolia

    Luca Risolia Guest

    On 10/08/2012 07:34, Juha Nieminen wrote:
    > Luca Risolia <> 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, Aug 11, 2012
    #13
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    4
    Views:
    783
    Daniel T.
    Feb 16, 2006
  2. Nordlöw
    Replies:
    2
    Views:
    787
    Marcel Müller
    Apr 16, 2008
  3. Juha Nieminen
    Replies:
    0
    Views:
    382
    Juha Nieminen
    Aug 7, 2012
  4. TDH1978
    Replies:
    6
    Views:
    603
    TDH1978
    Aug 10, 2012
  5. Ansel
    Replies:
    1
    Views:
    392
    Juha Nieminen
    Aug 16, 2012
Loading...

Share This Page