On 05/25/2010 06:04 PM, Steven Schveighoffer wrote:
On Tue, 25 May 2010 18:27:32 -0400, Andrei Alexandrescu
<seewebsiteforem...@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)?
Yes, but the cursor would have to pass scrutiny for usefulness just like
anything else.
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 think it got lost when I reordered the code (I did a major reshuffling
just before posting). I put it back.
I don't like insertInstead, can we make it replace?
replace was the original name. insertInstead is consistent with the
other two, so we have (softI|i)nsert[Before|After|Instead].
What about the purge function of dcollections (i.e. removal while
iterating)?
Removal while iterating is achieved through different means. I need to
think through the details a bit more, but in essence it doesn't have to
be a primitive. The primitives should allow implementation of a generic
function that removes elements that satisfy a condition, something as
follows:
If the collection supports softRemove, if you want to remove an element
while iterating with a range r, you can say coll.softRemove(r.take(1)).
If it doesn't, I'm thinking of allowing the erase/remove idiom
(http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Erase-Remove). For
that, remove should return a range positioned right after the removed
element. Let me think a bit more about that.
What about opApply? Without opApply, you cannot use foreach to get both
keys and values.
I'd like to design without opApply as part of the primitives. You can
use foreach to iterate tuples of 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.
Sounds promising!
Andrei
