CODEWITHSUNDEEP
c++vector
bcf
bcf

Reputation: 2134

2d std::vector Contiguous Memory?

Consider the following code, which allocates a 2d std::vector<std::vector<int> > of size 5 x 3 and prints the memory addresses of each element:

#include <iostream>
#include <vector>

int main() {
  int n = 5, m = 3;
  std::vector<std::vector<int> >vec (n, std::vector<int>(m));

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      std::cout << &(vec[i][j]) << " ";
    }
    std::cout << "\n";
  }
}

Output:

0x71ecc0 0x71ecc4 0x71ecc8 
0x71ece0 0x71ece4 0x71ece8 
0x71ed00 0x71ed04 0x71ed08 
0x71ed20 0x71ed24 0x71ed28 
0x71ed40 0x71ed44 0x71ed48

Of course, for a fixed row, each column is contiguous in memory, but the rows are not. In particular, each row is 32 bytes past the start of the previous row, but since each row is only 12 bytes, this leaves a gap of 20 bytes. For example, since I thought vectors allocate contiguous memory, I would have expected the first address of the second row to be 0x71eccc. Why is this not the case, and how does vector decide how much of a gap to give?

Upvotes: 2

Views: 1768

Answers (2)

user4581301
user4581301

Reputation: 33931

Agree with Mr. Fox's results and solutions1. Disagree with the logic used to get there.

In order to be resizable, a std::vector contains a dynamically allocated block of contiguous memory, so the outer vector has a pointer to a block of storage that contains N vectors that are contiguous. However, each of these inner vectors contains a pointer to its own block of storage. The likelihood (without some really groovy custom allocator voodoo) of all N blocks of storage being contiguous is astonishingly small. The overhead of the N vectors is contiguous. The data almost certainly not, but could be.

1 Mostly. The std::arrays in a std::vector will be contiguous, but nothing prevents the implementor of std::array from putting in additional state information that prevents the arrays in the std::arrays from being contiguous. An implementor who wrote the std::array in such a way is an occupant of an odd headspace or solving a very interesting problem.

Upvotes: 2

Fantastic Mr Fox
Fantastic Mr Fox

Reputation: 33864

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:

enter image description here

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.

Upvotes: 2

Related Questions