Boost logo

Boost :

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

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


 Jeremy Siek www:
 Ph.D. Candidate email: jsiek_at_[hidden]
 Univ. of Notre Dame work phone: (219) 631-3906

Boost list run by bdawes at, gregod at, cpdaniel at, john at