container stuff

[Andrei Alexandrescu]

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