On Sunday, 30 December 2012 at 10:58:38 UTC, Jonathan M Davis
wrote:
On Sunday, December 30, 2012 16:18:18 d coder wrote:
For some reason, remove doesn't support take like it should,
but linearRemove does.
[SNIP]
- Jonathan M Davis
That's because remove guarantees o(1), whereas linearRemove is
allowed to operate in o(N).*
Removing a DListRange is o(1)
To remove a "take" range, one must first walk the source range
until you have extracted the eauivalent DListRange, which is a
o(N)operation.
Forcing you to use the word "linearRemove" guarantees you know
what you are paying for.
That is the how and why.
--------
As a matter of fact, std.algorithm.Array doesn't even have
"remove" for exactly this reason, but it does have
"linearRemove". Trying to call Array.remove will actually result
in a weird-ass error because the compiler thinks you are calling
std.algorithm.remove, but you may not immediately realize that
nor what the compiler is complaining about...
--------
*The whole thing is a little inconsistent because "insert" may or
may not be linear but there is no "linearInsert" variant. Guess
this is to avoid things like "linearStableInsertBefore".
As for remove, according to the "top doc", the complexities are
actually:
c.remove(r) O(nr * log nc)
c.linearRemove(r) O(nc)
So technically, remove could accept a take!Range... but I think
having a generalized complexity is wishful thinking, each
container should define its own complexities.
--------
One last thing, avoid using the "stable" versions of remove.
Appart from Slist's stableRemoveFront, NONE of them are actually
stable (stable = "guarantees that ranges iterating over the
container are never invalidated"). And even, then, that's because
SList has a weird design, which I think may end up getting
"fixed" ...
