std.container update

[Steven Schveighoffer]

On Thu, 27 May 2010 09:27:39 -0400, Steven Schveighoffer  
<schveiguy at yahoo.com> wrote:

> On Thu, 27 May 2010 09:23:03 -0400, Steven Schveighoffer  
> <schveiguy at yahoo.com> wrote:
>
>> On Thu, 27 May 2010 00:36:24 -0400, Andrei Alexandrescu  
>> <SeeWebsiteForEmail at erdani.org> wrote:
>>
>>> I just implemented a singly-linked list type to illustrate the  
>>> container abstraction.
>>>
>>> http://erdani.com/d/phobos/std_container.html
>>> http://erdani.com/d/phobos/container.d
>>>
>>> One interesting aspect is that SList must cooperate with Take. More  
>>> details are to be found in code, but essentially SList ranges are all  
>>> sentinel-terminated, which makes them "right-bound". If you want to  
>>> only remove a few elements from the middle of a list, you need to  
>>> construct a range that spans a limited portion of the list. I encoded  
>>> that by using the Take abstraction in std.range.
>>>
>>> Please let me know of how you find it. There are a few refinements and  
>>> ancillary functions to define, but those are pretty clear given the  
>>> rest.
>>
>> Well, one thing I don't like about it is that you cannot do O(1)  
>> insertion or removal.  insertBefore requires O(n) complexity and  
>> insertAfter requires O(m) complexity.  Removal will require O(n)  
>> complexity, even though it doesn't exist right now.
>>
>> Fast removal and insertion are key to having a linked list.  I'd  
>> suggest modifying the range so it uses a Node ** instead, which points  
>> to the _next element of the previous node of the one currently being  
>> iterated, or _root if it's the first node in the list.
>
> In fact, I'd say that it would be critical to split the insert and  
> remove functions to slow (O(n) or greater) versions and fast( O(lg(n) or  
> less)) functions.  Some algorithms may depend on fast insertion and  
> removal, such as mergesort on a linked list.
>

Actualy mergesort could not be implemented without some sort of way to  
restructure the list without allocating new nodes, requiring knowledge of  
the link structure.  I'm not sure it could be generic... I'll think about  
this a bit.

-Steve