How a vector grows

Lesson 28 of 30 · Part 7 · Going further · about 15 minutes

push_back always seems to have room: add one, and the vector gets one more box. How does it do that? This lesson looks at the memory behind a vector. Start with two numbers: size() is how many elements it holds now, and capacity() is how many it can hold before it has to move.

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> v;6    for (int i = 1; i <= 9; i++) {7        v.push_back(i * 10);8        std::cout << "size " << v.size() << ", capacity " << v.capacity() << '\n';9    }10    return 0;11}

size 1, capacity 1
size 2, capacity 2
size 3, capacity 4
size 4, capacity 4
size 5, capacity 8
size 6, capacity 8
size 7, capacity 8
size 8, capacity 8
size 9, capacity 16

capacity doesn't go up one at a time. It goes 1, 2, 4, 8, 16: each time it runs out of room, it doubles.

size and capacity

A vector keeps its elements in one block of memory on the heap (lesson 20 covered the heap). That block is usually a bit bigger than what's in use:

While size is less than capacity, push_back just fills the next free box, which is fast. When size equals capacity, the next push_back has to move.

Note: Doubling is what g++ does. The C++ standard only asks for "fast on average," and some compilers grow by 1.5 instead. Don't write programs that depend on the exact capacity.

Moving to a bigger block

When it's full, a vector does three things:

1. asks the heap for a bigger block (twice the size, in g++);
2. moves the old elements over one by one;
3. gives the old block back (like delete[]).

Press Step and go through the second and third push_back: watch the boxes of prices move to a new block of memory:

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> prices;6    prices.push_back(12);7    prices.push_back(30);8    prices.push_back(8);9    std::cout << "size " << prices.size() << ", capacity " << prices.capacity() << '\n';10    prices.push_back(45);11    std::cout << "size " << prices.size() << ", capacity " << prices.capacity() << '\n';12    return 0;13}

size 3, capacity 4
size 4, capacity 4

The fourth push_back doesn't move: the capacity is already 4, so there's exactly one free box left.

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> v{1, 2, 3};6    v.push_back(4);7    std::cout << v.capacity() << '\n';8    return 0;9}

After a move, old references are no good

Moving is handy, but there's a trap: if you're still holding a reference into the old block, after the move it refers to memory that has been given back. Below, first is a reference to v[0], and then push_back makes v move:

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> v{10, 20, 30};6    int& first = v[0];7    std::cout << "first: " << first << '\n';8    v.push_back(40);9    std::cout << "first: " << first << '\n';10    return 0;11}

first: 10
first: 
heap-use-after-free

Our engine stops at the last cout with heap-use-after-free: the program used heap memory that was already given back. first is still tied to the old block; the elements moved away long ago. It's the same mistake as using memory after delete in lesson 20. With a real compiler this line might still show 10 (nobody has reused the old memory yet) or some odd number: that's undefined behavior, and the hardest kind to track down. Press "see what went wrong" and step through it.

Pointers and iterators break the same way. This tries to "add a +5 score for each low score," calling push_back while it loops:

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> scores{70, 80};6    for (auto it = scores.begin(); it != scores.end(); ++it) {7        if (*it < 75) {8            scores.push_back(*it + 5);9        }10    }11    std::cout << scores.size() << '\n';12    return 0;13}

heap-use-after-free

push_back makes scores move, it still points into the old block, and the next *it goes wrong. Range for is an iterator loop underneath (last lesson), so don't add to scores inside for (int s : scores) either.

Note: The rule: after anything that can make a vector grow (push_back, insert, resize...), treat every reference, pointer and iterator you got before as broken. Get a fresh one if you need it.

Indexes don't break

An index means "the nth one," which has nothing to do with which block the elements live in, so it still works after a move. To remember which element you mean, keep its index:

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> v{10, 20, 30};6    std::size_t first = 0;7    v.push_back(40);8    v.push_back(50);9    v[first] += 1;10    std::cout << "First: " << v[first] << '\n';11    return 0;12}

First: 11

reserve: ask for room up front

If you know roughly how many elements are coming, call reserve(n) first: it gets one block big enough for n elements, and nothing moves until you go past n.

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> v;6    v.reserve(100);7    std::cout << "size " << v.size() << ", capacity " << v.capacity() << '\n';8    for (int i = 0; i < 100; i++) {9        v.push_back(i);10    }11    std::cout << "size " << v.size() << ", capacity " << v.capacity() << '\n';12    return 0;13}

size 0, capacity 100
size 100, capacity 100

reserve only gets memory; it adds no elements, so size() is still 0 and v[0] still isn't allowed. A hundred elements went in without a single move. Without reserve, doubling capacity from 1 to 128 would ask for memory 8 times, and the last 7 of those would also move.

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> v{1, 2, 3, 4, 5};6    v.clear();7    std::cout << v.size() << " " << v.capacity() << '\n';8    return 0;9}

Tip: You never have to reserve: the program is correct without it, and doubling is already fast on average. Use it when there are a great many elements and you know how many.

Practice

Write the code, then press Check. A hint costs nothing; the answer is there when you need it.

6 memory requests

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> v;6    int grows = 0;7 8    std::cout << grows << " memory requests\n";9    return 0;10}

Last: 60

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> v{20, 40};6    int& last = v.back();7    v.push_back(60);8    std::cout << "Last: " << last << '\n';9    return 0;10}

size 50, capacity 50
Last: 2500

1#include <iostream>2#include <vector>3 4int main() {5    std::vector<int> squares;6 7    return 0;8}

What you learned

• size() is how many are in it, capacity() how many the block holds; g++ doubles when full: 1, 2, 4, 8...
• When it's full, a vector moves: gets a bigger block, moves the elements over, gives the old block back.
• After a move, references, pointers and iterators from before point at given-back memory; using them is undefined behavior (our engine stops: heap-use-after-free).
• Don't add to a vector inside a range for or an iterator loop over it.
• Indexes don't break: to remember which element, keep its index.
• reserve(n) gets room for n up front without changing size(); clear() removes elements but keeps the memory.