DList and SList missing length property?

[Steven Schveighoffer]

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