GSoC-2011 project:: Containers

[Steven Schveighoffer]

On Wed, 30 Mar 2011 14:30:37 -0400, spir <denis.spir at gmail.com> 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.

Yes, the range should do this.

-Steve