N-dimensional std::array initialized with templates

Question

Consider the following code:

#include <iostream>
#include <array>

template <typename, int, int...> struct NArray;

template <typename T, int NUM_DIMENSIONS, int N>
struct NArray<T, NUM_DIMENSIONS, N> {
    using type = std::array<T, N>;
};

template <typename T, int NUM_DIMENSIONS, int FIRST, int... REST>
struct NArray<T, NUM_DIMENSIONS, FIRST, REST...> {
    using type = std::array<typename NArray<T, NUM_DIMENSIONS, REST...>::type, FIRST>;
};

template <typename T, int NUM_DIMENSIONS, int... N>
typename NArray<T, NUM_DIMENSIONS, N...>::type NDimensionalArray() {
    typename NArray<T, NUM_DIMENSIONS, N...>::type nArray;
    return nArray;
}

int main() {
    const auto nArray = NDimensionalArray<int,4, 2,4,5,3>();
}

What I want is to be able to extend the template pack of NDimensionalArray with more int values so that certain values are initialized to some specified fixed value. For example,

auto a = NDimensionalArray<bool,4, 2,4,5,3, 1,2,3,2, 0,0,2,1>(true);

will return a 2x4x5x3 4-dimensional std::array with a[1][2][3][2] = true and a[0][0][2][1] = true, and every other element false. But I'm having issues with multiple template packs and can't seem to get it working. Any help would be appreciated. Thanks.

I think I had kind of a [related question once](http://stackoverflow.com/questions/18251815/creating-an-array-initializer-from-a-tuple-or-variadic-template-parameters). Please don't care too much about the downvote on the question, check the useful answer. — πάντα ῥεῖ, Oct 31 '14 at 20:51
What is your algorithm for what the ints mean? How do you know that it's a 4-D array with 2 elems set vs a 2-D array with 5 elems set? — Barry, Oct 31 '14 at 20:52
You can't have multiple non-deduced parameter packs like that, the compiler has no way of knowing where one ends and another begins — Brian Bi, Oct 31 '14 at 20:53
Ok guys, I've edited my code above so now the compiler knows how many dimensions the array has (NUM_DIMENSIONS). Does that help? — prestokeys, Oct 31 '14 at 20:55
@prestokeys What you would need here is a specialization on `NUM_DIMENSIONS=0` and use `NUM_DIMENSIONS-1` when you recurse. That is part of the answer, anyway. — cdhowie, Oct 31 '14 at 20:55
Doesn't matter, you still can't have multiple non-deduced parameter packs. Standard says: "A template parameter pack of a function template shall not be followed by another template parameter unless that template parameter can be deduced from the parameter-type-list of the function template or has a default argument" — Brian Bi, Oct 31 '14 at 20:56
Might be a lot simpler to code if you just group the elements... `auto a = NDimensionalArray, seq<1, 2, 3, 2>, seq<0, 0, 2, 1>>(true);` — Barry, Oct 31 '14 at 20:56
@Brian Not really, if you know how many dimensions there are you can have a specialization at `NUM_DIMENSIONS=0` that switches logic to interpret the contents of the pack differently. — cdhowie, Oct 31 '14 at 20:57
@cdhowie OK, I see what you're saying. In any case, the primary template has to be declared with a *single* parameter pack. — Brian Bi, Oct 31 '14 at 21:02
Ok, so although Barry's wrapper idea may work, I do prefer the solution of the form `template `. — prestokeys, Oct 31 '14 at 21:05
@prestokeys Note that the compiler's limit on template recursion could bite you, though. If you use the `seq<>` approach then it must recurse only 3-4 times versus 12; you'll get about four times the number of recursive calls doing it with a flat pack. — cdhowie, Oct 31 '14 at 21:06
Ok, `template ` I'll give a go first. But there is no hope for `template ` to work? — prestokeys, Oct 31 '14 at 21:09
Man I just started writing this... just doing the assignments for `a[1][2][3][2] = true` part is ridiculous. — Barry, Oct 31 '14 at 21:09
@prestokeys Not when the type of `SEQ` is the same type as `DIMENSIONS`, no. The compiler can't tell where one pack ends and the next begins. — cdhowie, Oct 31 '14 at 21:19
@cdhowie. Oh but SEQ is actually of type `template class SEQ` though, while DIMENSIONS is int.... Yikes, I don't think I've ever used the syntax for when a template template is itself a pack before. I have to look up that syntax now. — prestokeys, Oct 31 '14 at 21:21
@prestokeys Oh... yeah, my eyes are starting to glaze over a bit. I'm pretty good with templates and specializations and SFINAE stuff, but once template templates appear I lose focus pretty quickly. — cdhowie, Oct 31 '14 at 21:22
Uh, I gave it a try -- but it's ugly: http://coliru.stacked-crooked.com/a/f28b7519189a130d Basically it's *initializing* each array element with a default value or a special value, based on the input parameters. — dyp, Oct 31 '14 at 21:52

Barry · Accepted Answer · 2014-11-04T16:05:27.160

5

Well here's a working solution. If somebody can improve upon it, I would be very interested in seeing it because I don't know any other way to do it.

#include <iostream>
#include <array>
#include <cstring>

template <int... > struct seq {};

template <typename, int...> struct NArray;

template <typename T, int N>
struct NArray<T, N> {
    using type = std::array<T, N>;
};

template <typename T, int FIRST, int... REST>
struct NArray<T, FIRST, REST...> {
    using type = std::array<typename NArray<T, REST...>::type, FIRST>;
};

template <typename T, typename Dim>
struct make_narray;

template <typename T, int... N>
struct make_narray<T, seq<N...>>
{
    using type = typename NArray<T, N...>::type;
};

template <typename T>
T& get(T& val, seq<>)
{
    return val;
}

template <typename NA, int E0, int... Es>
auto get(NA& arr, seq<E0, Es...>)
-> decltype(get(arr[E0], seq<Es...>{}))
{
    return get(arr[E0], seq<Es...>{});
}

template <typename T, typename Dim, typename... Elems>
typename make_narray<T, Dim>::type
NDimensionalArray(T val)
{
    typename make_narray<T, Dim>::type narray{};
    auto _{get(narray, Elems{}) = val ...};  // Quick initialization step!
    return narray;
}

int main() {
    auto a = NDimensionalArray<bool, seq<2, 4, 5, 3>, seq<1, 2, 3, 2>, seq<0, 0, 2, 1>>(true);

    std::cout << std::boolalpha;
    std::cout << a[0][0][0][0] << std::endl; // prints false
    std::cout << a[1][2][3][2] << std::endl; // prints true
    std::cout << a[0][0][2][1] << std::endl; // prints true
}

edited Nov 04 '14 at 16:05

answered Oct 31 '14 at 21:29

Barry

286,269
29
621
977

+1 Nice job. I'd add a static_assert to check that the number of indices is good as a first thing inside `NDimensionalArray`. – jrok Oct 31 '14 at 21:32
Replacing `narray.fill(false);` with `narray.fill(T{});` doesn't seem to compile. But `memset(&narray, T{}, sizeof(narray));` does work. – prestokeys Oct 31 '14 at 21:52
@prestokeys my bad, I forgot it's a multi dimensional array. Rolled back the edit. – jrok Oct 31 '14 at 21:57
Great answer! I was able to get rid of the recursion with a pack expansion trick so I edited that in. I also think you can get rid of the `memset` by replacing the initialization with an empty brace (i.e `typename make_narray::type narray{};`) which will zero-initialize each array. – David G Oct 31 '14 at 22:49
Right, you don't. You can remove the `assign` struct entirely and do `auto l{(0, (get(narray, Elems{}) = val), 0)...};` under the array declaration. – David G Oct 31 '14 at 23:35
Not only can the `assign` struct can be removed, but so can the comma operator. Just place `auto l{get(narray, Elems{}) = val ...};` right after the line `typename make_narray::type narray{};` and the initialization is done. – prestokeys Nov 04 '14 at 15:57
@prestokeys Thanks! Even better. I updated the answer. – Barry Nov 04 '14 at 16:02
@prestokeys I prefer `_` to `l`... looks to much like `1` – Barry Nov 04 '14 at 16:06
Whatever name we use, unfortunately there is no way to remove the compiler warning from GCC (set with -Wall) that the variable is not used, without adding some dummy line to use it. Is there not a way to make that initializer_list anonymous? – prestokeys Nov 04 '14 at 16:15

Piotr Skotnicki · Answer 2 · 2014-11-01T10:32:14.250

The exact syntax you wanted NDimensionalArray<bool,4, 2,4,5,3, 1,2,3,2, 0,0,2,1>(true), in both C++14 and C++11 (second demo):

#include <iostream>
#include <iomanip>
#include <array>
#include <tuple>
#include <utility>
#include <type_traits>
#include <cstddef>

template <typename, int, int...> struct NArray;

template <typename T, int NUM_DIMENSIONS, int N>
struct NArray<T, NUM_DIMENSIONS, N>
{
    using type = std::array<T, N>;
};

template <typename T, int NUM_DIMENSIONS, int FIRST, int... REST>
struct NArray<T, NUM_DIMENSIONS, FIRST, REST...>
{
    using type = std::array<typename NArray<T, NUM_DIMENSIONS, REST...>::type, FIRST>;
};

template <typename A, typename T>
void assign(A& arr, const T& value)
{
    arr = value;
}

template <int I, int... Is, typename A, typename T>
void assign(A& arr, const T& value)
{
    assign<Is...>(arr[I], value);
}

template <int SIZE, int PACK, int... Ind, typename T, typename A, std::size_t... Is>
auto set(const T& value, A& arr, std::index_sequence<Is...> seq)
    -> std::enable_if_t<(SIZE*PACK == sizeof...(Ind))>
{    
}

template <int SIZE, int PACK, int... Ind, typename T, typename A, std::size_t... Is>
auto set(const T& value, A& arr, std::index_sequence<Is...> seq)
    -> std::enable_if_t<(SIZE*PACK < sizeof...(Ind))>
{    
    constexpr auto t = std::make_tuple(Ind...);
    assign<std::get<PACK*SIZE+Is>(t)...>(arr, value);
    set<SIZE, PACK+1, Ind...>(value, arr, seq);
}

template <typename T, int DIMS, int... N, std::size_t... Is>
auto make_narray(const T& value, std::index_sequence<Is...> seq)
{
    constexpr auto t = std::make_tuple(N...);
    typename NArray<T, DIMS, std::get<Is>(t)...>::type arr{};
    set<DIMS, 1, N...>(value, arr, seq);
    return arr;
}

template <typename T, int DIMS, int... N>
auto NDimensionalArray(const T& value)
{    
    return make_narray<T, DIMS, N...>(value, std::make_index_sequence<DIMS>{});
}

int main()
{
    auto a = NDimensionalArray<bool,4, 2,4,5,3, 1,2,3,2, 0,0,2,1>(true);
    std::cout << std::boolalpha;
    std::cout << a[1][2][3][2] << std::endl; // ~~~~^
    std::cout << a[0][0][2][1] << std::endl; // ~~~~~~~~~~~~^
    std::cout << a[0][0][0][0] << std::endl; // (not set)
}

Output:

true
true
false

DEMO (C++14)

DEMO 2 (C++11)

Just curious. 3 interesting and different solutions posted, and each solver saying that their solutions are ugly. Does that mean that the complexity of the question inevitably results in an ugly solution, or that their solutions are only the "first draft" that they suspect can and should be improved? — prestokeys, Nov 01 '14 at 02:30
@prestokeys Actually when I now look at it, it's not *that bad*, but still hard to read. I added C++11 version, and I don't think this particular approach can be simplified more. The *ugliness* is a result of splitting the pack into sub-sequences and the need of accessing array's elements using that subsequences. It also produces a lot of instantiations of each function. But at least you have the syntax you wanted, without `seq<>` wrappers. — Piotr Skotnicki, Nov 01 '14 at 10:00
@prestokeys Yeah neither are like the worst code I've ever read, but it's fundamentally a complicated problem that you're asking right... throw a bunch of stuff at a template and have it do different things with it? If explaining the question is so complicated, it's likely the answers will be too. — Barry, Nov 01 '14 at 16:08
@PiotrS. +1. Not having to write out the return types in those functions definitely helps clean stuff up :) — Barry, Nov 01 '14 at 16:08
The C++11 solution does not need NArraySignature. Can just use `typename NArray>::value...>::type` for MakeNArray's return type, and `decltype(MakeNArray(value, make_index_sequence{}))` for NDimensionalArray's return type (tested). — prestokeys, Nov 04 '14 at 17:18

prestokeys · Answer 3 · 2016-04-09T03:38:58.627

Solution with the initializing positions in the argument pack ARGS&&... args instead:

#include <array>
#include <iostream>
#include <deque>

template <typename, std::size_t...> struct NArray;

template <typename T, std::size_t N>
struct NArray<T,N> {
    using type = std::array<T,N>;
};

template <typename T, std::size_t First, std::size_t... Rest>
struct NArray<T, First, Rest...> {
    using type = std::array<typename NArray<T, Rest...>::type, First>;
};

template <typename E, typename Container, typename T>
void assign (E& element, Container&&, const T& v) { element = v; }

template <typename Subarray, std::size_t N, typename Container, typename T>
void assign (std::array<Subarray, N>& narray, Container&& pos, const T& v) {
    const std::size_t index = pos.front();
    pos.pop_front();
    assign (narray[index], pos, v);
}

template <typename T, int... Dimensions, typename... Args>
typename NArray<T, Dimensions...>::type NDimensionalArray (const T& value, Args&&... args) {
    typename NArray<T, Dimensions...>::type narray{};
    const auto initializer = {std::forward<Args>(args)...};
    const int groupSize = sizeof...(Dimensions),  numGroups = initializer.size() / groupSize;
    for (std::size_t i = 0;  i < numGroups;  i++)
        assign (narray, std::deque<std::size_t>(initializer.begin() + i*groupSize, initializer.begin() + (i+1)*groupSize), value);
    return narray;
}

int main() {
    const auto multiArray = NDimensionalArray<double, 5,6,7,8,9> (3.14,  1,2,3,2,4,  3,3,2,1,2,  0,1,3,1,2);
    std::cout << multiArray[1][2][3][2][4] << '\n';  // 3.14
    std::cout << multiArray[3][3][2][1][2] << '\n';  // 3.14
    std::cout << multiArray[0][1][3][1][2] << '\n';  // 3.14
}

score 0 · Answer 4 · answered Apr 09 '16 at 01:15

Here is Piotr's solution tidied up a bit, by removing his enable_if specializations and using the index trick once again instead. Also, I've generalized to the following example syntax for any number of set values:

makeNDimensionalArray<char, I<3,6,5,4>, I<2,4,3,2, 0,1,2,3, 1,2,4,3>, I<0,0,0,0, 2,3,1,2>, I<1,1,2,1>>('a','b','c')

where I<3,6,5,4> sets the multi-array's dimensions. Then I<2,4,3,2, 0,1,2,3, 1,2,4,3> sets those three indexed positions of the array to 'a', I<0,0,0,0, 2,3,1,2> sets those two indexed positions of the array to 'b', and so forth.

#include <iostream>
#include <array>
#include <tuple>
#include <utility>

template <typename, std::size_t, std::size_t...> struct NArray;

template <typename T, std::size_t NumDimensions, std::size_t N>
struct NArray<T, NumDimensions, N> {
    using type = std::array<T, N>;
};

template <typename T, std::size_t NumDimensions, std::size_t First, std::size_t... Rest>
struct NArray<T, NumDimensions, First, Rest...> {
    using type = std::array<typename NArray<T, NumDimensions, Rest...>::type, First>;
};

template <typename T, std::size_t... Dimensions>
using NDimensionalArray = typename NArray<T, sizeof...(Dimensions), Dimensions...>::type;

template <typename T, typename Dimensions> struct NArrayFromPack;

template <typename T, template <std::size_t...> class P, std::size_t... Dimensions>
struct NArrayFromPack<T, P<Dimensions...>> : NArray<T, sizeof...(Dimensions), Dimensions...> {
    static constexpr std::size_t num_dimensions = sizeof...(Dimensions);
};

template <typename A, typename T>
void setArrayValue (A& a, const T& t) { a = t; }

template <std::size_t First, std::size_t... Rest, typename Array, typename T>
void setArrayValue (Array& array, const T& t) {
    setArrayValue<Rest...>(array[First], t);
}

template <typename Indices, typename Sequence> struct InitializeArray;

template <template <std::size_t...> class P, std::size_t... Is, std::size_t... Js>
struct InitializeArray<P<Is...>, std::index_sequence<Js...>> {
    template <typename Array, typename T>
    static void execute (Array& array, const T& t) {
        constexpr std::size_t GroupSize = sizeof...(Js),  NumGroups = sizeof...(Is) / GroupSize;
        set<GroupSize>(array, t, std::make_index_sequence<NumGroups>{});
    }
private:
    template <std::size_t GroupSize, typename Array, typename T, std::size_t... Ks>
    static void set (Array& array, const T& t, std::index_sequence<Ks...>) {
        const int dummy[] = {(do_set<Ks, GroupSize>(array, t), 0)...};
        static_cast<void>(dummy);
    }
    template <std::size_t N, std::size_t GroupSize, typename Array, typename T>
    static void do_set (Array& array, const T& t) {
        constexpr std::size_t a[] = {Is...};
        setArrayValue<a[N*GroupSize + Js]...>(array, t);
    }
};

template <typename T, typename Dimensions, typename... Indices, typename... Args>
auto makeNDimensionalArray (const Args&... args) {
    using A = NArrayFromPack<T, Dimensions>;
    typename A::type array;
    const int a[] = {(InitializeArray<Indices, std::make_index_sequence<A::num_dimensions>>::execute(array, args), 0)...};
    static_cast<void>(a);
    return array;
}

template <std::size_t...> struct I;

int main() {
    const NDimensionalArray<char, 3,6,5,4> a = makeNDimensionalArray<char, I<3,6,5,4>, I<2,4,3,2, 0,1,2,3, 1,2,4,3>, I<0,0,0,0, 2,3,1,2>, I<1,1,2,1>>('a','b','c');
    std::cout << a[2][4][3][2] << std::endl;  // a
    std::cout << a[0][1][2][3] << std::endl;  // a
    std::cout << a[1][2][4][3] << std::endl;  // a
    std::cout << a[0][0][0][0] << std::endl;  // b
    std::cout << a[2][3][1][2] << std::endl;  // b
    std::cout << a[1][1][2][1] << std::endl;  // c
}

N-dimensional std::array initialized with templates

4 Answers4