Vector - std::vector

S2.0 What This Teaches

std::vector<T> is the default dynamic array in C++. This tutorial covers:

Creating and initializing vectors
push_back, pop_back, insert, erase
Element access: [], at(), front(), back()
Size vs capacity
Iterating with range-for and algorithms

S2.1 Creating a Vector

std::vector<int> v1 = {3, 1, 4, 1, 5, 9};   // initializer list
std::vector<int> v2(5, 0);                   // five zeros
std::vector<int> v3;                         // empty

// reserve capacity upfront to avoid repeated reallocation
std::vector<int> v4;
v4.reserve(100);

S2.2 push_back, pop_back, emplace_back

std::vector<int> v;
v.push_back(10);     // append by copy/move
v.push_back(20);
v.push_back(30);     // {10, 20, 30}

v.pop_back();        // remove last element: {10, 20}

v.emplace_back(30);  // construct in-place (more efficient for complex types)

S2.3 Element Access

std::vector<int> v = {10, 20, 30};

v[1];         // 20 - unchecked; undefined behavior if out of range
v.at(1);      // 20 - throws std::out_of_range if index invalid
v.front();    // 10 - first element
v.back();     // 30 - last element
v.data();     // raw pointer to underlying array

S2.4 Size and Capacity

std::vector<int> v;
v.reserve(10);          // allocate space for 10 without changing size

v.push_back(1);
v.push_back(2);
std::cout << v.size();      // 2  - number of elements
std::cout << v.capacity();  // 10 - allocated slots

v.shrink_to_fit();      // release excess capacity

When a vector runs out of capacity it reallocates to a larger buffer (typically 2×). reserve(n) before filling avoids repeated reallocations.

S2.5 insert and erase

std::vector<int> v = {1, 2, 4, 5};
v.insert(v.begin() + 2, 3);   // {1, 2, 3, 4, 5}
v.erase(v.begin() + 2);       // {1, 2, 4, 5}

Both are O(n) because elements after the insertion/deletion point must be shifted. Use push_back/pop_back for O(1) operations at the end.

S2.6 Example - All Together

// Vector - creation, access, iteration, modification.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

    std::sort(v.begin(), v.end());
    std::cout << "sorted: ";
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";

    v.erase(std::unique(v.begin(), v.end()), v.end());  // remove duplicates
    std::cout << "unique: ";
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";

    int sum = std::accumulate(v.begin(), v.end(), 0);
    std::cout << "sum=" << sum << " size=" << v.size() << "\n";

    v.push_back(99);
    v.pop_back();

    std::cout << "at(0)=" << v.at(0) << " back=" << v.back() << "\n";
    return 0;
}

sorted: 1 1 2 3 4 5 6 9
unique: 1 2 3 4 5 6 9
sum=30 size=7
at(0)=1 back=9

S2.7 Exercise

Exercise

Create a std::vector<double> of 10 values and write a function that returns the mean and the median.
Use std::remove_if followed by erase to remove all odd numbers from a vector (the erase-remove idiom).
Use reserve to pre-allocate space for 1 000 000 elements and fill with push_back. Repeat without reserve and observe the timing difference.

S2.8 Common Mistakes

Using [] with an out-of-range index

std::vector<int> v = {1, 2, 3};
std::cout << v[5];   // undefined behavior: no bounds check

Use v.at(5) during development to get a catchable exception.

Iterator invalidation after push_back

auto it = v.begin();
v.push_back(42);   // may reallocate; it is now dangling
std::cout << *it;  // undefined behavior

Do not hold iterators or pointers into a vector across any operation that may reallocate.

Confusing size and capacity

size() is the number of elements. capacity() is the number of elements that fit without reallocation. After reserve(100), size() is still 0.

S2.9 Key Terms

Term	Meaning
push_back	Append an element; may reallocate if at capacity
emplace_back	Construct element in-place at the end; avoids extra copy
pop_back	Remove the last element; O(1)
at(i)	Bounds-checked element access; throws std::out_of_range
reserve(n)	Ensure capacity for n elements without changing size
size()	Number of elements currently stored
capacity()	Elements that fit without reallocation
iterator invalidation	Reallocation makes existing iterators/pointers invalid