std.container update

Steven Schveighoffer schveiguy at yahoo.com
Thu May 27 06:46:31 PDT 2010


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.


I have another general question in general about these collections.

Ranges fix a very bad problem with iterators -- non-matching begin and end  
iterators.  For example, passing a begin from one list and and end from  
another.

However, all your range functions such as remove, insertBefore, etc. are  
called via the container type, using a range as an argument.  But there  
can be no static verification that a range actually is part of a given  
container.  Should there be some requirement that a container validates  
that a range is part of the container before performing the operation?   
This is the case for dcollections.

In your current implementation of SList, verification seems incidental for  
insertBefore because you must find the previous node from the root anyways  
(and that will throw on enforce if it cannot find it).  But insertAfter  
does not, so something like this will compile, run, and result in strange  
behavior:

auto sl1 = make(SList!int, 1, 2, 3, 4, 5); // I may not have this correct,  
but it's not important
auto sl2 = make(SList!int, 6, 7, 8, 9, 10);

auto r1 = sl1[];
r1.popFront();
r1.popFront();

auto r2 = take(r1, 2);
sl2.insertAfter(r2, 666); // actually inserts into sl1

-Steve


More information about the Digitalmars-d mailing list