container stuff

[Don]

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