GSoC-2011 project:: Containers

[KennyTM~]

On Mar 31, 11 02:30, spir wrote:
> On 03/30/2011 05:30 PM, Steven Schveighoffer wrote:
>>> Do you mean removal of an already accessed node/value? If yes, then
>>> removal
>>> can effectively be O(1), but to first get the access (here, via a
>>> pointer)
>>> one needs O(n) traversing the list in any case.
>>
>> Of course. With SList, you need O(n) to get to the element, and then
>> O(n) to
>> remove it once you find it ;)
>
> I guess you refer to the fact that, in a slist, as opposed to doubly
> linked list, one misses the 'previous' slot needed to insert or remove.
> Thus, one must re-traverse to reach it. Is it the issue you're evoking?
> There is a trick to avoid that, wrote it once long ago (since then I
> have, like you, only used doubly-linked ones). I guess the point is,
> while traversing to search a given element (by index, value, pattern
> matching or whatever) to constantly keep track of the previously visited
> node. Thus, when you get there, you have the needed trio
> (previous/current/next) available for whatever operation.
>
> Denis

Using 'previous' pointer to allow O(1) removal will make this program 
crash, although I don't know if this is allowed or not:

     auto r = slist.front;
     r.popFront();
     slist.removeFront();
     slist.remove(r);

(You don't need 'next' because it is already stored in the 'current' node.)