This is not strictly related to C++ but its type system serves to illustrate the

Question

This is not strictly related to C++ but its type system serves to illustrate the problem well.

Assume:

We have a generic template Container<T> (such as a std::vector<T>) which stores an unspecified number of elements of the same type T on the heap. Each element is allocated and deallocated via the constructor and destructor of T.

A type M that stores m elements on the heap (so M itself is a kind of container). However, the value of m is not known at compile time, so it cannot be used as a template parameter to M.

Problem:

If we try to use a type Container<M>, accessing the elements of M inside this container would require two pointer dereferences, which in general has worse performance than if all elements of M were laid out contiguously.
Non-ideal solution:

Create a separate class ContainerFixed<T> that manages the memory of T directly, if T is assumed to have the same size throughout the container. T would 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).

Explanation / Answer

I think you could more or less solve this by having an API similar to allocators, whereby a container could specify how to allocate its metadata and elements contiguously. That is, a container would provide an

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.