GSoC-2011 project:: Containers

[spir]

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).

> 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).

>  This is somewhat ugly, but is the cost of having a
> singly linked list. I can guarantee anyone who knows what they are doing is
> never going to use SList, unless they are just interested in a stack type.

Precisely. It's also very well adapted for input/forward ranges, since all 
operations happen at front. What do you think? (The kind of ranges that may 
hold their contents). Note that the semantics of range iteration is clearly 
analogous to list iteration:

     while (node) {
         element = node.element;
         doSomethingWith(element);
         node = node.next;
     }

     while (! r.empty) {
         element = f.front;
         doSomethingWith(element);
         r.popFront();
     }

(Only that range vocabulary is imo rather weird:
     while (r.hasNext) {
         element = r.nextElement;
         doSomethingWith(element);
         r.moveNext();
     }
)

Denis
-- 
_________________
vita es estrany
spir.wikidot.com