C++11 dynamic multidimensional array of any type u

Question

How do you create a multidimensional array (matrix) whose dimensions are determined at runtime.

The best way seems to be to take a vector of dimensions for construction and also a vector of offsets to access individual elements

This will also allow using initializer lists:

This should take a matrix of types determined at compile time, so templates make sense

C++11 features should be used as appropriate, bonus points for lambdas

Example usage:

int main(int, char **)
{
        static const std::size_t d1{2};
        static const std::size_t d2{3};
        static const std::size_t d3{4};
        multi_vec<std::size_t> q({d1,d2,d3});

        for (std::size_t i1=0; i1 < d1; ++i1)
                for (std::size_t i2=0; i2 < d2; ++i2)
                        for (std::size_t i3=0; i3 < d3; ++i3)
                                q[{i1,i2,i3}]=foo(i1,i2,i3);

        for (std::size_t i1=0; i1 < d1; ++i1)
                for (std::size_t i2=0; i2 < d2; ++i2)
                        for (std::size_t i3=0; i3 < d3; ++i3)
                                std::cout << "{"
                                        << i1 << ","
                                        << i2 << ","
                                        << i3 << "}=> "
                                        << foo(i1,i2,i3) << "=="
                                        << q[{i1,i2,i3}]
                                        << ((foo(i1,i2,i3) == q[{i1,i2,i3}])
                                              ? " good" : " ERROR")
                                << std::endl;
};

Answer 1

You use C. Honestly, C's dynamic arrays are superior to anything C++ offers. Here is the code for a 3D array:

//Allocation, the type needs some effort to understand,
//but once you do understand it, this is easy:
int width = 7, height = 8, depth = 9;
int (*array)[height][width] = malloc(depth*sizeof(*array));

//Filling, completely natural...
for(int z = 0; z < depth; z++) {
    for(int y = 0; y < height; y++) {
        for(int x = 0; x < width; x++) {
            array[z][y][x] = 42;
        }
    }
}

//Deallocation, trivial...
free(array);

A 3D array is nothing more or less than a 1D array of 2D arrays (which are 1D arrays of 1D arrays in turn), so you declare a pointer *array to a 2D array of integers int (...)[heigh][width], and allocate space for depth such elements malloc(depth*sizeof(*array)). This is fully analogous to creating a 1D array with int *array = malloc(length*sizeof(*array));. The rest is array-pointer-decay magic.

This works is C, because C allows array types to contain dynamic sizes (since C99). It's like defining two constants with the declared sizes at the point of the declaration. C++, on the other hand, still insists on array sizes being compile-time constants, and thus fails to allow you multi-dimensional arrays of dynamic size.

Answer 2

As answered here https://stackoverflow.com/a/19725907/2684539 :

#include <cstddef>

#include <vector>

template<typename T>
class MultiArray
{
public:
    explicit MultiArray(const std::vector<size_t>& dimensions) :
        dimensions(dimensions),
        values(computeTotalSize(dimensions))
    {
        assert(!dimensions.empty());
        assert(!values.empty());
    }

    const T& get(const std::vector<size_t>& indexes) const
    {
        return values[computeIndex(indexes)];
    }
    T& get(const std::vector<size_t>& indexes)
    {
        return values[computeIndex(indexes)];
    }

    size_t computeIndex(const std::vector<size_t>& indexes) const
    {
        assert(indexes.size() == dimensions.size());

        size_t index = 0;
        size_t mul = 1;

        for (size_t i = 0; i != dimensions.size(); ++i) {
            assert(indexes[i] < dimensions[i]);
            index += indexes[i] * mul;
            mul *= dimensions[i];
        }
        assert(index < values.size());
        return index;
    }

    std::vector<size_t> computeIndexes(size_t index) const
    {
        assert(index < values.size());

        std::vector<size_t> res(dimensions.size());

        size_t mul = values.size();
        for (size_t i = dimensions.size(); i != 0; --i) {
            mul /= dimensions[i - 1];
            res[i - 1] = index / mul;
            assert(res[i - 1] < dimensions[i - 1]);
            index -= res[i - 1] * mul;
        }
        return res;
    }

private:
    size_t computeTotalSize(const std::vector<size_t>& dimensions) const
    {
        size_t totalSize = 1;

        for (auto i : dimensions) {
            totalSize *= i;
        }
        return totalSize;
    }

private:
    std::vector<size_t> dimensions;
    std::vector<T> values;
};

int main()
{
    MultiArray<int> m({3, 2, 4});

    m.get({0, 0, 3}) = 42;
    m.get({2, 1, 3}) = 42;

    for (size_t i = 0; i != 24; ++i) {
        assert(m.computeIndex(m.computeIndexes(i)) == i);
    }
    return 0;
}

Answer 3

This is actually a good place to use lambdas with std::for_each and unique_ptr for memory management:

template <class T>
class multi_vec
{
public:
    using param=std::vector<size_t>;

    explicit multi_vec(const param& dimensions)
        : dim{dimensions}, prod {1}
    {
        std::for_each(dim.begin(), dim.end(), [this] (std::size_t val)
        {
            mult.emplace_back(prod);
            prod *= val;
        } );
        ptr.reset(new T[prod]);
    }
    std::size_t capacity() const { return prod; }

    // undefined if elements in lookup != elemenets in dim
    // undefined if any element in lookup
        // is greater than or equal to corresponding dim element
    T& operator[](const param& lookup)
    {
        return ptr[get_offset(lookup)];
    }
    const T operator[](const param& lookup) const
    {
        return ptr[get_offset(lookup)];
    }
private:
    std::size_t get_offset(const param& lookup) const
    {
        std::size_t offset=0;
        auto mit=mult.begin();
        std::for_each(lookup.begin(), lookup.end(), [&offset, &mit] (std::size_t val)
        {
            offset+=*mit * val;
           ++mit;
        } );
        return offset;
    }
    param dim;
    param mult;
    std::size_t prod;
    std::unique_ptr<T[]> ptr;
};

This uses a single dimensional array for actual storage and caches multipliers for reuse Since a normal multidimension array e.g. x[2][3][4] does not bounds check, going out of bounds is deemed undefined instead of constantly checking values that are probably valid. In the same way diminsionality is not checked for lookups, if required, a static member can be added to check if a parameter is valid, in terms of bounds or dimensionality.