C++ Vectors

A vector is C++’s dynamic array: a container from the Standard Template Library (STL) that stores elements contiguously in memory, just like a plain array, but can grow or shrink at runtime. Unlike a fixed-size C-style array, you never need to know how many elements you’ll need in advance. Vectors are the default “go-to” container in C++ for storing a sequence of values, and understanding how they work under the hood (capacity, reallocation, iterators) is essential for writing efficient, correct C++ code.

Overview / How It Works

std::vector is a class template defined in the <vector> header. A vector manages a single, contiguous block of heap-allocated memory that holds its elements, exactly like an array. Because the memory is contiguous, you can index into a vector in O(1) constant time with operator[], and the underlying data can be accessed as a raw pointer via .data() for interoperability with C APIs.

A vector tracks two separate numbers internally:

  • size – the number of elements currently stored (what size() returns).
  • capacity – the number of elements the currently allocated block can hold before a new, larger block must be allocated (what capacity() returns).

When you call push_back() and the vector is already at full capacity, it cannot simply extend the existing memory block (something else might be using the bytes right after it), so it: (1) allocates a new, larger block of memory (typically double the old capacity), (2) copies or moves every existing element into the new block, (3) destroys the old elements, and (4) frees the old block. This is called reallocation. Because growth is geometric (usually 2x) rather than by a fixed amount, appending n elements one at a time still costs only amortized O(1) per element overall, even though any single push_back() that triggers a reallocation is O(n).

This also explains why pointers, references, and iterators into a vector can become invalid after a reallocation – the old memory block is gone, so anything pointing into it now points to freed memory.

Vectors are templates, so a vector<int>, a vector<string>, and a vector<Student> are all distinct types, each storing elements of exactly one type.

Syntax

#include <vector>

vector<Type> name;                 // empty vector
vector<Type> name(count);           // count default-constructed elements
vector<Type> name(count, value);    // count copies of value
vector<Type> name = {v1, v2, v3};   // initializer list
Member function Purpose
push_back(x) Append x to the end
pop_back() Remove the last element
size() Number of elements currently stored
capacity() Number of elements the current allocation can hold
empty() True if size() == 0
operator[] Access element by index, no bounds checking
at(i) Access element by index, throws std::out_of_range if invalid
front() / back() Reference to first / last element
insert(pos, x) Insert x before iterator pos
erase(pos) Remove the element at iterator pos
clear() Remove all elements (size becomes 0)
reserve(n) Pre-allocate capacity for at least n elements
resize(n) Change size to n, adding/removing elements as needed
begin() / end() Iterators to the first element / one-past-the-last

Examples

Example 1: Basic vector usage

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

int main() {
    vector<int> scores;
    scores.push_back(85);
    scores.push_back(92);
    scores.push_back(78);

    cout << "Number of scores: " << scores.size() << endl;

    for (int i = 0; i < scores.size(); i++) {
        cout << "Score " << i << ": " << scores[i] << endl;
    }

    for (int s : scores) {
        cout << s << " ";
    }
    cout << endl;

    return 0;
}

Output:

Number of scores: 3
Score 0: 85
Score 1: 92
Score 2: 78
85 92 78

This creates an empty vector<int> and grows it with push_back(). Indexing with [] works exactly like an array, and the range-based for loop visits every element without needing an index at all.

Example 2: Inserting, erasing, and safe access

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

int main() {
    vector<string> fruits = {"apple", "banana", "cherry"};

    fruits.insert(fruits.begin() + 1, "blueberry");
    cout << "After insert: ";
    for (const string& f : fruits) cout << f << " ";
    cout << endl;

    fruits.erase(fruits.begin());
    cout << "After erase: ";
    for (const string& f : fruits) cout << f << " ";
    cout << endl;

    cout << "Front: " << fruits.front() << endl;
    cout << "Back: " << fruits.back() << endl;

    try {
        cout << fruits.at(10) << endl;
    } catch (const out_of_range& e) {
        cout << "Caught exception: " << e.what() << endl;
    }

    return 0;
}

Output:

After insert: apple blueberry banana cherry 
After erase: blueberry banana cherry 
Front: blueberry
Back: cherry
Caught exception: vector::_M_range_check: __n (which is 10) >= this->size() (which is 3)

insert() and erase() take an iterator position, which is why fruits.begin() + 1 is used to insert at index 1. Note that at() performs bounds checking and throws std::out_of_range on an invalid index, while operator[] does not check at all.

Example 3: A realistic use – sorting a vector of structs

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

struct Student {
    string name;
    int score;
};

int main() {
    vector<Student> students = {
        {"Alice", 82},
        {"Bob", 95},
        {"Carla", 78}
    };

    sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
        return a.score > b.score;
    });

    for (const Student& s : students) {
        cout << s.name << ": " << s.score << endl;
    }

    return 0;
}

Output:

Bob: 95
Alice: 82
Carla: 78

Vectors work seamlessly with the <algorithm> header. Here, sort() takes a begin/end iterator range plus a lambda comparator, and reorders the vector’s elements in place to rank students by score, highest first.

Under the Hood: Capacity Growth

The following program prints size() and capacity() after each push_back() to reveal how a typical implementation (GCC’s libstdc++) doubles capacity when it runs out of room:

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

int main() {
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
        cout << "size=" << v.size() << " capacity=" << v.capacity() << endl;
    }
    return 0;
}

Output:

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
size=10 capacity=16

Notice capacity jumps 1 → 2 → 4 → 8 → 16: each time size would exceed capacity, a reallocation doubles it. The exact growth factor is implementation-defined (not guaranteed by the standard), but doubling is the common strategy because it keeps the amortized cost of push_back() at O(1). If you know in advance roughly how many elements you’ll store, call reserve(n) once up front – this pre-allocates capacity for n elements and avoids repeated reallocations and copies entirely. resize(n) is different: it actually changes the size, constructing or destroying elements as needed, not just the capacity.

Common Mistakes

Mistake 1: Using operator[] for out-of-range access

It’s tempting to index a vector like an array without checking bounds:

vector<int> v = {1, 2, 3};
cout << v[10] << endl; // undefined behavior: no bounds checking!

operator[] performs no bounds checking, so this reads garbage memory (or crashes) instead of producing a clean error. Use at() when the index isn’t already guaranteed valid, since it throws a catchable exception:

vector<int> v = {1, 2, 3};
try {
    cout << v.at(10) << endl;
} catch (...) {
    cout << "Index out of range!" << endl;
}

Output:

Index out of range!

Mistake 2: Erasing from a vector while iterating with a stale iterator

Calling erase() invalidates the iterator passed to it (and every iterator after it). Continuing to use that iterator afterward is undefined behavior:

vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it == 3) {
        v.erase(it); // invalidates it; the loop's ++it is now undefined behavior
    }
}

The fix is to capture erase()‘s return value, which is a valid iterator pointing to the element right after the one removed, and only advance manually otherwise:

vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end(); ) {
    if (*it == 3) {
        it = v.erase(it);
    } else {
        ++it;
    }
}
for (int x : v) cout << x << " ";
cout << endl;

Output:

1 2 4 5

Best Practices

  • Prefer at() over [] whenever an index might be invalid; reserve [] for hot loops where the index is already known to be safe.
  • Call reserve(n) up front when you know (or can estimate) the final size, to avoid repeated reallocations.
  • Pass vectors by const& to functions that only read them, to avoid an expensive copy of every element.
  • Use range-based for loops (for (const auto& x : v)) instead of manual index loops when you don’t need the index – it’s clearer and avoids off-by-one bugs.
  • Remember that push_back(), insert(), and erase() can invalidate iterators, pointers, and references into the vector; never hold onto them across such a call.
  • Use the erase-remove idiom (v.erase(remove(v.begin(), v.end(), value), v.end())) to remove all matching elements efficiently, rather than erasing one at a time.
  • Prefer emplace_back() over push_back() when constructing complex objects in place, to avoid an extra copy or move.

Practice Exercises

  • Write a program that reads 5 integers from the user with cin into a vector<int> (using a loop and push_back), then prints their sum and average.
  • Given vector<string> names = {"Al", "Beatrice", "Cy", "Donna", "Ed"};, write code that removes every name with fewer than 4 characters and prints the remaining names. (Hint: look up the erase-remove idiom, or erase manually using a corrected iterator loop like the one in Mistake 2.)
  • Write a program that creates an empty vector<int>, calls resize(10), and prints size() and capacity(). Then, on a fresh empty vector, call reserve(10) instead and print size() and capacity(). Explain in a comment why the two results differ.

Summary

  • A vector is a dynamic array: contiguous memory, O(1) indexed access, and automatic resizing.
  • Vectors track both size() (elements stored) and capacity() (allocated room); when size would exceed capacity, the vector reallocates, typically doubling capacity, and moves all elements to new memory.
  • This doubling strategy gives push_back() amortized O(1) performance, even though any single call that triggers reallocation costs O(n).
  • Use reserve() to pre-allocate capacity when the final size is known ahead of time, and resize() to actually change how many elements exist.
  • Prefer at() for bounds-checked access and be careful never to use iterators, pointers, or references after an operation that may invalidate them (like push_back, insert, or erase).
  • Vectors integrate directly with <algorithm> functions like sort(), find(), and remove() via their begin()/end() iterators.