CODEWITHSUNDEEP
c++arraysvariadic-templates
William Moy
William Moy

Reputation: 33

Using variadic templates to create a 2D array with variable column width?

Is it possible to create a "sparse" variable-length 2D array using only variadic templates and std::array? By sparse, I mean that each row could have a variable amount of columns.

Ideally, I'd like to instantiate something like VariableLengthTable<int,2,4,3>() and have it create an array of arrays that would map to something like {{0,1}, {0,1,2,3}, {0,1,2}}. I've seen SO posts that deal with variadic templates to create multidimensional arrays, but they are all symmetrical.

Note that I'm limited to zero-cost abstractions (e.g. std::array) as I'm working with a very memory constricted application.

Upvotes: 2

Views: 224

Answers (1)

Angew is no longer proud of SO
Angew is no longer proud of SO

Reputation: 171127

Yes, this should be possible in principle. Here's a bit to get you started:

template <class T, std::size_t... Dim>
using VariableLengthTable = std::tuple<std::array<T, Dim>...>;

This is a tuple of std::arrays, each with a length specified by one of the template arguments.

Note that because the length of a std::array is part of its type, the first dimension cannot be an array, since its members would need different types. However, std::tuple works nicely. As long as you're willing to use std::get<i> instead of [i], and restrict yourself to compile-time is, you should be good.

If a compile-time i is not enough, you have two options:

One, use VariableLengthTable as above and add a runtime-to-compiletime conversion. Conceptually, something like this switch:

T& get(std::size_t x, std::size_t y)
{
  switch (x) {
    case 0: return std::get<0>(varLenTable)[y];
    case 1: return std::get<1>(varLenTable)[y];
    case 2: return std::get<2>(varLenTable)[y];
    // and so on
  }
}

In reality, you'd probably need to compose this using recursion or inheritance to avoid a compile-time out-of-bounds access. Boost.Preprocessor might help with that.

Two, store all the data in one sequential buffer and index into it at runtime. Something like this:

template <class T, std::size_t... Dim>
class VariableLengthTable
{
  static const std::array<std::size_t, sizeof...(Dim)> dims = {{ Dim... }};

  static const std::array<std::size_t, sizeof...(Dim)> cumulDims = [](){
    std::array<std::size_t, sizeof...(Dim)> result;
    result[0] = 0;
    for (std::size_t idx = 1; idx < sizeof...(Dim); ++idx) {
      result[idx] = result[idx - 1] + dims[idx];
    }
    return result;
  }();

  std::array<T, cumulDims[sizeof...(Dim) - 1] + dims[sizeof...(Dim) - 1]> data;

public:
  T& get(std::size_t x, std::size_t y)
  {
    return data[cumulDims[x] + y];
  }
};

The code above is to show the principle, not guaranteed to compile as-is.

Upvotes: 3

Related Questions