DList and SList missing length property?

[monarch_dodra]

On Tuesday, 28 May 2013 at 19:24:05 UTC, Steven Schveighoffer 
wrote:
> On Tue, 28 May 2013 15:06:53 -0400, Jonathan M Davis 
> <jmdavisProg at gmx.com> wrote:
>
>> On Tuesday, May 28, 2013 20:51:55 monarch_dodra wrote:
>>> That was in C++03. In C++11, length was reduced to 0(1). And
>>> splice was increased to 0(N) (I think, I don't remember the 
>>> exact
>>> details, but it was definitely changed).
>>
>> I do remember hearing something about that, though that will 
>> actually result
>> in some nasty performance changes to some of the code out 
>> there (including
>> code that I've written).
>>
>> Regardless, you have the choice of making length O(1) or 
>> splicing O(1) and not
>> both, and C++98/03 made splicing O(1), which I'm inclined to 
>> believe is the
>> better choice, though having size when it's O(n) was a 
>> definite mistake on
>> C++'s part IMHO. I hate to think of how many times I've seen 
>> programmer's
>> write container.size() == 0 instead of empty(), particularly 
>> when size() was
>> O(n)...
>
> I actually had performance bugs the OTHER way -- I needed the 
> length of a list, and was using .size() without realizing it 
> was O(n).  In profiling my code, I found that 
> std::list<T>::iterator::operator++ was the most used function, 
> and I had no idea why for a LONG time :)
>
> You know, it is trivial to have an O(1) splice O(n) length list 
> wrapped into an o(n) splice O(1) length list.  All you need is 
> to add a tracked length.  And this is a REAL pain when you have 
> to do it manually.  There should just be two list types in 
> <list>
>
> -Steve

A proper implementation should be able to track length anyway: 
provide 0(1) splice, and an "amortized" 0(1) length.

I've always wondered why the standard didn't decide to do *that*? 
I think *we* should provide that...