Template argument order issue in make_* functions that return an array

[dsharlet]

When allocators are expensive to construct (e.g. auto_allocator uses a lot of stack space), the current make_array and similar helpers are problematic, because they use a default argument for the allocator value, and a default template type argument.

An example of currently problematic code is this:

auto temp = make_array(other.shape(), auto_allocator<T, 32 * 32 * 4>());

i.e. a temporary array the same shape as another array, but possibly placed on the stack.

The problem with this is that there are two arrays of size 32 * 32 * 4 * sizeof(T) on the stack: one owned by temp, the other just created to make the call to make_array and never actually used.

It would be better if we could specify the type of the allocator, without ever instantiating it.

We clearly need to split each instance of make_* into two overloads: one with an allocator argument, and one without (to avoid the default argument instance). The overload that takes an allocator instance is not a problem, template type deduction is fine in this case (and we don't even need a default value of the allocator type).

However, the overload without it is problematic:

template <typename T, typename Shape, typename Alloc = std::allocator<T>>
auto make_array(const Shape& shape) {
   ...
}

We want to be able to take the default allocator 99% of the time. But when we want to specify the type, sometimes specifying the type of the shape is hard, e.g. if using make_compact on a shape with non-trivial constant extents/strides.

So we want the Alloc template parameter to be earlier in the list, at least before Shape, but then Shape needs a default type. Maybe just giving this a dummy type, maybe even just void is reasonable? That would hopefully not interfere with type deduction, and making an array with no shape argument would be an error anyways?