Andrei Alexandrescu wrote:
> 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?

Can a container have different ElementTypes from ValueTypes?

On 05/25/2010 09:07 PM, Walter Bright wrote:
> Andrei Alexandrescu wrote:
>> 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?
>
> Can a container have different ElementTypes from ValueTypes?

For a hash K->V, KeyType is K, ValueType is V, and ElementType is Tuple!(K, V).

Andrei

Andrei Alexandrescu wrote:
> On 05/25/2010 09:07 PM, Walter Bright wrote:
>> Andrei Alexandrescu wrote:
>>> 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?
>>
>> Can a container have different ElementTypes from ValueTypes?
> 
> For a hash K->V, KeyType is K, ValueType is V, and ElementType is Tuple!(K, V).

Ok, that makes it clear, and it needs to be in the spec.

On 05/25/2010 06:04 PM, Steven Schveighoffer wrote:
> What about the purge function of dcollections (i.e. removal while
> iterating)?

I changed remove and softRemove to return a range positioned to after the removed stuff.

Andrei

Andrei Alexandrescu Wrote:

> 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.
> >>
> >> 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.

softXXX might be better named safeXXX or stableXXX.  The names might be more suggestive of preserving iteration.

The doc isn't quite clear whether make is a member function or standalone.  I assume it's standalone, but that's worth firming up.

> > 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].

I second the request for the name "replace".  Despite the consistency, I think replace is clear to programmers as well as being more familiar and comfortable.  Also, the operation really isn't "insert instead", it's "delete then insert instead".  So there is lack of symmetry because it removes elements while the other does not.

Another  issue I see is that opIndex and its brethren takes KeyType, but for something like vector, this should be size_t..  I don't think you want ElementType to be tuple!(size_t, ElementType) in this case.

Related to this, do you intend removal of a single element to use remove(range) or removeKey?

Finally, opSlice(begin, end) is not there.  Was this intentional or overlooked?

Jerry

Andrei Alexandrescu 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.

Looks great to me. A couple of comments:

> 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.

The softXXX primitives are listed as having the same complexity as the non-soft primitives. Should it be explicitly stated that non-soft should always be at least as fast as soft? (So that if you don't need the soft guarantee, you should always use the non-soft primitive?)

Also, I agree with Jerry that something like "stable" would be more intuitive than "soft". I guess it's not exactly the same meaning as stableSort, but it's pretty close. A problem with the name "soft" is that it's a harder, stronger guarantee! It seems to be a concept of a "tame" removal as opposed to reckless, "savage" removal?



> 
> 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

Andrei A.:

>I hope to work with ranges only.<

Programming life is complex, you can't fit all of it in one schema ("A foolish consistency is the hobgoblin of little minds").


>Will look into it, sounds like an implementation matter.<

Yes, right. But to implement this idea the foreach() has to change a bit, to set the flag in nonrelease mode. If implemented this idea lessens a bit the need for the stable ("soft") methods.


>Probably some trees could save some state if they exploit O(log n) length.<

In general a length can be O(n) if for example you want to compute it on a linked list that doesn't keep the number of items inserted. Are you going to just not give a length attribute for such linked lists (so users have to use something like walkLength)?

Bye,
bearophile

Andrei Alexandrescu Wrote:

> On 05/25/2010 09:07 PM, Walter Bright wrote:
> > Andrei Alexandrescu wrote:
> >> 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?
> >
> > Can a container have different ElementTypes from ValueTypes?
> 
> For a hash K->V, KeyType is K, ValueType is V, and ElementType is Tuple!(K, V).
> 
> Andrei

How about simple arrays? There's a lot of similarity between T[] and T[int]...

On 05/26/2010 11:44 AM, bearophile wrote:
> Andrei A.:
>
>> I hope to work with ranges only.<
>
> Programming life is complex, you can't fit all of it in one schema ("A foolish consistency is the hobgoblin of little minds").
>

Couldn't you just define opApply where you need it and it will be used where foreach is used by default, anyway?

>
>> Will look into it, sounds like an implementation matter.<
>
> Yes, right. But to implement this idea the foreach() has to change a bit, to set the flag in nonrelease mode. If implemented this idea lessens a bit the need for the stable ("soft") methods.
>
>
>> Probably some trees could save some state if they exploit O(log n) length.<
>
> In general a length can be O(n) if for example you want to compute it on a linked list that doesn't keep the number of items inserted. Are you going to just not give a length attribute for such linked lists (so users have to use something like walkLength)?
>

Isn't that a good thing? If I know length is fast, I can use it without worries, but if it might be O(n) you need to avoid it.

On 05/26/2010 04:44 AM, bearophile wrote:
> Andrei A.:
>
>> I hope to work with ranges only.<
>
> Programming life is complex, you can't fit all of it in one schema
> ("A foolish consistency is the hobgoblin of little minds").
>
>
>> Will look into it, sounds like an implementation matter.<
>
> Yes, right. But to implement this idea the foreach() has to change a
> bit, to set the flag in nonrelease mode. If implemented this idea
> lessens a bit the need for the stable ("soft") methods.
>
>
>> Probably some trees could save some state if they exploit O(log n)
>> length.<
>
> In general a length can be O(n) if for example you want to compute it
> on a linked list that doesn't keep the number of items inserted. Are
> you going to just not give a length attribute for such linked lists
> (so users have to use something like walkLength)?

Correct, some collections (notably SList) will simply not provide length().

In fact I will implement SList soon as an illustration of the design.

Andrei