DList and SList missing length property?

[monarch_dodra]

On Thursday, 30 May 2013 at 01:56:03 UTC, Steven Schveighoffer 
wrote:
> 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.

That's why I said "amortized" with quotes. Not the exact term, I 
know. I should have been clearer. "You can get 0(1) length, 
except in certain situations, where you'll have to pay once an 
0(n) to get back to 0(1)".

And yeah, it is dependent on usage. Like vector's push_back. 
(although incidentally *that* is true amortized)

> 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.

http://www.cplusplus.com/reference/list/list/splice/

Note that 1 element splice (2) is not a problem. It has always 
been 0(1), regardless of scheme. In my scheme, it wouldn't 
invalidate legnth.

Only [iterator .. iterator] splice (3) is is problematic.

Full list splice (1) status is more complex. It is actually 0(1) 
in the scheme where length is 0(1). With my scheme, the 
guarantees depends on where you want to place the best compromise.