Re: [boost] Hash tables and singly linked lists

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>
 >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 
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.

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.

--Beman