On Wed, 29 May 2013 05:15:00 -0400, monarch_dodra <[email protected]>
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
<[email protected]> 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
