C++ Multidimensional array in existing memory

Question

(This is not a duplicate of this or this that refer to fixed sizes, the issue is not to understand how pointers are stored, but if the compiler can automate the manual function).

Based on this SO question multidimensional arrays are stored sequentially.

// These arrays are the same
int array1[3][2] = {{0, 1}, {2, 3}, {4, 5}}; 
int array2[6] = { 0, 1, 2, 3, 4, 5 }; 

However I'm trying to create a 2 dimension array of floats in pre-allocated memory:

float a[5][10] 
float b[50]; // should be same memory

Then I'm trying:

vector<char> x(1000);
float** a = (float**)x.data();
a[0][1] = 5;

The above code crashes, obviously because the compiler does not know the size of the array to allocate it in memory like in the compiler-level known array in the first example.

Is there a way to tell the compiler to allocate a multi dimensional array in sequential memory without manually calculating the pointers (say, by manually shifting the index and calling placement new for example)?

Currently, I'm doing it manually, for example:

template <typename T> size_t CreateBuffersInMemory(char* p,int n,int BufferSize)
{
    // ib = T** to store the data
    int ty = sizeof(T);

    int ReqArraysBytes = n * sizeof(void*);
    int ReqT = ReqArraysBytes * (ty*BufferSize);
    if (!p)
        return ReqT;

    memset(p, 0, ReqT);
    ib = (T**)p;
    p += n * sizeof(void*);
    for (int i = 0; i < n; i++)
    {
        ib[i] = (T*)p;
        p += ty*BufferSize;
    }
    return ReqT;
}

Thanks a lot.

Answer 1

To allocate T[rows][cols] array as a one-dimensional array allocate T[rows * cols].

To access element [i][j] of that one-dimensional array you can do p[i * cols + j].

Example:

template<class T>
struct Array2d {
    T* elements_;
    unsigned columns_;

    Array2d(unsigned rows, unsigned columns)
        : elements_(new T[rows * columns]{}) // Allocate and value-initialize.
        , columns_(columns)
    {}

    T* operator[](unsigned row) {
        return elements_ + row * columns_;
    }

    // TODO: Implement the special member functions.
};

int main() {
    Array2d<int> a(5, 10);
    a[3][1] = 0;
}

Answer 2

Your code invokes undefined behavior because x.data() does not point to an array of pointers but to an array of 1000 objects of type char. You should be thankful that it crashes… ;-)

One way to access a contiguous buffer of some type as if it was a multidimensional array is to have another object that represents a multidimensional view into this buffer. This view object can then, e.g., provide member functions to access the data using a multidimensional index. To enable the a[i][j][k] kind of syntax (which you seem to be aiming for), provide an overloaded [] operator which returns a proxy object that itself offers an operator [] and so on until you get down to a single dimension.

For example, for the case that dimensions are fixed at compile time, we can define

template <int Extent, int... Extents>
struct row_major_layout;

template <int Extent>
struct row_major_layout<Extent>
{
    template <typename T>
    static auto view(T* data) { return data; }
};

template <int Extent, int... Extents>
struct row_major_layout
{
    static constexpr int stride = (Extents * ... * 1);

    template <typename T>
    class span
    {
        T* data;

    public:
        span(T* data) : data(data) {}

        auto operator[](std::size_t i) const
        {
            return row_major_layout<Extents...>::view(data + i * stride);
        }
    };

    template <typename T>
    static auto view(T* data) { return span<T>(data); }
};

and then simply create and access such a row_major_layout view

void test()
{
    constexpr int M = 7, N = 2, K = 5;

    std::vector<int> bla(row_major_layout<M, N, K>::size);

    auto a3d = row_major_layout<M, N, K>::view(data(bla));

    a3d[2][1][3] = 42;
}

live example here

Or in case the array bounds are dynamic:

template <int D>
class row_major_layout;

template <>
class row_major_layout<1>
{
public:
    row_major_layout(std::size_t extent) {}

    static constexpr std::size_t size(std::size_t extent)
    {
        return extent;
    }

    template <typename T>
    friend auto view(T* data, const row_major_layout&)
    {
        return data;
    }
};

template <int D>
class row_major_layout : row_major_layout<D - 1>
{
    std::size_t stride;

public:
    template <typename... Dim>
    row_major_layout(std::size_t extent, Dim&&... extents)
        : row_major_layout<D - 1>(std::forward<Dim>(extents)...), stride((extents * ... * 1))
    {
    }

    template <typename... Dim>
    static constexpr std::size_t size(std::size_t extent, Dim&&... extents)
    {
        return extent * row_major_layout<D - 1>::size(std::forward<Dim>(extents)...);
    }

    template <typename T>
    class span
    {
        T* data;
        std::size_t stride;
        const row_major_layout<D - 1>& layout;

    public:
        span(T* data, std::size_t stride, const row_major_layout<D - 1>& layout)
            : data(data), stride(stride), layout(layout)
        {
        }

        auto operator[](std::size_t i) const
        {
            return view(data + i * stride, layout);
        }
    };

    template <typename T>
    friend auto view(T* data, const row_major_layout& layout)
    {
        return span<T>(data, layout.stride, layout);
    }
};

and

void test(int M, int N, int K)
{
    std::vector<int> bla(row_major_layout<3>::size(M, N, K));

    auto a3d = view(data(bla), row_major_layout<3>(M, N, K));

    a3d[2][1][3] = 42;
}

live example here

Answer 3

Based on this answer assuming you want an array of char you can do something like

std::vector<char> x(1000);
char (&ar)[200][5] = *reinterpret_cast<char (*)[200][5]>(x.data());

Then you can use ar as a normal two-dimensional array, like

char c = ar[2][3];

Answer 4

For anyone trying to achieve the same, I 've created a variadit template function that would create a n-dimension array in existing memory:

template <typename T = char> size_t CreateArrayAtMemory(void*, size_t bs)
{
    return bs*sizeof(T);
}

template <typename T = char,typename ... Args>
size_t CreateArrayAtMemory(void* p, size_t bs, Args ... args)
{
    size_t R = 0;
    size_t PS = sizeof(void*);
    char* P = (char*)p;
    char* P0 = (char*)p;

    size_t BytesForAllPointers = bs*PS;
    R = BytesForAllPointers;

    char* pos = P0 + BytesForAllPointers;
    for (size_t i = 0; i < bs; i++)
    {
        char** pp = (char**)P;
        if (p)
            *pp = pos;
        size_t RLD = CreateArrayAtMemory<T>(p ? pos : nullptr, args ...);
        P += PS;
        R += RLD;
        pos += RLD;
    }
    return R;
}

Usage:

Create a 2x3x4 char array:

int j = 0;
size_t n3 = CreateArrayAtMemory<char>(nullptr,2,3,4);
std::vector<char> a3(n3);
char*** f3 = (char***)a3.data();
CreateArrayAtMemory<char>(f3,2,3,4);
for (int i1 = 0; i1 < 2; i1++)
{
    for (int i2 = 0; i2 < 3; i2++)
    {
        for (int i3 = 0; i3 < 4; i3++)
        {
            f3[i1][i2][i3] = j++;
        }
    }
}