std::vector and contiguous memory of multidimensional arrays

Question

I know that the standard does not force std::vector to allocate contiguous memory blocks, but all implementations obey this nevertheless.

Suppose I wish to create a vector of a multidimensional, static array. Consider 2 dimensions for simplicity, and a vector of length N. That is I wish to create a vector with N elements of, say, int[5].

Can I be certain that all N*5 integers are now contiguous in memory? So that I in principle could access all of the integers simply by knowing the address of the first element? Is this implementation dependent?

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*.

Answer 1

The standard does require the memory of an std::vector to be contiguous. On the other hand, if you write something like:

std::vector<std::vector<double> > v;

the global memory (all of the v[i][j]) will not be contiguous. The usual way of creating 2D arrays is to use a single

std::vector<double> v;

and calculate the indexes, exactly as you suggest doing with float. (You can also create a second std::vector<float*> with the addresses if you want. I've always just recalculated the indexes, however.)

Answer 2

Elements of a Vector are gauranteed to be contiguous as per C++ standard.
Quotes from the standard are as follows:

From n2798 (draft of C++0x):

23.2.6 Class template vector [vector]

1 A vector is a sequence container that supports random access iterators. In addition, it supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time. Storage management is handled automatically, though hints can be given to improve efficiency. The elements of a vector are stored contiguously, meaning that if v is a vector where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().

C++03 standard (23.2.4.1):

The elements of a vector are stored contiguously, meaning that if v is a vector where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().

Also, see here what Herb Sutter's views on the same.

Answer 3

As @Als already pointed out, yes, std::vector (now) guarantees contiguous allocation. I would not, however, simulate a 2D matrix with an array of pointers. Instead, I'd recommend one of two approaches. The simpler by (by far) is to just use operator() for subscripting, and do a multiplication to convert the 2D input to a linear address in your vector:

template <class T>
class matrix2D { 
     std::vector<T> data;
     int columns;
public:
     T &operator()(int x, int y) {
         return data[y * columns + x];
     }

     matrix2D(int x, int y) : data(x*y), columns(x) {}
};

If, for whatever reason, you want to use matrix[a][b] style addressing, you can use a proxy class to handle the conversion. Though it was for a 3D matrix instead of 2D, I posted a demonstration of this technique in previous answer.

Answer 4

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++?

Answer 5

Under the hood, a vector may look approximately like (p-code):

class vector<T> {
    T      *data;
    size_t  s;
};

Now if you make a vector<vector<T> >, there will be a layout like this

vector<vector<T>> --> data {
    vector<T>,
    vector<T>,
    vector<T>
};

or in "inlined" form

vector<vector<T>> --> data {
    {data0, s0},
    {data1, s1},
    {data2, s2}
};

Yes, the vector-vector therefore uses contiguous memory, but no, not as you'd like it. It most probably stores an array of pointers (and some other variables) to external places.

The standard only requires that the data of a vector is contiguous, but not the vector as a whole.

Answer 6

A simple class to create, as you call it, a 2D array, would be something like:

template <class T> 2DArray {
private:
    T *m_data;
    int m_stride;
public:
    2DArray(int dimY, int dimX) : m_stride(dimX) : m_data(new[] T[dimX * dimY]) {}
    ~2DArray() { delete[] m_data; }
    T* operator[](int row) { return m_data + m_stride * row; }
}

It's possible to use this like:

2DArray<int> myArray(30,20);

for (int i = 0; i < 30; i++)
    for (int j = 0; j < 20; j++)
        myArray[i][j] = i + j;

Or even pass &myArray[0][0] as address to low-level functions that take some sort of "flat buffers".

But as you see, it turns naive expectations around in that it's myarray[y][x].

Generically, if you interface with code that requires some sort of classical C-style flat array, then why not just use that ?

Edit: As said, the above is simple. No bounds check attempts whatsoever. Just like, "an array".