Std::Vector and Contiguous Memory of Multidimensional Arrays

std::vector and contiguous memory of multidimensional arrays

For reference the way I currently create a 2D array in a contiguous memory block is by first making a (dynamic) array of float* of length N, allocating all N*5 floats in one array and then copying the address of every 5th element into the first array of float*.

That's not a 2D array, that's an array of pointers. If you want a real 2D array, this is how it's done:

float (*p)[5] = new float[N][5];

p [0] [0] = 42;   // access first element
p[N-1][4] = 42;   // access last element

delete[] p;

Note there is only a single allocation. May I suggest reading more about using arrays in C++?

2d std::vector Contiguous Memory?

The overhead size of a vector is not 0. You have 24 bytes between the last element of your vector and the first element of the next vector. Try this:

cout << sizeof(std::vector<int>) << endl;

You will find the output to be 24 (Likely for your implementation of std::vector and compiler etc). Live example which happens to match.

You can imagine the vector layout like this:

If you want your elements to actually be contiguous then you need to do:

1. Use a std::array<std::array<int>> for no overhead (c++11 only). Note that this cannot be resized.
2. Use std::vector<int> and the formula row * numRows + col to access the element for row, col.

Is a vector of arrays contiguous?

Is a vector of arrays contiguous?

No, it is not. std::array may contain padding or even additional members at the end. More details, e.g., here:

• Is the data in nested std::arrays guaranteed to be contiguous?
• Is the size of std::array defined by standard

---

But I believe this is very unlikely to happen and you can simply check such situations by comparing 2 * sizeof(double) with sizeof(std::array<double, 2>).

What is the memory layout of vector of arrays?

Arrays do not have any indirection, but just store their data "directly". That is, a std::array<int, 5> literally contains five ints in a row, flat. And, like vectors, they do not put padding between their elements, so they're "internally contiguous".

However, the std::array object itself may be larger than the set of its elements! It is permitted to have trailing "stuff" like padding. So, although likely, it is not necessarily true that your data will all be contiguous in the first case.

An int
+----+
|    |
+----+

A vector of 2 x int
+----+----+----+-----+        +----+----+
| housekeeping | ptr |        | 1  |  2 |
+----+----+----+-----+        +----+----+
                   |          ^
                   \-----------

An std::array<int, 5>
+----+----+----+----+----+----------->
| 1  |  2 |  3 |  4 |  5 | possible cruft/padding....
+----+----+----+----+----+----------->

A vector of 2 x std::array<int, 5>
+----+----+----+-----+        +----+----+----+----+----+----------------------------+----+----+----+----+----+----------->
| housekeeping | ptr |        | 1  |  2 |  3 |  4 |  5 | possible cruft/padding.... | 1  |  2 |  3 |  4 |  5 | possible cruft/padding....
+----+----+----+-----+        +----+----+----+----+----+----------------------------+----+----+----+----+----+----------->
                   |          ^
                   \-----------

And, even if it were, due to aliasing rules, whether you'd be able to use a single int* to navigate all 10 numbers would potentially be a different matter!

All in all, a vector of ten ints would be clearer, completely packed, and possibly safer to use.

In the case of a vector of vectors, a vector is really just a pointer plus some housekeeping, hence the indirection (as you say).

c++ std multidimensional array memory layout

int simple_2D_array[M][N];

This is guaranteed to be contiguous in memory. You can use pointer arithmetic to calculate the position of any index relative to the start.

std::array<std::array<int,N>,M> std_2D_array;

This, in general, does not have to be contiguous in memory. It is an array of objects, each of which happens to be an array. While each of the internal arrays is logically equivalent to a C-style array as its only non-static data member, it is permissible for the compiler to decide that the entire internal array requires padding.

So, in practice, it is probably contiguous, but it probably doesn't pay to rely on that. Just write an iterator or something.

C++ Properly deallocate multidimensional array with underlying contiguous memory

Should actually be like this:

void delete_3d(double *** array, const int& sz, const int& sy, const int& sx) {
    // first, restore the pointer to the actual aMem
    double * aMem = array[0][0];
    // only one dimension was allocated in the loop,
    // so only one loop should be deallocating things
    for(int k = 0; k < sz; k++) {
        delete [] array[k];
    }
    delete[] array;
    delete[] aMem;
}

---

A way-better solution

Wrap std::vector to get both: contiguous memory and a reasonably simple access syntax and as a bonus no additional arrays which is better for memory, performance and maintenance:

class Array3d {
public:
    Array3d(size_t sx, size_t sy, size_t sz)
        : m_sx(sx), m_sy(sy) {
        m_array.resize(sx * sy * sz);
    }

    // Can't overload operator[] with more that one parameter
    // so we'll have to do with operator()
    double &operator()(size_t x, size_t y, size_t z) {
        size_t index = x * m_sx * m_sy + y * m_sy + z;
        return m_array[index];
    }

private:
    size_t m_sx, m_sy;
    std::vector<double> m_array;
};

Usage example:

Array3d array(3, 3, 3);
array(0, 1, 2) = 3.14;

Does std::array of std::array have contiguous memory?

According to the standard the memory should be contiguous. The 26.3.7.1 [array.overview] paragraph states (emphasis mine):

The header defines a class template for storing fixed-size
sequences of objects. An array is a contiguous container. An instance
of array stores N elements of type T, so that size() == N is an
invariant.

Update: It appears the implementation might include the padding.
More info on the subject in these SO posts:

Is the size of std::array defined by standard?

and specifically this answer:

Is the data in nested std::arrays guaranteed to be contiguous?

Would vector of vectors be contiguous?

In short, no. This is what actually happens:

---

Related Topics