Containers

[deadalnix]

I want to start working on a container library. Interestingly 
enough, I don't think we have what we need on that front.

I'll describe here what are the design I intend to go for, and 
the rationales for it, but before, there is an unsolved problem 
that I don't know how to work around that is somewhat of a 
blocker. If one of you guys have an idea how to solve it, I'm 
taking. If I'm being honest, this is probably the most important 
problem that need to be solved for D right now. That problem is 
turtling down type qualifiers.

For instance, if we have a Vector!T, then we want it to convert 
to a Vector!(const T) and we want const(Vector!T) == 
const(Vector!(const T)), all of it implicitly. Same goes for 
other qualifiers.

To put it bluntly, I have no idea how to achieve this. And I 
don't think we'll have a good set of collection before this is 
sorted out.

Now onto the design:
  - Value types. It is very easy to turn a value into a reference 
type, not so much the other way around. reference type also come 
with a bag of edges cases, like the collection being null vs 
empty, that cause confusion and problems in practice.
  - COW. Value type collection can be very expensive to work with 
if the eagerly copy everything. On the other hand, COW ensures 
copies are cheap. There are also very common use case that are 
well served by COW collections, for instance, when one wants 
value types for collection that are infrequently changes - but 
you don't know or can't prove that they won't.
  - Small collection features. As every engineer, but no 
mathematician will tell you, is that most numbers are small. It 
is also true of collection sizes. In order to speed things up for 
collection that are expected to be small, being able to specify 
Vector!(T, 8) to reserve 8 slots for elements, in the base 
collection, and only allocate on heap if the collection size 
grows past this. LLVM has a collection library doing so and it is 
the most useful thing in the world (see 
https://www.youtube.com/watch?v=vElZc6zSIXM for more details).
  - Not expose much of its internals. This like iterators being 
raw pointers (or the result of using the in operator) for 
instance, impose constraint on the internal that almost always 
end up costing a ton of perf as new techniques are discovered 
(recent exemples include open addressing with SSE probing for 
instance). All of this needs to be wrapped.

I have a good idea how to solve all these problems. I have no 
idea how to solve the type qualifier one. I need help.