container stuff

[Andrei Alexandrescu]

On 05/25/2010 06:04 PM, Steven Schveighoffer wrote:
> 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)?

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