DList and SList missing length property?

[Steven Schveighoffer]

On Wed, 29 May 2013 05:15:00 -0400, monarch_dodra <monarchdodra at gmail.com>  
wrote:

> On Tuesday, 28 May 2013 at 22:29:02 UTC, Steven Schveighoffer wrote:
>> On Tue, 28 May 2013 17:11:06 -0400, monarch_dodra  
>> <monarchdodra at gmail.com> wrote:
>>
>>> 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...
>>
>> I'm not sure how that works, can you explain/have a link?
>>
>> -Steve
>
> Well, the basic idea is to give your list an "m_size" member. This  
> starts at 0. Whenever the user does a push_back/pop_back or whatnot  
> operation, the the "m_size" attribute gets correctly upgraded. At that  
> point, calling "size()" simply returns "m_size".
>
> Now, once a splice operation gets called, the m_size gets reset to a  
> magic value, to indicate that tracking of the size has been lost.  
> Operations will seize upgrading m_size, until a call to size is made, at  
> which point it will be re-calculated, once.

This is O(n) length, not amortized O(1) length, as it is highly dependent  
on usage.

For example, in a project I am currently working on, I most frequently am  
using splice to move one list element at a time.  This degrades your  
solution to basically O(n) length for every move, and I move a lot.

-Steve