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.