On Thursday, 30 May 2013 at 01:56:03 UTC, Steven Schveighoffer
wrote:
On Wed, 29 May 2013 05:15:00 -0400, monarch_dodra
<monarchdo...@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
<monarchdo...@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.
