Efficient method to initialize a really large C++ vector with the same values

Question

I was doing this leetcode problem and I had to initialize a very large 2D DP array of size 2^14 x 14 with all entries set to -1 to solve the problem. However I noticed a big performance difference depending on whether I'm using vector or array for this DP array.

Using vector:

vector<vector<int>> dp(1 << nums.size(), vector<int>(nums.size(), -1));

gave me a runtime of 251 ms

Meanwhile, using array with memset:

int dp[1 << 14][14];
memset(dp, -1, sizeof(dp));

only gave me a runtime of 95 ms

Is there a way to initialize this array as efficiently using C++ vector?

I have tried alternatives such as using std:fill, but it doesn't produce any runtime difference.

• NathanOliver: dont use 2d vectors, instead write a class that holds a 1d vector and pretend that it is 2d using maths
• user4581301: Simple example of above: stackoverflow.com/a/36123944/4581301 Rational: One vector is contiguous and cache-friendly. A vector of vectors is exactly that: One vector that holds a bunch of other vectors all with their own block of memory that might not be anywhere near the others.
• sweenish: It's worth considering if this is actually the expected solution to the problem.
• N_ E: It's not needed in this case, but it did make me wonder if it's possible to do the thing I asked in case I'm faced with a problem that needs it
• NathanOliver: @SheltonLiu Its a performance issue. A 2d vector, unlike a 2d array, does not guarantee that all the rows will be in one contiguous piece of memory. Each row itself is guaranteed to be contiguous, but row 1 could be in a completely different place in memory than row 2, and so on. This means every time you change rows you there's a good chance you'll get a cache miss

Answer 1

Using something like this:

template <class T>
class matrix2d {
 std::vector<T> data;
 std::size_t cols;
 std::size_t rows;
public:
 matrix2d(std::size_t y, std::size_t x, T init = T()) : cols(x), rows(y), data(x*y, init) {}
 T &operator()(std::size_t y, std::size_t x) { 
 assert(x<=cols);
 assert(y<=rows);
 return data[y*cols+x];
 }
 T operator()(std::size_t y, std::size_t x) const {
 assert(x<=cols);
 assert(y<=rows);
 return data[y*cols+x];
 }
 friend std::ostream &operator<<(std::ostream &os, matrix2d const &m) {
 for (std::size_t y=0; y<m.rows; y++) {
 for (std::size_t x = 0; x<m.cols; x++) {
 os << m(y,x) << "\t";
 }
 os << "\n";
 }
 return os;
 }
};
int main() { 
 using namespace std::chrono;
 
 auto start = steady_clock::now();
 matrix2d m(1<<14, 14, -1);
 auto stop = steady_clock::now();
 uint64_t total = 0;
 for (int i=0; i<(1<<14); i++) {
 for (int j=0; j<14; j++) {
 total+=m(i,j);
 }
 }
 std::cout << "Total: " << total << "\n";
 std::cout << duration_cast<microseconds>(stop-start).count() << "us\n";
 auto start2 = steady_clock::now(); 
 int dp[1 << 14][14];
 memset(dp, -1, sizeof(dp));
 auto stop2 = steady_clock::now();
 std::cout << duration_cast<microseconds>(stop2-start2).count() << "us\n";
}

I get about the same amount of time to initialize one as the other (but both are in the range of hundreds of microseconds, not anything like multiple milliseconds.