On Wed, 30 Mar 2011 14:28:49 -0400, KennyTM~ <kenn...@gmail.com> wrote:
On Mar 30, 11 23:01, Steven Schveighoffer wrote:
And yes, you can, if you have a pointer to the element right before the
insertion/removal point.
That what I've said in the previous post. The point is linearRemove's
interface does not take that pointer.
/// Removes a range from the list in linear time.
Range linearRemove(Range r);
Perhaps SList could provide an O(1) .removeAfter method, like:
/// Remove elements in the range [r.front+1 .. $)
Range removeAfter(Range r) {
// add checking yourself.
r._head._next = null;
return Range(null);
}
or an O(1) .removeOneAfter which may be more useful than chopping the
whole tail:
/// Remove one element in at r.front+1
/// and return the range [r.front+2 .. $)
Range removeOneAfter(Range r) {
// add checking yourself.
r._head._next = r._head._next._next;
r.popFront();
return r;
}
So I have an SList!int, and I want to remove a certain element in linear
time. How can I do this with SList, even with your primitives? Answer:
the really convoluted difficult way:
void removeSpecificElement(SList!int mylist, int elem)
{
if(!mylist.empty && mylist.front() == elem)
mylist.removeFront();
else
{
auto r1 = slist[];
auto r2 = r1;
r1.popFront();
while(!r1.empty && r1.front != elem)
{
r2 = r1;
r1.popFront();
}
if(!r1.empty)
mylist.removeOneAfter(r2);
}
}
Whereas, I'd rather have:
mylist.remove(take(find(mylist, elem), 1));
BTW, I realized while reading the docs that this only applies to removal,
insertion does have an insertAfter function (though with the range
properly implemented, insert becomes possible).
-Steve
