Multi-dimension array template with dimension deduction

Question

I want to make an NDArray template which has a fixed dimension, but can be resized across each dimension.

My question is how to make it be able to deduce the dimensions in the constructor according to how many pair of {} is used? The elements in the constructor will be used to initialize some of the elements.

#include <array>
#include <iostream>

template<typename T, size_t Dimension>
class NDArray
{
    T* buffer = nullptr; //flattened buffer for cache locality
    std::array<size_t, Dimension> dimension;    //keep the current sizes of each dimension
public:
    NDArray(std::initializer_list<T> elements) : dimension{elements.size()}   //for 1D
    {
        std::cout << "Dimension = " << Dimension << '\n';
    }
    NDArray(std::initializer_list<NDArray<T, Dimension-1>> list) //how to make this works???
    {
        std::cout << "Dimension = " << Dimension << '\n';
    }
};

template<typename T, size_t N>
NDArray(const T(&)[N]) -> NDArray<T, 1>;

int main()
{
    NDArray a{ {3,4,5} };//OK, NDArray<int, 1> because of the deduction guide
    NDArray b{ {{1,2,3}, {4,5,6}} };//Nope, I want: NDArray<int, 2>
}

I don't think that's possible. Initialiser lists have no type. Well, there is `std::initializer_list`, but it's... complicated. This is one of the reasons why CTAD (class template argument deduction) doesn't work with `std::map`, which frequently uses nested braces for initialisations. — Fureeish, Sep 01 '20 at 21:43
Even if it does turn out to be impossible or, more likely, possible with but requiring so much bizzarro code that's it's more confusing rather than less, this is a good question. — user4581301, Sep 01 '20 at 21:47

score 4 · Answer 1 · answered Sep 02 '20 at 14:00

This is impossible in the general case, but possible in however many specific cases you want to spell out.

An initializer list has no type. The only way you can deduce a type for it (as in, separate from having a default template argument) is that we have two special cases spelled out in [temp.deduct.call]/1:

If removing references and cv-qualifiers from P gives std::initializer_list<P′> or P′[N] for some P′ and N and the argument is a non-empty initializer list ([dcl.init.list]), then deduction is performed instead for each element of the initializer list independently, taking P′ as separate function template parameter types P′_i and the ith initializer element as the corresponding argument. In the P′[N] case, if N is a non-type template parameter, N is deduced from the length of the initializer list. Otherwise, an initializer list argument causes the parameter to be considered a non-deduced context ([temp.deduct.type]).

This is the rule that lets the following work:

template <typename T>
constexpr auto f(std::initializer_list<T>) -> int { return 1; }

static_assert(f({1, 2, 3}) == 1);

But that isn't enough to get this to work:

static_assert(f({{1, 2}, {3, 4}}) == 1); // ill-formed (no matching call to f)

Because the rule is - okay, we can strip one layer of initializer_list but then we have to deduce the elements. And once we strip one layer of initializer list, we're trying to deduce T from {1, 2} and that fails - we can't do that.

But we know how to deduce something from {1, 2} - that's this same rule. We just have to do it again:

template <typename T>
constexpr auto f(std::initializer_list<T>) -> int { return 1; }

template <typename T>
constexpr auto f(std::initializer_list<std::initializer_list<T>>) { return 2; }


static_assert(f({1, 2, 3}) == 1);
static_assert(f({{1, 2}, {3, 4}}) == 2);

and again:

template <typename T>
constexpr auto f(std::initializer_list<T>) -> int { return 1; }

template <typename T>
constexpr auto f(std::initializer_list<std::initializer_list<T>>) { return 2; }

template <typename T>
constexpr auto f(std::initializer_list<std::initializer_list<std::initializer_list<T>>>) { return 3; }


static_assert(f({1, 2, 3}) == 1);
static_assert(f({{1, 2}, {3, 4}}) == 2);
static_assert(f({{{1, 2}, {3, 4}}, {{5, 6}, {7, 8}}}) == 3);

The same way we have the carve-out for std::initializer_list<T>, we also have the carve-out for T[N]. That works the same way, just a bit less typing:

template <typename T, size_t N>
constexpr auto f(T(&&)[N]) -> int { return 1; }

template <typename T, size_t N1, size_t N2>
constexpr auto f(T(&&)[N1][N2]) { return 2; }

template <typename T, size_t N1, size_t N2, size_t N3>
constexpr auto f(T(&&)[N1][N2][N3]) { return 3; }


static_assert(f({1, 2, 3}) == 1);
static_assert(f({{1, 2}, {3, 4}}) == 2);
static_assert(f({{{1, 2}, {3, 4}}, {{5, 6}, {7, 8}}}) == 3);

I presume there is no syntax way to expand size_t... N into something that expands into sizeof... N - dimensional array? — NoSenseEtAl, Sep 03 '20 at 16:19

Amir Kirsh · Answer 2 · 2020-09-02T17:10:38.677

You may achieve almost what you want, if you are OK with explicitly creating NDArray inside the std::initialize_list this way:

int main()
{
    NDArray a{3,4,5}; // would be deduced to NDArray<int, 1>
    NDArray b{ NDArray{1,2,3}, {4,5,6} }; // would be deduced to NDArray<int, 2>
}

Note that it is enough to explicitly add NDArray only for the first appearance of each dimension. For example, for 3D NDArray:

NDArray c { NDArray{ NDArray{8, 3}, {1, 2}, {1, 2, 3} }, 
                   {        {4, 5}, {8, 9, 7}, {2, 5} } };

To achieve that you need to have these two deduction guides:

template<typename T>
NDArray(const std::initializer_list<T>&)
                -> NDArray<T, 1>;

template<typename T, size_t DIMENSIONS>
NDArray(const std::initializer_list<NDArray<T, DIMENSIONS>>&) 
                -> NDArray<T, DIMENSIONS + 1>;

Code example: http://coliru.stacked-crooked.com/a/1a96b1eaa0717a67

Multi-dimension array template with dimension deduction

2 Answers2