std.container update
Steven Schveighoffer
schveiguy at yahoo.com
Thu May 27 06:23:03 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.
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.
-Steve
More information about the Digitalmars-d
mailing list