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.


Andrei

On Tue, 25 May 2010 18:27:32 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@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

Andrei Alexandrescu:

>I feel this design is pretty close to what I really wanted.<

Good :-)

How is opApply playing in the design of the containers? Can opSlice return a struct that defines opApply?


> There are a bunch of "soft" primitives. Those are meant to put a stop to the iterator invalidation problems experienced in the STL.

I can suggest another thing, that doesn't replace this idea, but can make the nonsoft primitives a little safer when the program is compiled in nonrelease mode: http://d.puremagic.com/issues/show_bug.cgi?id=4179


>any container must be a reference type, whether implemented as a class or struct.<

This probably makes their usage simpler, so this can be the right decision. But then you can't define something like a TinyHashSet or a StaticBitSet that are better allocated on the stack... (a StaticBitSet is a struct template I have defined, at compile time you give it its length and it gets allocated on the stack, and represents a set of integers in an intgerval, or something similar).

Why is length O(log(n))? If a linked list has no length field, to compute its length it has to scan all of it.

make(): this has just killed the new :-)

Among the standard primitives is it useful to have something to ask the actual computational complexity of a specific operation of a specific container? There are some ways to implement this, the simplest is to define enum with the most common complexities, and then a collection can contain an enum (const) value for each operation, something like:
enum lengthComplexity = CompComplexity.linear;
I don't know if this can be useful (to choose collections, to infer code complexity, etc).

Bye,
bearophile

Andrei Alexandrescu wrote:
> I've uploaded a work in progress on the container design here:

Great! Some nitpicky comments:

1. What's the difference between a value and an element?

2. What's the affect of clear() on the capacity?

3. Shouldn't KeyTypes be a type tuple?

On 05/25/2010 06:04 PM, Steven Schveighoffer wrote:
> On Tue, 25 May 2010 18:27:32 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail@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

On 05/25/2010 06:18 PM, bearophile wrote:
> Andrei Alexandrescu:
>
>> I feel this design is pretty close to what I really wanted.<
>
> Good :-)
>
> How is opApply playing in the design of the containers? Can opSlice return a struct that defines opApply?

I hope to work with ranges only.

>> There are a bunch of "soft" primitives. Those are meant to put a stop to
>> the iterator invalidation problems experienced in the STL.
>
> I can suggest another thing, that doesn't replace this idea, but can make the nonsoft primitives a little safer when the program is compiled in nonrelease mode: http://d.puremagic.com/issues/show_bug.cgi?id=4179

Will look into it, sounds like an implementation matter.

>> any container must be a reference type, whether implemented as a class or struct.<
>
> This probably makes their usage simpler, so this can be the right decision. But then you can't define something like a TinyHashSet or a StaticBitSet that are better allocated on the stack... (a StaticBitSet is a struct template I have defined, at compile time you give it its length and it gets allocated on the stack, and represents a set of integers in an intgerval, or something similar).

I'm guessing some value container-like entities wouldn't harm if they can easily be converted to references.

> Why is length O(log(n))? If a linked list has no length field, to compute its length it has to scan all of it.

I forgot the case I had in mind. I know that opSlice() must be O(log n) for e.g. tree traversals. Probably some trees could save some state if they exploit O(log n) length.

> make(): this has just killed the new :-)
>
> Among the standard primitives is it useful to have something to ask the actual computational complexity of a specific operation of a specific container? There are some ways to implement this, the simplest is to define enum with the most common complexities, and then a collection can contain an enum (const) value for each operation, something like:
> enum lengthComplexity = CompComplexity.linear;
> I don't know if this can be useful (to choose collections, to infer code complexity, etc).

If it can be used gainfully, that would be great. Intriguing idea.


Andrei

On 05/25/2010 07:35 PM, Walter Bright wrote:
> Andrei Alexandrescu wrote:
>> I've uploaded a work in progress on the container design here:
>
> Great! Some nitpicky comments:
>
> 1. What's the difference between a value and an element?

None.

> 2. What's the affect of clear() on the capacity?

There is no guaranteed effect.

> 3. Shouldn't KeyTypes be a type tuple?

Yes. At the end of the day you must be able to say KeyTypes!3 to get the fourth type there. You say it should be KeyTypes[3]. I see tuple trouble, sigh. With a template I feel I have more control.


Andrei

Andrei Alexandrescu wrote:
> On 05/25/2010 07:35 PM, Walter Bright wrote:
>> Andrei Alexandrescu wrote:
>>> I've uploaded a work in progress on the container design here:
>>
>> Great! Some nitpicky comments:
>>
>> 1. What's the difference between a value and an element?
> 
> None.

Then I suggest sticking with one or the other throughout the spec. Also, there's both an ElementType and a ValueType.


>> 2. What's the affect of clear() on the capacity?
> 
> There is no guaranteed effect.

Should say so in the spec.


>> 3. Shouldn't KeyTypes be a type tuple?
> 
> Yes. At the end of the day you must be able to say KeyTypes!3 to get the fourth type there. You say it should be KeyTypes[3]. I see tuple trouble, sigh. With a template I feel I have more control.

The reason I prefer a tuple for this is then I can ask KeyTypes.length, whereas with the template that's not specified by the spec.

On 05/25/2010 08:31 PM, Walter Bright wrote:
> Andrei Alexandrescu wrote:
>> On 05/25/2010 07:35 PM, Walter Bright wrote:
>>> Andrei Alexandrescu wrote:
>>>> I've uploaded a work in progress on the container design here:
>>>
>>> Great! Some nitpicky comments:
>>>
>>> 1. What's the difference between a value and an element?
>>
>> None.
>
> Then I suggest sticking with one or the other throughout the spec. Also,
> there's both an ElementType and a ValueType.

Sorry, I was wrong. ValueType is defined for keyed containers to mean the mapped type. Should I call it MappedType?

Andrei

On 05/25/2010 08:31 PM, Walter Bright wrote:
> Andrei Alexandrescu wrote:
>>> 2. What's the affect of clear() on the capacity?
>>
>> There is no guaranteed effect.
>
> Should say so in the spec.

I guess if it's missing then it's implied.

>>> 3. Shouldn't KeyTypes be a type tuple?
>>
>> Yes. At the end of the day you must be able to say KeyTypes!3 to get
>> the fourth type there. You say it should be KeyTypes[3]. I see tuple
>> trouble, sigh. With a template I feel I have more control.
>
> The reason I prefer a tuple for this is then I can ask KeyTypes.length,
> whereas with the template that's not specified by the spec.

OK.


Andrei