container stuff

[Steven Schveighoffer]

On Tue, 25 May 2010 18:27:32 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> I've uploaded a work in progress on the container design here:
>
> http://erdani.com/d/phobos/std_container.html
>
> It's deceptively simple - the entire design is a nomenclature, really.  
> Any given container may choose to implement whichever primitives it can,  
> if (and only if) it can satisfy the requirements. Beyond that, each  
> container can define its own primitives.
>
> The design is not fancy, which doesn't worry me in the least because I  
> was aiming for the right design, not a fancy design. I feel this design  
> is pretty close to what I really wanted.
>
> The major players are the containers themselves and the ranges they  
> define. Most operations are defined in terms of ranges, not containers.  
> The containers only need to support a modicum of primitives that affect  
> the topology of containers, plus a few convenience functions.
>
> There are a bunch of "soft" primitives. Those are meant to put a stop to  
> the iterator invalidation problems experienced in the STL. The container  
> implementor may alias softXyz to xyz if she knows the operation won't  
> mess the ranges currently iterating the container (which is the case for  
> most node-based containers). I haven't yet discussed subtler cases in  
> which a range starts with a removed element etc., but I plan to.
>
> So, this is it really: the containers specification is a collection of  
> capabilities. A given container picks the ones it can support  
> meaningfully, and user code has the specification as semantic and  
> complexity guarantees.
>
> This design is quite far removed from Steve's, which makes the  
> integration with dcollection tenuous. But at a minimum, maybe we can  
> work out something in which Steve offers, with credit, implementation  
> for this design and also offers dcollections as a separate library.

I take it from the comment in the docs that cursors can be an auxiliary  
range?  Is there any reason not to define a mandatory cursor type (a  
cursor is elementary to define if a range is definable)?

There is no remove(Range) function, this is a bad omission.  It's one of  
the main reasons I created dcollections (quick element removal when  
element lookup is not quick).

I don't like insertInstead, can we make it replace?

What about the purge function of dcollections (i.e. removal while  
iterating)?

What about opApply?  Without opApply, you cannot use foreach to get both  
keys and values.

I can probably submit my basic implementations, and use them from std.x to  
implement dcollections.  This way, the complex pieces are shared.   
Dcollections definitely fills needs that this collection package doesn't,  
and it should be mostly compatible.

-Steve