Computing the linear index of a multi-dimensional array when using the curiously recurring template-CodePudding

I am writing a multi-dimensional array class in C and would like to have static and dynamic memory versions of it. Based on an answer from one of my previous posts, I used CRTP to define a base class which then has access to the respective data containers (std::array and std::vector) with contiguous memory in the derived classes.

I wish to implement the multi-dimensional subscript operator (e.g. to access the (1, 2) entry of a 4x3 matrix whose 12 entries are stored contiguously in memory) in the base class itself so as to avoid code duplication. Note that I just picked the subscript operator as it is the simplest class method that illustrates what I wish to achieve. I have attempted to adapt the multi-dimensional subscript linearisation solution given here by @Jarod42 to my case with CRTP. However, I am unsure about how to store the array dimensions in the derived classes in order to infer them in the base class when computing the linearised index. I hope the following code demonstrates my issue clearly (I am compiling with C 20):

#include <array>
#include <cassert>
#include <vector>

/** Multi-dimensional Array Base Class with CRTP. */
template <class derived, class T>
class MultiDimArray
{
private:
  constexpr derived& Derived() noexcept { return static_cast<derived&>(*this); }

  constexpr const derived& Derived() const noexcept { return static_cast<const derived&>(*this); }

protected:
  constexpr MultiDimArray() {}

public:
  // I've butchered the syntax in the following subscript operators, but I hope it captures what I intend to do.
  constexpr const T& operator()(HookTypeToPack<Derived().Dimensions, std::size_t> ...Is) const {
    return *(this->Derived()[ComputeIndex<Derived().Dimensions...>(Is...)]);
  }

  constexpr T& operator()(HookTypeToPack<Derived().Dimensions, std::size_t> ...Is) {
    return *(this->Derived()[ComputeIndex<Derived().Dimensions...>(Is...)]);
  }
};

/** Static Multi-dimensional Array Class */
template <class T, std::size_t ...Dims>
class StaticMultiDimArray : public std::array<T, (Dims * ...)>,
                            public MultiDimArray<StaticMultiDimArray<T, (Dims * ...)>, T>
{
private:
  constexpr static std::size_t nEntries = (Dims * ...);
  constexpr static std::tuple<HookTypeToPack<Dims, std::size_t>...> Dimensions = std::make_tuple(Dims...);
  friend MultiDimArray<StaticMultiDimArray<T, (Dims * ...)>, T>;

public:
  constexpr StaticMultiDimArray() : std::array<T, nEntries>(InitStaticArray<T, nEntries>(0.0)) {}
};

/** Dynamic Multi-dimensional Array Class */
template <class T>
class DynamicMultiDimArray : public std::vector<T>, public MultiDimArray<DynamicMultiDimArray<T>, T>
{
private:
  std::size_t nEntries;
  std::tuple<...> Dimensions; // Not sure what to use here considering a tuple is immutable
  friend MultiDimArray<DynamicMultiDimArray<T>, T>;

public:
  DynamicMultiDimArray() : std::vector<T>() {}

  template <typename ...Dims>
  DynamicMultiDimArray(Dims ...dimensions) : std::vector<T>((dimensions * ...), 0.0) { Resize(dimensions...); }

  template <typename ...Dims>
  void Resize(Dims ...dimensions)
  {
    nEntries = (dimensions * ...);
    this->resize(nEntries);
    // store dimensions in Dimensions...
  }
};

The support functions InitStaticArray, HookTypeToPack, and ComputeIndex used above are defined as follows:

template <class T, std::size_t size>
constexpr auto InitStaticArray(const T& value)
{
  std::array<T, size> arr;
  std::fill(arr.begin(), arr.end(), value);
  return arr;
}

template <std::size_t, typename T>
using HookTypeToPack = T;

template <std::size_t ...Dims>
constexpr std::size_t ComputeIndex(HookTypeToPack<Dims, std::size_t> ...multi_index)
{
  constexpr std::size_t dims_arr[] = {Dims...};
  std::size_t multi_index_arr[] = {multi_index...};

  std::size_t index(0), factor(1);
  for(int i = 0; i < sizeof...(Dims); i  )
  {
    assert(0 <= multi_index_arr[i] && multi_index_arr[i] < dims_arr[i]);
    index  = factor * multi_index_arr[i];
    factor *= dims_arr[i];
  }

  assert(0 <= index && index < (Dims * ...));
  return index;
}

Can anyone give me some advice on how to store the array dimensions in StaticMultiDimArray and DynamicMultiDimArray so they can be appropriately invoked in the operator() overloads in MultiDimArray?

CodePudding user response：

There are several options. One you are already hinting at: store the dimensions in the derived class. However, don't use a std::tuple; that allows every element to have a different type, while we just want the size of every dimension to be a std::size_t. Use a std::array for the static array, std::vector for the dynamic one:

template <class T, std::size_t ...Dims>
class StaticMultiDimArray :
    public std::array<T, ...>,
    public MultiDimArray<...>
{
  constexpr static std::array dimensions{Dims...};
  ...
};

template <class T>
class DynamicMultiDimArray :
    public std::vector<T>,
    public MultiDimArray<...>
{
  std::vector<std::size_t> dimensions;
  ...
};

You also don't need to make the constructor of DynamicMultiDimArray a template, instead you can have it take a std:initializer_list as an argument, like so:

DynamicMultiDimArray(std::initializer_list<std::size_t> dimensions) :
    std::vector<T>(std::accumulate(dimensions.begin(), dimensions.end(), std::size_t{1}, std::multiplies<std::size_t>())),
    Dimensions(dimensions) {}

Yeah, the initialization of the actual vector of elements looks very ugly now. I would recommend not using inheritance for this, but composition. Then you can initialize the dimensions first, then the array/vector of data, and can make a member variable in MultiDimArray that calculates the number of entries:

template <class derived, class T>
class MultiDimArray {
  ...
  constexpr std::size_t nEntries() const {
    const auto &dimensions = Derived().dimensions;
    return std::accumulate(dimensions.begin(), dimensions.end(), std::size_t{1}, std::multiplies<std::size_t>());
  }
  ...
};

template <class T>
class DynamicMultiDimArray :
    public MultiDimArray<...>
{
  std::vector<std::size_t> dimensions;
  std::vector<T> data;
  ...
public:
  DynamicMultiDimArray(std::initializer_list<std::size_t> dimensions) :
      Dimensions(dimensions),
      data(nEntries()) {}
};

Similarly, you can make operator() take a std::initializer_list<std::size_t> for the indices. Code using this looks like so:

DynamicMultiDimArray dimarr({3, 5, 7}); // create new array
...
std::cout << dimarr({1, 2, 3}) << '\n'; // print element at index 1, 2, 3

This avoids a lot of template hassle. You could even consider creating a custom multi-dimensional index type instead of a std::initializer_list<std::size_t>, making it easier to store indices in a variable and pass them around.