34

Suppose I want to represent a two-dimensional matrix of int as a vector of vectors:

std::vector<std::vector<int> > myVec;

The inner dimension is constant, say 5, and the outer dimension is less than or equal to N. To minimize reallocations I would like to reserve space:

myVec.reserve(N);

What size is assumed for the inner vector? Is this purely implementation dependent? How does this effect the spatial locality of the data? Since the inner dimension is a constant is there a way to tell the compiler to use this constant size? How do these answers change if the inner vector's size changes?

OSE
  • 986
  • 2
  • 13
  • 19
  • 2
    vector of vectors is not a particularly good way to represent a rectangular matrix. It's more useful for jagged arrays, where each row has a different number of columns. – Ben Voigt Sep 24 '13 at 21:18

3 Answers3

21

Since your inner dimension is constant, I think you want

std::vector< std::array<int, 5> > vecs;
vecs.reserve(N);

This will give you preallocated contiguous storage, which is optimal for performance.

Ben Voigt
  • 277,958
  • 43
  • 419
  • 720
  • 2
    @Samer: That's nonsense, `array` doesn't require any C++11 features and is available as `std::tr1::array` since 2007, and `boost::array` even before that. – Ben Voigt Sep 25 '13 at 14:26
14

The size of the inner vectors is completely irrelevant for resizing the outer vector. There are no locality guarantees for your bundle of vectors, the locality guarantee (i.e. contiguous block in memory) exists for a single vector only.

Remember that a vector object itself has constant sizeof-size, its actual data is usually dynamically allocated. The outer vector, to first approximation, is a contiguous block of N 'pointers' to the inner vectors. Your reserve call does not reserve memory for possible elements of inner vectors, but only for the inner vector objects themselves (i.e. their bookkeeping data and their pointers to their dynamically allocated data block).

us2012
  • 16,083
  • 3
  • 46
  • 62
14

The inner vectors are initialized with the default constructor. So if you write:

vector<vector<int> > vecs;
vecs.reserve(10);

This is equivalent to calling the constuctor of vector<int> or vector<int>() for each element. Which means you'll have a zero-sized vectors. But remember, you can't use them unless you resize (not reserve) your vectors.

Remember, too, that it could be sometimes more efficient to resize with the initial size that you would need. So it's useful to do something like

vector<vector<int> > vecs(3,vector<int>(5));

This will create a vector with size 3, and each element will contain a vector of size 5.

Remember also, that it could be more efficient to use deque rather than vector if you're going to resize your vectors often. They're easy to use (as vectors) and you don't need to reserve, since the elements are not contiguous in memory.

The Quantum Physicist
  • 24,987
  • 19
  • 103
  • 189
  • 1
    A two-dimensional matrix is likely used for random-access, which a `deque` can't do efficiently. – Ben Voigt Sep 25 '13 at 14:26
  • 4
    `reserve()` does not call the default constructor! Therefore does not initialise. It only allocates the memory. – anilbey Aug 24 '19 at 19:25
  • Can I ask why the syntax is not intuitive for the size of 'inner' vectors? vector > vecs(3,5); Isn't this more intuitive? When I tried, it failed though. – ZoomIn Oct 14 '21 at 16:15
  • 2
    @ZoomIn "Intuitive" is subjective. I'm OK with this form, because I understand how the constructor of `std::vector` works. You're constructing a vector of 3 elements, each element has `vector(5)` as initial value. To me this makes sense. If we were to accept your way of doing it, it would mean that initializing a vector with an integer would be OK, which will cause all kinds of problems and introduce type-safety issues. Imagine accepting `std::vector v = 5`... what does that even mean?! It's all kinds of confusing. – The Quantum Physicist Oct 15 '21 at 06:10