This is not strictly related to C++ but its type system serves to illustrate the problem well.
We have a generic template
Container<T>(such as a
std::vector<T>) which stores an unspecified number of elements of the same type
Ton the heap. Each element is allocated and deallocated via the constructor and destructor of
melements on the heap (so
Mitself is a kind of container). However, the value of
mis not known at compile time, so it cannot be used as a template parameter to
- If we try to use a type
Container<M>, accessing the elements of
Minside this container would require two pointer dereferences, which in general has worse performance than if all elements of
Mwere laid out contiguously.
- Create a separate class
ContainerFixed<T>that manages the memory of
Tis assumed to have the same size throughout the container.
Twould also have to exchange information about its storage with the containing class. However, if we implement another kind of container, then we have to repeat this process again.
The problem arises because the container class is oblivious of the storage requirements of
T so it defers the allocation to
T itself; if the container had known that
T only requires a fixed (though not known at compile time) number of elements then this issue could have been avoided.
Now I feel as though that if there was some way to communicate to the container that
M has a definite size
m (as in
M<m>, which is not legal in C++), then from the type signature of
Container<M<m> > one can potentially deduce that a faster allocation scheme is possible. (It's a bit like dependent types, in a way.) That is, any
Container1<Container2<m> > can be allocated more efficiently as a "flattened" container.
What would be a more general solution to this problem? I don't think this is something that can be easily solved in C++ (feel free to prove me wrong), so I would certainly like to hear if this is something that other languages can solve in a much simpler way (perhaps with more sophisticated type systems).