From: Beman Dawes (bdawes_at_[hidden])
Date: 2001-01-12 09:00:05
At 09:02 PM 1/11/2001 -0500, Jeremy Siek wrote:
>On Thu, 11 Jan 2001, Matthew Austern wrote:
>auster> First question: is size() O(1), or O(N)? The only way for
>auster> it to be O(1) is if you keep an element count in the list.
>auster> I'm opposed to keeping such a count, because users who care
>auster> about it can keep a count themselves; I don't want to spend
>auster> that extra word of storage.
>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
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.
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk