In article <3B000006.40C0385E@dollywood.itp.tuwien.ac.at>, Christopher
Eltschka <celtschk@dollywood.itp.tuwien.ac.at> wrote:
>> I think that is a rather different containers than the simple variation I
>> have in my mind: I think of a container with essentially the same
>> interface as the std::vector and std::list, but with different
>> complexities.
>>
>> I think one can consider other tree containers as well, but I have not
>> given that much thought.
>
>So I conclude what you want is _not_ a tree, but a _sequence_.
>More exactly, a sequence with O(log n) insertion/deletion and
>O(log n) random access, which happens to be *implementable*
>in terms of a balanced tree.

Right, this is the class I arrived at. (But not the original poster of
this thread has some other ideas, I think.)

>Written this way, it suddenly looks like something one can
>inserted into STL relatively easy. It's just inappropriate to
>call that container "balanced tree", just as it is inappropriate
>to call std::set<> "red-black tree": The tree is an
>implementation detail, nothing else.

Right: There is a whole category of sequence containers, called vector,
singly/doubly linked lists, stack, deque, tree, whatever, that essentially
have the same interface, but only differs in the complexities of the
different operations.

These interfaces differ somewhat in the current C++ library, because one
did not want novice programmers to inadvertently use operations with high
complexities. But I think that is something that should be left to the
programmer to decide, using tools such as profilers.

For example, a forward singly list may not have an iterator decrement
operator, because every decrement must be arrived at any incrementing from
the first link. But in a program that may still be the right thing, if
decrements happen seldom enough.

The tree based sequence container I think of fits into that picture: It
should be easy in an implementation to change the implementation technique
in order to get the right complexities for your program.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

kuehl@ramsen.informatik.uni-konstanz.de (Dietmar Kuehl) dared to utter in
news:9dm0os$8dc$2@news.BelWue.DE:

> Hi,
> Martijn Lievaart (xnews.public.home@bogus.rtij.nl) wrote:
>
>: The same reasoning
>: probably applies here too. I still build my own lists when memory
>: requirements dictate so. The same would hold for trees as far asa I'm
>: concerned.
>
> These are all trade-offs. What is suitable for one party may be
> unsuitable for another one. ... and if we are thinking about a tree

I agree completely. I only wanted to point out that such trade-offs have
been made before, and in my opinion correctly. That does not mean that this
thus also applies to trees, as you originally pointed out there are so many
more issues.

> class in the standard C++ library it should be of general use. IMO the
> best approach to this is to provide the suitable algorithms for dealing
> with tree classes and have the user toss together the appropriate ones
> for the given implementation. That is, no tree class is defined in the
> standard library at all but the necessary concepts and algorithms are.

Interesting line of thought. I seldomly use tree structures because the
interesting ones are relatively hard to build so other solutions are
quickly apealing. If the standard library would help in building custom
tree structures that would be great.

Maybe we could use some traits class here to describe the kind of tree and
have the algorithms adapt accordingly. But here I'm starting to go out of
my league, so I'll leave it to the experts here :-).

Regards,
Martijn Lievaart

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

On Tue, 15 May 2001 17:27:16 GMT, remove.haberg@matematik.su.se (Hans
Aberg) wrote:

> In article <3B000006.40C0385E@dollywood.itp.tuwien.ac.at>, Christopher
> Eltschka <celtschk@dollywood.itp.tuwien.ac.at> wrote:

> >Written this way, it suddenly looks like something one can
> >inserted into STL relatively easy. It's just inappropriate to
> >call that container "balanced tree", just as it is inappropriate
> >to call std::set<> "red-black tree": The tree is an
> >implementation detail, nothing else.

Yes, the performance is all that is required.

> Right: There is a whole category of sequence containers, called vector,
> singly/doubly linked lists, stack, deque, tree, whatever, that essentially
> have the same interface, but only differs in the complexities of the
> different operations.

I have done that kind of container, just for fun.  I never found a use
for it.  I'm talking about the sequence with logN operations.  Can you
give some real uses?  It is basically a sequence with a logN find_pos.
Better than list and worse than vector.  I guess the important part is
that the insert is logN, but why do you want it?

BTW, can you name this thing?  The abstraction, not your assumed
implementation.

John

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <3AFE8640.2B108267@wizard.net>, "James Kuyper Jr."
<kuyper@wizard.net> wrote:

>Hans Aberg wrote:
>...
>> >Radoslav Getov (nospam@mai.com) wrote:
>> >: Add a balanced binary tree container to STL
>...
>> The reason for adding such a container to the C++ library is a reasonable
>> average complexity: For lists, insertion complexity is O(1), whereas for
>> search of index k, k an integer, is O(n) (where n = container size); for
>> an array, it is the opposite.
>> The balanced tree container has both those complexities O(log n).
>
>So does std::map<>.  What advantage does this proposed binary tree
>container have compared with std::map<> that justifies having two
>classes with what will probably be almost identical internals?

Essentially, one gets a std::map where the keys always are sequential
numbers 0, ..., n-1, where n is the container size:

It proves tricky to keep the number sequential in a map when deleting
items. Also, a new std::tree class can optimize somewhat, as it needs not
treat the keys as dynamic data.

>The only advantage I've seen in the proposed class are its improved
>complexity requirements for inserts and deletes, and I'm skeptical about
>the feasibility of meeting those requirements.

The linear lists in a language like Haskell makes search for indices
awfully slow. On the other hand, because of the generality, one could not
expect to flip in std::vector, because it would make inserts unacceptably
slow.

The same problem would occur if one tries to design similar container used
in a great generality.

> This class is essentially
>equivalent to exposing some of the internals of std::map<>, which makes
>about as much sense as exposing the internals of a horse - horses with
>their internals exposed are in danger of getting them damaged, or
>infected, and the same applies here.

On the contrary, the internals are already (almost) available in view of
the std::map class. So one simply wants a class with a proper interface.

>The root(), parent(), left(), and right() functions report relationships
>that should matter only to the code which manages the container, not to
>the code which uses it.

I think that is a rather different containers than the simple variation I
have in my mind: I think of a container with essentially the same
interface as the std::vector and std::list, but with different
complexities.

I think one can consider other tree containers as well, but I have not
given that much thought.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Hans Aberg wrote:
>
> In article <3AFE8640.2B108267@wizard.net>, "James Kuyper Jr."
> <kuyper@wizard.net> wrote:
>
> >Hans Aberg wrote:
> >...
> >> >Radoslav Getov (nospam@mai.com) wrote:
> >> >: Add a balanced binary tree container to STL
> >...
> >> The reason for adding such a container to the C++ library is a reasonable
> >> average complexity: For lists, insertion complexity is O(1), whereas for
> >> search of index k, k an integer, is O(n) (where n = container size); for
> >> an array, it is the opposite.
> >> The balanced tree container has both those complexities O(log n).
> >
> >So does std::map<>.  What advantage does this proposed binary tree
> >container have compared with std::map<> that justifies having two
> >classes with what will probably be almost identical internals?
>
> Essentially, one gets a std::map where the keys always are sequential
> numbers 0, ..., n-1, where n is the container size:
>
> It proves tricky to keep the number sequential in a map when deleting
> items. Also, a new std::tree class can optimize somewhat, as it needs not
> treat the keys as dynamic data.
>
> >The only advantage I've seen in the proposed class are its improved
> >complexity requirements for inserts and deletes, and I'm skeptical about
> >the feasibility of meeting those requirements.
>
> The linear lists in a language like Haskell makes search for indices
> awfully slow. On the other hand, because of the generality, one could not
> expect to flip in std::vector, because it would make inserts unacceptably
> slow.
>
> The same problem would occur if one tries to design similar container used
> in a great generality.
>
> > This class is essentially
> >equivalent to exposing some of the internals of std::map<>, which makes
> >about as much sense as exposing the internals of a horse - horses with
> >their internals exposed are in danger of getting them damaged, or
> >infected, and the same applies here.
>
> On the contrary, the internals are already (almost) available in view of
> the std::map class. So one simply wants a class with a proper interface.
>
> >The root(), parent(), left(), and right() functions report relationships
> >that should matter only to the code which manages the container, not to
> >the code which uses it.
>
> I think that is a rather different containers than the simple variation I
> have in my mind: I think of a container with essentially the same
> interface as the std::vector and std::list, but with different
> complexities.
>
> I think one can consider other tree containers as well, but I have not
> given that much thought.

So I conclude what you want is _not_ a tree, but a _sequence_.
More exactly, a sequence with O(log n) insertion/deletion and
O(log n) random access, which happens to be *implementable*
in terms of a balanced tree.

Written this way, it suddenly looks like something one can
inserted into STL relatively easy. It's just inappropriate to
call that container "balanced tree", just as it is inappropriate
to call std::set<> "red-black tree": The tree is an
implementation detail, nothing else.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

> Add a balanced binary tree container to STL

Awhile ago I wrote a tree template. It meets the requirements for an STL
sequence container and can be used fairly interchangeably with a list (where
a tree is a value at the tree node and a list of children). Sub-trees are
also trees. There is no distinction on leaf nodes (a leaf is simply a tree
with no children). The tree isn't self balancing but I had intended to
implement the primitives (like rotate) as generic functions so you could
balance it easily.

What I did implement was a full suite of iterators on the tree - children,
inorder, preorder, postorder, and parent. All but parent are bi-directional,
and all have the associated [begin, end) STL semantics. I also implemented
an iterator type "fullorder" which is a combination pre- and post-, visiting
each node twice. The fullorder iterator has a method "leading()" which
returns true if this is the first visit (and this node will be revisited if
the iterator continues to be incremented). You can also set leading to
"flip" to the trailing (or back to the leading) side. The iterators track
tree depth during traversal (always relative to the initial construction of
the iterator, although it can be set) - this keeps the notion of depth out
of the tree structure and keeps the time orders low. All of the iterators
can be incremented in amortized constant time (where the traversal of the
entire tree will take O(N) although any single increment/decrement may take
O(d) where d is the depth of the tree). I found this class made things like
formatted XML output trivial:

gen::tree<string> dom;
typedef gen::tree<string>::fullorder_iterator fullorder;

//... fill tree

for (fullorder iter (dom.begin<fullorder>());
        iter != dom.end<fullorder>(); ++iter)
    {
    for (int i = 0; i < iter.depth(); ++i)
        std::cout << "    ";

    std::cout << "<";
    if (!iter.leading()) std::cout << "/";

    std::cout << *iter << ">" << std::endl;
    }

[Side note - I use the convention of using template functions (or member
functions) with the first template parameter being the result type - then
using specifying that type to get the appropriate call.]

I have considered doing an adaptor to force the tree to be a binary tree, or
an alternate implementation would be to do the foundation template as a
binary tree and have an adaptor to make trees (Knuth describes how a binary
tree can be used to implement a forest of trees and how the iterators map
between the two).

There are also alternate organizations of the children - if this is a
"sequence tree" one could also envision an associative tree where the
children are ordered.

I've seen several generic graph implementations that provide a tree
implementation as a specialized graph - but none that map into the normal
sequence generic algorithms well.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Hi,
Radoslav Getov (nospam@mai.com) wrote:
: Add a balanced binary tree container to STL

For such a container to be useful, it is first necessary to come up
with a suitable abstraction: Just dealing with one specific binary tree
class is not the C++ way to do things. Instead, a bunch of concepts
should be set up to deal with various kinds of binary trees or even
trees in general and then corresponding algorithms are provided.
Whether it reasonable to provide a corresponding "convenience" class
which just ties together the various algorithms is a different issue.
Probably it is more reasonable to have the user toss together a class
suitable for the application's needs: For example, I can imagine lots
of variations in the tree data structures depending on the respective
needs. Here are just some:

- Is a parent pointer stored or not: Many tree operations don't
  require a parent point but can deal with the path from the root to
  the given node. This might be a size vs. speed trade-off but probably
  it is actually a speed/size vs. flexibility trade-off (I haven't
  measured this, however).

- Is the tree really balanced and if so which balancing strategy is
  used. AVL vs. red/black trees are an obvious decision. For some
  probabilistic stuff a splay tree might also be a suitable balancing
  strategy whcih might even be faster for certain kinds of applications
  (eg. if typically accesses are more or less local in the tree).

- Are leaf nodes linked to the root of the corresponding subtree (I
  don't know the English term for this): This trades speed of certain
  iteration patterns against modification time and node size.

- What are the subtrees called. "left" and "right" seems natural but
  isn't "children[0]" and "childern[1]" (or something similar) as
  natural in a setting where general trees are also used.

- How are the nodes maintained anyway? It is legal for multiple trees
  to share subtrees (which, however, basically rules out balancing)?

: - support insertion at user-specified position (given by iterator);
: complexity 0(1)

It cannot be done in O(1) time for balanced trees: This operation takes
at least O(log n). It might be possible to do it in O(1) amortized time
for certain usage patterns but I doubt that this is true in general.
However, I haven't verified my claim.

: - support deletion of arbitrary node with complexity 0 (1)

Same as for insertion. Here my guess is somewhat stronger that it
cannot be done in the complexity, even amortized complexity.

: - additionally to 'normal' (e.g. list::iterator) interface, define these
: functions of its iterators:
:    iterator iterator::left()   // get the left child; return 'end()' if none
:    iterator iterator::right() // the right child
:    iterator iterator::parent() // the parent; end() if 'root'

I would almost certain split the tree iterator interface and the
sequence iterator interface into two different entities! The sequence
iterator can obviously be implemented in terms of tree iterators (even
in various variations like pre-, in-, and post-order, level order,
etc.). However, the iterators might eg. use an internal stack to avoid
the need for parent pointers. This does not fit the sequence iterator
model well... (although it is implementable).

: Writting a balanced tree is not a trivial task.

Yes, a basic version takes about a day's work. This is non-trivial and
it might be reasonable to provide the corresponding algorithms. I doubt
that an arbitrary selection of possible implementation properties
serves all uses reasonably well and thus I doubt that The Tree class is
reasonable approach. However, the algorithms should probably be there.

: The funny thing, though, is that in most (all?) STL implementations balanced
: trees are already present (used in 'set' and 'map').

It is an implementation detail and depending on the implementation
these classes are clearly not suitable for general use: They are at
least sometimes tailored to the use in the STL associative containers,
ie. to the use of a sorting function. Also, the standard does not
mandate a balanced tree implementation. Skip lists are another
alternative, AFAIK, although I'm not aware of any implementation using
this approach. Another alternative is the use of Beyer trees, I think.
I haven't tought enough about the issue of not invalidating iterators,
however, to tell for sure whether this kind of trees is an alternative
for the STL associative containers. In any case, even if all
implementations use balanced trees, these are not suitable abstracted
and there are no suitable concepts defined for the use of trees (or any
other non-sequence data structure).

Note that I'm not argueing against the addition of tree algorithms to
the standard library. All I'm saying is that it requires somewhat more
work than just exhibiting the tree interface to do it reasonably.
--
<mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

On Wed,  9 May 2001 17:02:52 GMT, "Radoslav Getov" <nospam@mai.com>
wrote:

> This idea was there for a while, and here it is again:
>
> Add a balanced binary tree container to STL

I have problems understanding this.

A binary tree is a tree thingie that does tree things.  Its structure
is everything.  It's a special graph.

A balanced binary tree is a low level search data structure.  It is
not a tree because balancing it destroys the tree structure.

> It should include all the 'std::list' behaviour, and additionally:
>
> - support insertion at user-specified position (given by iterator);
> complexity 0(1)
> - support deletion of arbitrary node with complexity 0 (1)
> - deletion and insertions should not invalidate other iterators
> - operations should preserve its balance
> - additionally to 'normal' (e.g. list) interface define function 'top()' or
> 'root()':
>     iterator tree::root()

Get a root iterator, do an insertion and it is not the root anymore.
What does root have to do with this?

> - additionally to 'normal' (e.g. list::iterator) interface, define these
> functions of its iterators:
>    iterator iterator::left()   // get the left child; return 'end()' if none
>    iterator iterator::right() // the right child
>    iterator iterator::parent() // the parent; end() if 'root'

I had a parent, did an erase, and suddenly my parent is my child?

> Writting a balanced tree is not a trivial task. Of course, those of us that
> need them, have no choice but to implement them by themselves.
> The funny thing, though, is that in most (all?) STL implementations
> balanced
> trees are already present (used in 'set' and 'map').

Yes, the interface is the union of the four associative containers.  It
does exactly what they do and nothing more.  It is an implementation
detail.

It is clear to me that you do not want a tree that could be used for
parse trees, for example.

It is not clear to me what you do want.  You clearly want a logN search,
insert, erase structure.  What is missing in the four associative
containers?  I'm trying to abstract your needs from a specific data
structure to an interface and its use.

John

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <9di52a$hf1$3@news.BelWue.DE>, dietmar_kuehl@yahoo.com wrote:
>Radoslav Getov (nospam@mai.com) wrote:
>: Add a balanced binary tree container to STL
>
>For such a container to be useful, it is first necessary to come up
>with a suitable abstraction: Just dealing with one specific binary tree
>class is not the C++ way to do things. Instead, a bunch of concepts
>should be set up to deal with various kinds of binary trees or even
>trees in general and then corresponding algorithms are provided.
>Whether it reasonable to provide a corresponding "convenience" class
>which just ties together the various algorithms is a different issue.

The reason for adding such a container to the C++ library is a reasonable
average complexity: For lists, insertion complexity is O(1), whereas for
search of index k, k an integer, is O(n) (where n = container size); for
an array, it is the opposite.

The balanced tree container has both those complexities O(log n).

So if one has a mixture of container operations, and does not know how the
use of those operations balances out, then the balanced tree container is
a good alternative.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

kuehl@ramsen.informatik.uni-konstanz.de (Dietmar Kuehl) dared to utter in
news:9di52a$hf1$3@news.BelWue.DE:

>
> - Is a parent pointer stored or not: Many tree operations don't
>   require a parent point but can deal with the path from the root to
>   the given node. This might be a size vs. speed trade-off but probably
>   it is actually a speed/size vs. flexibility trade-off (I haven't
>   measured this, however).
>

I agree with all you say, except this one. A std::list<> is a double linked
list. Why was that chosen over a single linked list? I think that was, in
short, because of the added value at minimal cost. The same reasoning
probably applies here too. I still build my own lists when memory
requirements dictate so. The same would hold for trees as far asa I'm
concerned.

Regards,
Martijn Lievaart

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Dietmar wrote:

[ Interresting comments, as usual. ]

> In any case, even if all
> implementations use balanced trees, these are not suitable abstracted
> and there are no suitable concepts defined for the use of trees (or any
> other non-sequence data structure).

I can see one usefull operation on search trees not available
in existing associative: left and right move on an iterator.

My point is to search a root of a monotonic function on a (sorted)
associative container: it's impossible to do efficientely w/o
breaking the encapsulation. With a sorted random-access
Sequence (the equivalent of a SortedAssociativeContainer w/o
insertion/removal), just use binary_search.

The implementation of SortedAssociativeContainer::find already
does a n-ary search to have logarithmic complexity; all I want
is to have the right to do it my-self, or at least to have a
find(Predicate) member function.

But moving these find functions (find (Key) and find (Predicate))
out of the (member) interface of SortedAssociativeContainers
would be closer to the spirit of the STL.

Anyway, the STL doesn't really understand the spirit of the STL.
And member functions shall be banned (be we already mentionned
that, didn't we ?).

  -- VB

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Hi,
Valentin Bonnard (Valentin.Bonnard@free.fr) wrote:
: Dietmar wrote:

: [ Interresting comments, as usual. ]

: > In any case, even if all
: > implementations use balanced trees, these are not suitable abstracted
: > and there are no suitable concepts defined for the use of trees (or any
: > other non-sequence data structure).

: I can see one usefull operation on search trees not available
: in existing associative: left and right move on an iterator.

I haven't debated that it might be useful to have more direct access to
the underlying trees. All I was saying is that the underlying concepts
are missing and that the internally used trees are typically only
suitable to implement the associative container interface. What I would
consider useful is a set of algorithms doing tree manipulations on
suitable concepts for trees. This would make it easy to implement a
tree class because the actually operational stuff is already there.
What is missing is only are only the declarations and calling of the
correct algorithms.

: Anyway, the STL doesn't really understand the spirit of the STL.

Although I agree, I want to point out that the people would created the
STL hadn't the technical equipment we have now (the compilers at this
time were really inferior to the current compilers and even the
language was more restrictive in some important aspects) and that we
know have gained the insights over several additional years.
Personally, I'm all in favour of cleaning up the concepts, algorithms,
and iterators (I don't care much about the containers as I consider
them to be more or less just examples of sequences). My pet change is
the separation of position from access, ie. turning the current
iterators into two concepts, namely iteration and property maps (see
the Boost Graph Library at <http://www.boost.org/> for details on the
latter): The algorithms would be more general and could operate cleanly
on proxied containers, for example. At the same time it would be
possible to implement the current interface in terms of the new
abstraction to deal with compatibility issues.

: And member functions shall be banned (be we already mentionned
: that, didn't we ?).

At the last standardization meeting there was a lengthy discussion of
how to cope with specialized versions of eg. 'swap()'. As it turns out,
this stuff is pretty easy to deal with when you have member functions.
It is harder with free standing functions. My personal preference is
currently to rely completely on Koenig-lookup.

However, I'm also in favour of defining concepts only in terms of free
standing functions rather than in terms of member functions. Of course,
this does not mean that member functions aren't used for the internal
implementation. Only the concepts should go without member functions.
--
<mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Hi,
Martijn Lievaart (xnews.public.home@bogus.rtij.nl) wrote:
: kuehl@ramsen.informatik.uni-konstanz.de (Dietmar Kuehl) dared to utter in
: news:9di52a$hf1$3@news.BelWue.DE:
: > - Is a parent pointer stored or not: Many tree operations don't
: >   require a parent point but can deal with the path from the root to
: >   the given node. This might be a size vs. speed trade-off but probably
: >   it is actually a speed/size vs. flexibility trade-off (I haven't
: >   measured this, however).

: I agree with all you say, except this one. A std::list<> is a double linked
: list. Why was that chosen over a single linked list? I think that was, in
: short, because of the added value at minimal cost.

... and why does SGI STL (and I think some other standard C++ library
implementations) also provide a class 'slist' which is actually a
singly linked list?

: The same reasoning
: probably applies here too. I still build my own lists when memory
: requirements dictate so. The same would hold for trees as far asa I'm
: concerned.

These are all trade-offs. What is suitable for one party may be
unsuitable for another one. ... and if we are thinking about a tree
class in the standard C++ library it should be of general use. IMO the
best approach to this is to provide the suitable algorithms for dealing
with tree classes and have the user toss together the appropriate ones
for the given implementation. That is, no tree class is defined in the
standard library at all but the necessary concepts and algorithms are.
--
<mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Hans Aberg wrote:
...
> >Radoslav Getov (nospam@mai.com) wrote:
> >: Add a balanced binary tree container to STL
...
> The reason for adding such a container to the C++ library is a reasonable
> average complexity: For lists, insertion complexity is O(1), whereas for
> search of index k, k an integer, is O(n) (where n = container size); for
> an array, it is the opposite.
> The balanced tree container has both those complexities O(log n).

So does std::map<>.  What advantage does this proposed binary tree
container have compared with std::map<> that justifies having two
classes with what will probably be almost identical internals?

The only advantage I've seen in the proposed class are its improved
complexity requirements for inserts and deletes, and I'm skeptical about
the feasibility of meeting those requirements. This class is essentially
equivalent to exposing some of the internals of std::map<>, which makes
about as much sense as exposing the internals of a horse - horses with
their internals exposed are in danger of getting them damaged, or
infected, and the same applies here. This is a fundamental concept in
good OO design - hide the implementation details, so that the using code
doesn't make the mistake of becoming dependent upon those details.

The root(), parent(), left(), and right() functions report relationships
that should matter only to the code which manages the container, not to
the code which uses it. Since the managing code might change those
relationships after any insert() or erase(), those values aren't useful
for very long anyway. By exposing the internals, these functions freeze
the container's design; with std::map<> implementors are free to
experiment with different ways of implementing it that might not be
equivalent to a binary tree, and that might make it difficult to emulate
a binary tree.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Matthew Austern" <austern@research.att.com> wrote in message
news:dil8zk6whez.fsf@isolde.research.att.com...
> "Radoslav Getov" <nospam@mai.com> writes:
>
> > This idea was there for a while, and here it is again:
> >
> > Add a balanced binary tree container to STL
> >
> > It should include all the 'std::list' behaviour, and additionally:
> >
> > - support insertion at user-specified position (given by iterator);
> > complexity 0(1)
> > - support deletion of arbitrary node with complexity 0 (1)
>
> I don't see that either of those is possible.  If you've got a
> balanced tree, then in general insertion or deletion requires extra
> steps to maintain the balance.  In a red-black tree, for example,
> insertion and deletion are O(log N) because you have to maintain the
> red-black property.
>
>
I'm talking about amortized time, of course..

Radoslav Getov



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

This idea was there for a while, and here it is again:

Add a balanced binary tree container to STL

It should include all the 'std::list' behaviour, and additionally:

- support insertion at user-specified position (given by iterator);
complexity 0(1)
- support deletion of arbitrary node with complexity 0 (1)
- deletion and insertions should not invalidate other iterators
- operations should preserve its balance
- additionally to 'normal' (e.g. list) interface define function 'top()' or
'root()':
    iterator tree::root()
- additionally to 'normal' (e.g. list::iterator) interface, define these
functions of its iterators:
   iterator iterator::left()   // get the left child; return 'end()' if none
   iterator iterator::right() // the right child
   iterator iterator::parent() // the parent; end() if 'root'

Writting a balanced tree is not a trivial task. Of course, those of us that
need them, have no choice but to implement them by themselves.
The funny thing, though, is that in most (all?) STL implementations balanced
trees are already present (used in 'set' and 'map').
For some reason, though, the idea that a balanced binary tree could be
useful
enough by itself is not common enough, so they are not in the standard, not
are exposed publicly even as non-standard extensions in the STL
implementations I am aware of.

Everything that has to be done is to make 'tree' interface standard,
compliant as
much as possible to the interfaces of the other containers. Particularly, it
should
be possible to replace 'list' with 'tree' without any functional or
complexity difference.

Of course, some specific extensions (compared to 'list' could be added to
the tree container and its iterators.

Radoslav Getov





---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

"Radoslav Getov" <nospam@mai.com> writes:

> This idea was there for a while, and here it is again:
>
> Add a balanced binary tree container to STL
>
> It should include all the 'std::list' behaviour, and additionally:
>
> - support insertion at user-specified position (given by iterator);
> complexity 0(1)
> - support deletion of arbitrary node with complexity 0 (1)

I don't see that either of those is possible.  If you've got a
balanced tree, then in general insertion or deletion requires extra
steps to maintain the balance.  In a red-black tree, for example,
insertion and deletion are O(log N) because you have to maintain the
red-black property.



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]