DList -- removing an element

[monarch_dodra]

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