Re: [boost] Re: boost::tree advice?

From: Dan Rosen (dan.rosen_at_[hidden])
Date: 2005-03-29 23:20:44

David,

Let me take a step back. I think we're fundamentally in agreement, but
we have very different use cases in mind. I had considered neither
btrees nor tries in my initial work on developing general-purpose tree
containers, so the examples I provided and the language I used might
have made it seem like I didn't *want* to consider them.

What I'm doing right now is just gathering requirements and ideas. One
requirement is clearly "keep your tree nodes on a diet," which was the
slant of my initial questions in this thread (i.e. how to satisfy a
variety of needs without making my nodes and iterators obese); I see
that as sort of a common-sense implementation-level requirement. I'm
also just as interested in functional requirements, and it's clear
that having a fast k-ary tree (single and multi-keyed alike) such as
you're proposing is one such requirement. Another such requirement is
my use case of trees with unbounded children per node. I make no claim
that both requirements can be met optimally, or even adequately, by
the same tree.

Regarding Jeff's design: as I said, I think the "feature-oriented"
paradigm seems extremely elegant from the client perspective
(generally speaking). But because I'm not yet aware of enough
different requirements, I don't yet see a reason to go with that type
of implementation. Emphasis on "yet." But through the process of
requirements gathering, it may turn out that there are compelling
reasons to vary a tree's implementation on a significant enough number
of axes to warrant going with that type of design.

Let me ask a question which I hope will direct this discussion down a
productive path: In what scenarios (as many as you can think of) would
users need to be directly exposed to the structure of some sort of
tree? This is in contrast to the situations where trees are the
sensible implementation (such as std::set, std::map, etc.) but needn't
be exposed. If we can put that list together, I think that would be a
good start.

Best,
dr