GSoC-2011 project:: Containers

[Steven Schveighoffer]

On Wed, 30 Mar 2011 14:21:35 -0400, spir <denis.spir at gmail.com> wrote:

> On 03/30/2011 05:01 PM, Steven Schveighoffer wrote:
>> On Wed, 30 Mar 2011 10:45:19 -0400, KennyTM~ <kennytm at gmail.com> wrote:
>>
>>> 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.
>>
>> If you have a linked list of any type, and can't do O(1) insertion or  
>> removal
>> of a single element, then you have failed. Linked list's complete  
>> advantage is
>> arbitrary O(1) insertion and removal. Arrays have O(n) insertion and  
>> removal,
>> with random access. Why would I ever use SList in its current form when  
>> it has
>> the same complexity as but less features than a builtin array?
>
> Because it's O(1) insertion/removal at front (not only of elements, also  
> of sublists).

I have O(1) insertion/removal at the end of an array.  Just call the end  
the "front" and you have the same thing.

BTW, deque supports O(1) insertion and removal at both ends.

>
>> And yes, you can, if you have a pointer to the element right before the
>> insertion/removal point.
>
> Sure, but what kind of programming sorcery provides this pointer without  
> O(n) traversal? (See my other post).

You are not getting it.

SList's implementation to remove the element containing 5:

auto r = find(mySList[], 5); // O(n) operation
mySList.linearRemove(take(r, 1)); // O(n) operation, even though I just  
searched for the element.

Expected implementation:

auto r = find(mySList[], 5); // O(n) operation
mySList.remove(take(r, 1)); // O(1) operation

If the second operation is O(n), *EVEN THOUGH YOU JUST GOT A POINTER TO  
IT*, then the list is a failure.  An SList range should retain enough info  
to be able to remove its front element, it's not that hard.

 From en.wikipedia.org:

"The principal benefit of a linked list over a conventional array is that  
the list elements can easily be added or removed without reallocation or  
reorganization of the entire structure because the data items need not be  
stored contiguously in memory or on disk. Linked lists allow insertion and  
removal of nodes at any point in the list, and can do so with a constant  
number of operations if the link previous to the link being added or  
removed is maintained during list traversal."

-Steve