How do vectors of vectors work?

Question

The answer here says:

From n2798 (draft of C++0x): 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().

This program works:

#include <iostream>
#include <vector>
#include <iterator>
using namespace std;

int main(){
  int k;
  cin >> k; cout << endl << "k = " << k << endl;
  ostream_iterator<int> oi(cout, " ");
  vector<vector<int> > vpi;
  while(k--)
  {
    vpi.push_back(vector<int>(istream_iterator<int>(cin), istream_iterator<int>()));
    cin.clear();
    cout<<"k = "<< k <<endl;
    copy(vpi[vpi.size()-1].begin(), vpi[vpi.size()-1].end(), oi);
    cout<<endl;
  }
}

How can a vector store vectors contiguously, when the elements of a vector must have equal size and the size of vectors to be stored is not known in advance?

I apologize if this has been asked before, I could not find it, if this is the case just drop me a link, please.

Answer 1

A std::vector is a small, fixed-size object. The usual implementation involves three pointers or one pointer and a couple of integer sizes (for current size and allocated capacity). The contents of the vector are not stored in the vector object itself, but in memory allocated using the vector's allocator (which defaults to the standard heap allocator).

So a vector of vectors is a small object, typically the size of three pointers. The vectors that are inside of it are small objects in contiguous memory somewhere in the heap. And the contents of those inner vectors are somewhere else in the heap.

Answer 2

Vectors can easily be stored continuously, since their elements are not within themselves but in some memory from the free store. The size of an object as specified by sizeof is compile-time constant expression, and those are the bits that are stored continuously.