On Tue, 25 May 2010 18:27:32 -0400, Andrei Alexandrescu
<[email protected]> 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
