RE: [boost] Hash tables and singly linked lists

From: Aleksey Gurtovoy (alexy_at_[hidden])
Date: 2001-01-13 05:29:30

Beman Dawes wrote:
> At 09:02 PM 1/11/2001 -0500, Jeremy Siek wrote:
>  >Another option is to provide both using a generative approach. Let the
>  >user choose at compile time whether they want a size() to be O(1) or
> O(N).
>
> Be careful; parameterization discourages users.  I think I'd rather see
> generative techniques reserved for killer problems that are otherwise
> intractable, at least until use of generative techniques becomes more
> common and there is more introductory material available.

But someone needs to start to apply them (reasonably :) to make them more
common ;). For me the 'slist' case seems to be a quite reasonable application
to start with. And I think that Jeremy doesn't mean that 'slist' should
_force_ users to make the choices they might be not interested in at all; as
you suggested below, we can always provide a few pre-generated classes with
some common sets of configuration parameters, so those of users who don't need
the flexibility of generative approach won't even notice the existence of the
amazing possibilities it offers ;).

BTW, one very good material on the topic, which is condemned to become
classic, is just a week far from the release -
http://www.awl.com/cseng/titles/0-201-70431-5. So (I think :), by the time
Matt's extended implementation of the standard library will be released, many
people will expect to see some kind of generative approach applied there, at
least in a few places ;).

> I've also wondered about a two-tier approach to this sort of problem.  A
> single component (slist in this case) with a reasonable set of design
> choices but not a whole lot of parameterization.  And then a generator
> (slist_generator) for those who care enough to be willing to learn who to
> use the parameterization.

That's that I think is a close-to-optimal solution; but I would rather reverse
the layers - 'slist_generator' would be a basic layer, and 'slist' would be
just one of a few pre-configured cases that together would cover most of the
common usage patterns/constraints.

--Aleksey