DList and SList missing length property?

[monarch_dodra]

On Tuesday, 28 May 2013 at 18:16:48 UTC, Jonathan M Davis wrote:
> Now, that being said, I don't see a splice operation on either 
> SList or DList
> (and I don't think that splicing an SList can be done in O(1) 
> anyway), so it
> would appear that the implementation is optimizing for an 
> operation that it
> doesn't currently support.

SList can be spliced, but the semantics are a bit more 
complicated. In most cases, if you need to splice, you'd use a 
DList anyway: SList is really for particular use cases.

I think that if splice is not in DList, it is only because it is 
not *yet* in DList. I have an implementation ready to submit, 
which adheres to Andrei's proposed container semantics. I have 
not yet submitted it though, because fixing DList is more 
important that inserting more functionality.

It's current semantics are neither value nor ref. It's... 
something else. My fault for inserting it when trying to fix 
previous clusterfuck. I've since submitted fix that gives it 
classic semantics, but it's kind of just sitting there...

We should *really* see to getting it (or something else) pulled 
through.

> The same situation exists with C++'s std::list type though - 
> size() is O(n)
> and splicing is O(1). However, we opted for not having 
> containers implement
> inefficient operations like that (which C++ mostly did as well, 
> but not in this
> case).
>
> - Jonathan M Davis

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'll look up the exact requirement later tonight.