std.container & ranges

[Dmitry Olshansky]

Looks like it was accidental cross-posting:

On 31.10.2011 20:11, Alessandro Stamatto wrote:
 >
 >     it still would be horribly slow O(N^2).
 >     Personally, because of that I'd prefer hand-rolled intrusive
 >     singly-linked list any time of day.
 >
 >
 > Now you're scaring me... You're saying that SList in D not only is 
bugged, but
 > a templated remove_if would run in O(N^2) instead of O(N) ????!!!!

Basically I'm saying that with current SList *implementation* it will 
run in O(N^2), because for some reason it always do a check on each 
range passed to remove that it does belong to this list. (i.e. it walks 
from head till hits it or it's own tail)

-- 
Dmitry Olshansky