GSoC-2011 project:: Containers

[KennyTM~]

On Mar 30, 11 21:09, Steven Schveighoffer wrote:
> On Wed, 30 Mar 2011 04:55:52 -0400, KennyTM~ <kennytm at gmail.com> wrote:
>
>> No, the big difference is you can't move backward in a singly-linked
>> list. So, for instance, SList can only have linearRemove, while
>> (doubly-linked) List can have a constant-time remove.
>
> I hate to point it out, but any linked list implementation, whether it
> be single or double-linked, which does not support O(1) removal is 100%
> useless. Might as well use an array.
>
> Andrei, you really need to fix that.
>
> -Steve

You can't O(1) remove an arbitrary range from an SList. O(1) removal is 
possible only if you also know an iterator right before the range.