Re: [boost] Hash tables and singly linked lists

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-01-11 21:02:09

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

auster> A more interesting question: what's the complexity of 
auster> L.insert(i, x)?  (Semantics: insert x before i.)
auster> [snip]
auster> (Actually, while writing this, I realized that, since I'm claiming
auster> that it's easy to build a slist-plus-end-pointer on top of an
auster> slist, I should provide a little tconc wrapper class that keeps 
auster> track of the last element, and that performs that iterator remapping
auster> that I've talked about.  Users who want zero overhead can use raw
auster> slist, users who want convenient insert-before can use the wrapper.
auster> I should probably give the wrapper a better name that tconc, though.
auster> Suggestions?)

I like where you going with this, and it matches up with what I said
above. In the library we can provide implementations of all the different
variations and let the user decide what's important to them.

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                        www: http://www.lsc.nd.edu/~jsiek/
 Ph.D. Candidate                  email: jsiek_at_[hidden]
 Univ. of Notre Dame         work phone: [phone]
----------------------------------------------------------------------