GSoC-2011 project:: Containers

[Steven Schveighoffer]

On Wed, 30 Mar 2011 14:28:49 -0400, KennyTM~ <kennytm at 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