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.

[This](http://stackoverflow.com/questions/13341264/vector-elements-do-not-appear-to-be-stored-contigously) question stems from a similar misconception. — Doru Georgescu, Dec 22 '12 at 20:17

score 3 · Accepted Answer · answered Dec 22 '12 at 17:59

3

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.

answered Dec 22 '12 at 17:59

Adrian McCarthy

45,555
16
123
175

There are no _dynamic-size objects_ in **C++**, are they? – K-ballo Dec 22 '12 at 18:00
@K-ballo Not really. Every object size is known at compile-time. However, objects can hold pointers to objects allocated at run-time in the heap, effectively being *kind-of-dynamic-size*, but still having a fixed `sizeof(T)`. – luiscubal Dec 22 '12 at 18:03
Right. Now please tell me how was I supposed to know that? _cplusplus.com_, _cppreference.com_, reading the code? How do you know this? Have you also asked on _stackoverflow.com_? :-) – Doru Georgescu Dec 22 '12 at 18:15
Stop tagging questions with `fixmybug` and `findmybug` as they are meta tags and not appropriate. Please refrain from doing so in the future or further moderator action may be taken. – casperOne Jan 02 '13 at 17:30

K-ballo · Answer 2 · 2012-12-22T17:57:34.907

0

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.

edited Dec 22 '12 at 17:57

answered Dec 22 '12 at 17:42

K-ballo

80,396
20
159
169

By "not within themselves" you probably mean that they are represented through pointers? – Doru Georgescu Dec 22 '12 at 17:49
1

@DoruGeorgescu: Yes, memory from the heap store, pointers, dynamic allocation. Otherwise, how would they work? – K-ballo Dec 22 '12 at 17:50
Otherwise they could not work, but where is this written? Objects are memorized directly, probably only containters are reprezented through pointers. Nothing about this on cplusplus.com. – Doru Georgescu Dec 22 '12 at 17:53
@DoruGeorgescu: _cplusplus.com_ is a reference to the **C++** language. The language dictates standard classes behavior, not their implementation. The behavior required by `vector` cannot be meet without using the free store... – K-ballo Dec 22 '12 at 17:57
Yes, but where on _cplusplus.com_ do you see that vectors of vectors are allowed? I really did not know. – Doru Georgescu Dec 22 '12 at 18:05
@DoruGeorgescu: Oh well, it just happens to be that http://www.cplusplus.com/reference/vector/vector/ explains both the dynamic nature of `vector`s and the requirements on their container type `T`. You missed the reference on vectors while researching for vectors? – K-ballo Dec 22 '12 at 18:08
Probably I should not learn from references. Do you have suggestions? – Doru Georgescu Dec 22 '12 at 18:36
What I missed was the fact that vectors are objects. I thought that they could be pointers to arrays or arrays. The fact that containers are objects is stated on the containers page, which indeed I only read diagonally. A few details, like those given by the chosen answer can only help memory. If you can answer to my last comment to the chosen answer, that would be great. Thank you. – Doru Georgescu Dec 22 '12 at 18:59

How do vectors of vectors work?

2 Answers2