C++11 dynamic multidimensional array of any type using vector/initilizer list

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;
};

Glenn Teitelbaum · Accepted Answer · 2013-12-31 17:19:10Z

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.

edited Dec 31, 2013 at 17:19

answered Dec 30, 2013 at 20:06

Glenn Teitelbaum

10.4k4 gold badges42 silver badges82 bronze badges

Sign up to request clarification or add additional context in comments.

11 Comments

Kerrek SB Over a year ago

If you're already going to store the size, why not use a std::vector<T>?

Glenn Teitelbaum Over a year ago

@KerrekSB How would that be an improvement over a size_t and std::unique_ptr<T[]>?

Kerrek SB Over a year ago

Unrelatedly: If I were to write this, I'd make it constructible from an initializer list of extents, and subscriptable with an initializer list of indexes...

Kerrek SB Over a year ago

Like multi_vec x({2, 5, 3}); x[{1,1,1}] = 10; etc.

Glenn Teitelbaum Over a year ago

@KerrekSB That will work as is - see the question for examples -- I didn't think that multi_vec<std::size_t> tt={3,4,5}; was clear (it looks like initial values), so I just left inializer list to vector take care of your examples

|

Community · Accepted Answer · 2017-05-23 12:16:33Z

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;
}

cmaster - reinstate monica · Accepted Answer · 2017-09-25 16:11:15Z

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.

Collectives™ on Stack Overflow

C++11 dynamic multidimensional array of any type using vector/initilizer list

3 Answers 3

11 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

11 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related