Re: splicing / size on lists

[Chris Jefferson <caj at cs dot york dot ac dot uk>]

Paolo Carlini wrote:

> Chris Jefferson wrote:
>
> > Does anyone have any comments / suggestions?
>
>
> Search the archive ;)
>
> Seriously, I'm not sure how the recent detailed discussions may change 
> our attitude toward this issue, but I'm pretty sure we already 
> discussed it in the past and eminent people said, roughly "if you 
> really need O(1) size, the list is not the right container", or 
> something very close.
Hmm.. you are right. This is one of the more stupid things in the C++
standard it appears. Everyone either provides O(1) size and O(n) splice
or O(n) size and O(1) splice. Unfortunatly you of course can't assume
anything better than O(n) size and O(n) splice, meaning that you end up
with the worst of both worlds ¬_¬. It would surely be better if they'd
fixed on one or the other... While I'd probably fall in the O(1) size
camp, I imagine it would upset more people than it would please to
change libstdc++'s implementation at this point.

Thanks

Chris