Boost logo

Boost :

Subject: Re: [boost] proposal for tree container
From: Gottlob Frege (gottlobfrege_at_[hidden])
Date: 2009-07-16 00:26:42


On Mon, Jul 6, 2009 at 11:58 AM, Jose<jmalv04_at_[hidden]> wrote:
> On Mon, Jul 6, 2009 at 4:39 PM, Andrew Sutton<andrew.n.sutton_at_[hidden]> wrote:
>
>> If there is going to be a discussion about adding tree.hh to Boost, then I
>> would hope that the discussion focuses on your implementation as a
>> standalone data structure, and not as a complete generic library.
>> Comparisons of tree.hh to the STL or BGL seem inappropriate to me.
>
> Yes, I think this is what the author means. I think in the old thread
> 2002 someone misunderstood the library and compared with BGL, which
> probably confused many. It is not for graphs but storing and querying
> tree-like data. One of the many apps where this data structure is
> useful is as a way to store parse results that can later be queried
> (e.g. DOM tree)
> http://en.wikipedia.org/wiki/K-ary_tree
>
> His implementation of a n-ary tree data structure has been used by a
> few apps already and there would be a mutual benefit if it becomes
> part of boost

I think the only question is whether it is 'generic enough' to be
widely useful. Obviously it isn't BGL. I think of BGL (although I
know little of it) of things (algorithms) to do with trees (and other
graphs) *once you have one*, not a tree in itself.

So is it a 'good enough' tree for most uses? (Seems to be useful
enough for some people already.) Can it (should it?) be made a bit
more generic for more uses?

And/or, should it be more specifically named (k_ary_tree or whatever),
to separate it from red_black_tree, splay_tree,... etc?

What are the requirements of 'tree-ness'? Containers like
std::map/list/deque/vector/... all have well defined requirements.

Tony


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk