std::vector in depth

Why vector is the default container

The STL (Standard Template Library) is the part of the C++ standard library that gives you containers (things that hold elements) and algorithms (things that work on them). Among the containers, std::vector is the one you should reach for first. Its elements sit in one continuous block of memory, exactly like an array, which makes it very fast for the processor's cache (a small, very fast memory that loves data stored side by side).

Size and capacity

size() is how many elements the vector holds. capacity() is how many it could hold before it must get a bigger block of memory. When you push_back into a full vector, it allocates a bigger block (typically 1.5× or 2× the old capacity), moves the elements across and frees the old block. Because growth is geometric, the average cost of push_back stays constant: this is called amortised O(1).

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;
    for (int i = 0; i < 6; ++i) {
        v.push_back(i);
        std::cout << "size " << v.size() << " capacity " << v.capacity() << '\n';
    }
    std::vector<int> orders;
    orders.reserve(100000);     // one allocation up front when you know the size
}

Common operations and their cost

O(1) means the time does not grow with the number of elements; O(n) means it grows in proportion to n. You will use this notation (Big-O) for the rest of the course.

emplace_back

struct Order { std::string item; int qty; };
std::vector<Order> cart;
cart.push_back(Order{"Rice", 2});     // builds an Order, then moves it in
cart.emplace_back("Dal", 1);          // builds the Order directly inside the vector

Iterator invalidation

Removing elements safely

std::vector<int> marks = {35, 80, 20, 90, 15};
// C++20: remove every value below 33
std::erase_if(marks, [](int m) { return m < 33; });     // marks is {80, 90}

// Before C++20: the erase-remove idiom
std::vector<int> v = {1, 0, 2, 0, 3};
v.erase(std::remove(v.begin(), v.end(), 0), v.end());   // v is {1, 2, 3}

Other useful operations

• v.clear() removes all elements (capacity usually stays).
• v.resize(n) changes the size, adding default values or dropping elements.
• v.empty() is true when size() is 0; check it before front(), back() or v[0].
• v.data() gives a pointer to the first element, for C functions.
• Two vectors can be compared with == and < (element by element).