From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2006-12-16 20:32:16
Pavel Vozenilek wrote:
> "Ion Gaztañaga" wrote:
> One solution may be to provide list::size()
> and have the size itself encoded as a signed integer.
> If the integer is >= 0 then the size() will return it.
> After splice() the number will be set negative.
> Only the next size() call will go through the list
> and set the correct value again.
> For a typical list<> use the size() should
> get amortized to O(1).
> Alexandrescu had discussed this few years ago
> in context of his YASLI library.
This can be an option. The downside is that size() is a const function
and we should declare the size member as mutable. This converts a
thread-safe function like size() to a non-thread safe one. But I agree
that this can be a good solution. To avoid wasting a bit of the internal
size integer, we could define size() as "this->size_ - 1", so
this->size_ == 0 could represent unknown size and this->size_== 1 an
empty list, this->size_ == 2 a list with just 1 element and so on.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk