Chapter 8: The Standard Library – Containers and Algorithms

The C++ standard library is large, well-tested, and often faster than code you would write yourself. Learning to use it effectively is one of the highest-leverage skills in the language. This chapter covers the containers and algorithms you will reach for most often.

The rule is simple: before you write a loop, check if there is an algorithm that does what you want. Before you write a data structure, check if a standard container fits. The library is written by people who have been thinking about these problems for decades.

8.1 std::vector

std::vector<T> is a dynamic array. It grows automatically as you add elements, stores elements contiguously in memory (like a C array), and supports random access in O(1). It is the right default container for most use cases.

#include <iostream>
#include <vector>
#include <string>
#include <numeric>

int main() {
    // Construction
    std::vector<int> empty;
    std::vector<int> sized(5, 0);                   // 5 zeros
    std::vector<int> init{10, 20, 30, 40, 50};      // initializer list
    std::vector<std::string> names;

    // Adding elements
    names.push_back("Alice");
    names.push_back("Bob");
    names.emplace_back("Carol");  // constructs in place — preferred for objects

    // Accessing
    std::cout << "First: " << names[0] << "\n";       // no bounds check
    std::cout << "First: " << names.at(0) << "\n";    // throws if out of range
    std::cout << "Last:  " << names.back() << "\n";
    std::cout << "Size:  " << names.size() << "\n";

    // Iterating
    for (const auto& name : names) {
        std::cout << name << "\n";
    }

    // Numeric sum
    std::vector<double> values{1.5, 2.5, 3.5, 4.5, 5.5};
    double total = std::accumulate(values.begin(), values.end(), 0.0);
    std::cout << "Sum: " << total << "\n";  // 17.5

    // Removing
    names.pop_back();              // removes last element
    names.erase(names.begin());    // removes first (shifts all others — O(n))

    // Reserve to avoid reallocations when you know the final size
    std::vector<int> big;
    big.reserve(1000);
    for (int i = 0; i < 1000; ++i) big.push_back(i);
    std::cout << "Size: " << big.size() << ", Capacity: " << big.capacity() << "\n";

    return 0;
}

When to use vector: almost always. It has the best cache performance of any container (contiguous memory), the simplest interface, and the fewest surprises. Default to vector and switch to another container only when you have a measured reason.

push_back vs emplace_back: push_back copies or moves an existing object. emplace_back constructs in place, passing arguments directly to the element's constructor. For primitive types they are equivalent; for objects, emplace_back can be more efficient.

Invalidation: operations that cause reallocation (push_back when size == capacity, insert, erase) invalidate all iterators and pointers into the vector. Do not hold iterators across such operations.

8.2 std::array

std::array<T, N> is a fixed-size array whose size is part of the type and is known at compile time. It lives on the stack (unless you new it), has zero overhead compared to a C array, and works with all standard algorithms.

#include <iostream>
#include <array>
#include <algorithm>
#include <numeric>

int main() {
    std::array<int, 5> scores{92, 85, 78, 96, 88};
    std::array<double, 3> point{1.0, 2.0, 3.0};

    std::cout << "Size: " << scores.size() << "\n";   // 5
    std::cout << "First: " << scores.front() << "\n"; // 92
    std::cout << "Last: " << scores.back() << "\n";   // 88

    // Works with all standard algorithms
    std::sort(scores.begin(), scores.end());
    for (int s : scores) std::cout << s << " ";
    std::cout << "\n";  // 78 85 88 92 96

    double avg = std::accumulate(scores.begin(), scores.end(), 0.0) / scores.size();
    std::cout << "Average: " << avg << "\n";

    // Cannot resize
    // scores.push_back(100);  // compile error

    // Structured binding
    auto [x, y, z] = point;
    std::cout << x << " " << y << " " << z << "\n";

    return 0;
}

Use std::array instead of C-style arrays (int arr[5]). It has bounds checking in debug builds (via .at()), a .size() method, and works with all algorithms. It has identical performance and memory layout to a C array.

8.3 std::map and std::unordered_map

Both are key-value stores. std::map keeps keys sorted (binary search tree, O(log n) operations). std::unordered_map uses a hash table (O(1) average, O(n) worst case). Choose based on whether you need sorted iteration.

#include <iostream>
#include <map>
#include <unordered_map>
#include <string>

int main() {
    // std::map: sorted by key, O(log n)
    std::map<std::string, int> wordCount;

    for (const std::string& word : {"apple", "banana", "apple", "cherry", "banana", "apple"}) {
        wordCount[word]++;  // creates entry with value 0 if key is absent
    }

    // Iterates in sorted alphabetical order
    for (const auto& [word, count] : wordCount) {
        std::cout << word << ": " << count << "\n";
    }

    // Lookup without creating an entry: use find()
    if (auto it = wordCount.find("banana"); it != wordCount.end()) {
        std::cout << "banana: " << it->second << "\n";
    }

    // Check existence without inserting: use count() (0 or 1 for map)
    if (wordCount.count("mango") == 0) {
        std::cout << "mango not found\n";
    }

    std::cout << "\n";

    // std::unordered_map: hash-based, O(1) average, unordered
    std::unordered_map<std::string, int> fastCount;
    for (const std::string& word : {"apple", "banana", "apple", "cherry", "banana", "apple"}) {
        fastCount[word]++;
    }

    // Order not guaranteed — print in whatever order the hash table gives
    for (const auto& [word, count] : fastCount) {
        std::cout << word << ": " << count << "\n";
    }

    return 0;
}

Important gotcha: map[key] inserts a default-initialized value if the key does not exist. This means if (wordCount["typo"] == 0) creates an entry for "typo" with value 0. Use find() or count() to check without inserting.

std::set and std::unordered_set are the sorted/hashed versions of sets (keys only, no values). Same performance characteristics.

8.4 std::string and std::string_view

std::string owns its character data. std::string_view (C++17) is a non-owning view into an existing string — a pointer and a length. Passing string_view costs nothing; passing string by value copies the characters.

#include <iostream>
#include <string>
#include <string_view>
#include <algorithm>

// Use string_view for read-only string parameters — zero copy
bool startsWith(std::string_view sv, std::string_view prefix) {
    return sv.size() >= prefix.size() &&
           sv.substr(0, prefix.size()) == prefix;
}

void printFirstN(std::string_view sv, size_t n) {
    std::cout << sv.substr(0, std::min(n, sv.size())) << "\n";
}

int main() {
    std::string greeting{"Hello, World!"};

    // Common operations
    std::cout << "Length: " << greeting.size() << "\n";
    std::cout << "Empty: " << greeting.empty() << "\n";

    // Finding
    size_t pos = greeting.find("World");
    if (pos != std::string::npos) {
        std::cout << "'World' at position " << pos << "\n";
        std::cout << "Substring: " << greeting.substr(pos, 5) << "\n";  // World
    }

    // Concatenation
    std::string a{"Hello"};
    std::string b{", C++!"};
    std::string c = a + b;  // creates new string
    a += b;                  // appends in place
    std::cout << "c: " << c << "\n";
    std::cout << "a: " << a << "\n";

    // To uppercase (modify in place)
    std::string s{"hello world"};
    for (char& ch : s) ch = static_cast<char>(std::toupper(ch));
    std::cout << s << "\n";

    // string_view: no copy, works with string literals and std::string
    std::cout << std::boolalpha;
    std::cout << startsWith("Hello, World", "Hello") << "\n";   // true
    std::cout << startsWith(greeting, "Goodbye") << "\n";       // false
    printFirstN("Hello, World!", 5);                             // Hello

    // Conversion
    int n = std::stoi("42");
    double d = std::stod("3.14");
    std::string ns = std::to_string(100);
    std::cout << n << " " << d << " " << ns << "\n";

    return 0;
}

Rule: use const std::string& or std::string_view for function parameters that only read the string. Prefer std::string_view in new code — it accepts char*, std::string, and string literals without any conversion or copy. The one case where std::string_view is dangerous is if you store it as a member or return it: the underlying data must outlive the view.

8.5 Iterators

Iterators are the abstraction that lets algorithms work on any container. An iterator points to an element in a container; you can dereference it with *, advance it with ++, and compare two iterators with ==.

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

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

    // begin() points to first element; end() points past the last
    auto it = v.begin();
    std::cout << "First: " << *it << "\n";  // 5
    ++it;
    std::cout << "Second: " << *it << "\n";  // 3

    // Reverse iterators: rbegin/rend
    std::cout << "Reversed: ";
    for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
        std::cout << *rit << " ";
    }
    std::cout << "\n";

    // std::find returns an iterator
    auto found = std::find(v.begin(), v.end(), 3);
    if (found != v.end()) {
        std::cout << "Found 3 at index " << std::distance(v.begin(), found) << "\n";
    }

    // Insert at a position
    v.insert(v.begin() + 2, 99);
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";

    return 0;
}

In modern C++ you use range-based for loops and algorithms rather than raw iterators for most work. But you need to understand iterators to understand what the algorithms do and to use find, lower_bound, erase, and other iterator-returning functions correctly.

The pattern container.begin() / container.end() appears constantly. end() points one past the last element — it is a sentinel value, not dereferenceable. Any algorithm that searches returns end() on failure.

8.6 Algorithms: sort, find, transform, and friends

The <algorithm> header contains over 100 algorithms. You will use about 15 of them regularly.

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

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

    // sort: O(n log n), in-place, requires random access
    std::sort(v.begin(), v.end());
    std::cout << "Sorted: ";
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";  // 1 1 2 3 3 4 4 5 5

    // unique + erase: remove consecutive duplicates (sort first!)
    auto last = std::unique(v.begin(), v.end());
    v.erase(last, v.end());
    std::cout << "Unique: ";
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";  // 1 2 3 4 5

    // count and count_if
    std::vector<int> data{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int evenCount = std::count_if(data.begin(), data.end(), [](int x) { return x % 2 == 0; });
    std::cout << "Even count: " << evenCount << "\n";  // 5

    // transform: apply a function to every element, write to output
    std::vector<int> squares(data.size());
    std::transform(data.begin(), data.end(), squares.begin(), [](int x) { return x * x; });
    std::cout << "Squares: ";
    for (int x : squares) std::cout << x << " ";
    std::cout << "\n";

    // accumulate: fold (reduce)
    int total = std::accumulate(data.begin(), data.end(), 0);
    std::cout << "Sum: " << total << "\n";  // 55

    // Accumulate with custom operation: product
    long long product = std::accumulate(data.begin(), data.end(), 1LL,
                                         [](long long acc, int x) { return acc * x; });
    std::cout << "Product: " << product << "\n";  // 3628800

    // min_element and max_element
    auto minIt = std::min_element(data.begin(), data.end());
    auto maxIt = std::max_element(data.begin(), data.end());
    std::cout << "Min: " << *minIt << ", Max: " << *maxIt << "\n";

    // any_of, all_of, none_of
    bool allPos  = std::all_of(data.begin(),  data.end(), [](int x) { return x > 0; });
    bool anyGt5  = std::any_of(data.begin(),  data.end(), [](int x) { return x > 5; });
    bool noneNeg = std::none_of(data.begin(), data.end(), [](int x) { return x < 0; });
    std::cout << std::boolalpha;
    std::cout << "All positive: " << allPos  << "\n";  // true
    std::cout << "Any > 5: "     << anyGt5  << "\n";  // true
    std::cout << "None negative: "<< noneNeg << "\n";  // true

    // binary_search (requires sorted range)
    std::vector<int> sorted{1, 3, 5, 7, 9, 11};
    std::cout << "Contains 7: " << std::binary_search(sorted.begin(), sorted.end(), 7) << "\n";
    std::cout << "Contains 6: " << std::binary_search(sorted.begin(), sorted.end(), 6) << "\n";

    // partition: elements satisfying predicate come first
    std::vector<int> mixed{1, 2, 3, 4, 5, 6, 7, 8};
    auto mid = std::partition(mixed.begin(), mixed.end(), [](int x) { return x % 2 == 0; });
    std::cout << "Evens: ";
    for (auto it = mixed.begin(); it != mid; ++it) std::cout << *it << " ";
    std::cout << "| Odds: ";
    for (auto it = mid; it != mixed.end(); ++it) std::cout << *it << " ";
    std::cout << "\n";

    // remove_if + erase: remove elements that satisfy a predicate
    std::vector<int> nums{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    auto newEnd = std::remove_if(nums.begin(), nums.end(), [](int x) { return x % 2 == 0; });
    nums.erase(newEnd, nums.end());
    std::cout << "Odd only: ";
    for (int x : nums) std::cout << x << " ";
    std::cout << "\n";  // 1 3 5 7 9

    return 0;
}

The remove_if + erase idiom (the "erase-remove idiom") is so common it is worth memorizing. std::remove_if moves elements that should be kept to the front and returns an iterator to the new end; then erase actually removes the "dead" elements from the container.

8.7 Ranges (C++20)

Ranges provide a composable, pipeline-style interface to algorithms. They are lazy: the filter and transform do not run until you iterate.

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

int main() {
    std::vector<int> data{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // Traditional: filter evens, square them, collect into vector
    std::vector<int> result;
    for (int x : data) {
        if (x % 2 == 0) result.push_back(x * x);
    }
    for (int x : result) std::cout << x << " ";
    std::cout << "\n";  // 4 16 36 64 100

    // With ranges: composable pipeline, evaluated lazily
    auto view = data
        | std::views::filter([](int x) { return x % 2 == 0; })
        | std::views::transform([](int x) { return x * x; });

    for (int x : view) std::cout << x << " ";
    std::cout << "\n";  // 4 16 36 64 100

    // Take first 3 multiples of 3
    auto mult3 = data
        | std::views::filter([](int x) { return x % 3 == 0; })
        | std::views::take(3);

    for (int x : mult3) std::cout << x << " ";
    std::cout << "\n";  // 3 6 9

    // Reverse
    auto rev = data | std::views::reverse | std::views::take(3);
    for (int x : rev) std::cout << x << " ";
    std::cout << "\n";  // 10 9 8

    // Collect a range view into a vector (C++23 has std::ranges::to)
    // In C++20, use the range constructor or std::ranges::copy:
    std::vector<int> squares;
    std::ranges::copy(view, std::back_inserter(squares));
    std::cout << "Squares vector size: " << squares.size() << "\n";

    return 0;
}

Ranges also work directly with algorithms in <ranges>:

#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>

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

    // std::ranges::sort works without begin/end
    std::ranges::sort(v);
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";  // 1 2 3 5 8 9

    // std::ranges::find
    auto it = std::ranges::find(v, 5);
    if (it != v.end()) std::cout << "Found 5 at index " << std::distance(v.begin(), it) << "\n";

    return 0;
}

Compile with -std=c++20 for Ranges.

Ranges are the direction the standard library is moving. In new projects targeting C++20 or later, prefer the ranges versions of algorithms over the iterator-pair versions.

8.8 Exercises

Easy

1. Count the frequency of each character in a fixed string using std::map<char, int>. Print the results in alphabetical order of the character.

2. Given a std::vector<int>, use std::sort, std::unique, and erase to produce a sorted vector of unique values.

Medium

3. Given a std::vector<std::string> of words, use std::transform to produce a new vector where every word has its first letter capitalized. Do not use a raw loop in main — put the transformation in a lambda.

Stretch

4. Define a struct Employee { std::string name; std::string department; double salary; }. Given a std::vector<Employee>, use C++20 ranges to produce a new sorted-by-salary vector of all employees in a given department. Use std::views::filter, std::views::transform (or directly collect), and std::ranges::sort.

8.9 Common mistakes

• Using vector[i] when bounds checking is needed. operator[] does not check bounds — it is undefined behavior if i >= size(). Use .at(i) when you are not sure the index is valid.

• Invalidating iterators during iteration. Calling push_back, insert, or erase on a vector while holding an iterator into it can invalidate that iterator. Collect modifications and apply them after the loop.

• Forgetting the erase step in the erase-remove idiom. std::remove_if returns an iterator to the new logical end but does not shrink the vector. Without the erase call, the "removed" elements are still in the vector in an unspecified state.

• Using map[key] to check existence. operator[] inserts a default-initialized value if the key is absent. Use find() or count() to check without side effects.

• Comparing string::npos as a signed integer. std::string::npos is size_t(-1) — a very large unsigned number. If you write int pos = s.find("x"); if (pos == -1), the signed/unsigned comparison may not behave as expected. Use size_t pos and compare with std::string::npos.

• Not reserving vector capacity when the final size is known. If you are going to push_back a million elements, call reserve(1'000'000) first to avoid repeated reallocations.

• Using std::string_view after the underlying string is destroyed. string_view is a view; it does not own the data. If the std::string it refers to goes out of scope, the string_view is dangling.

• Sorting an unsorted range before binary_search. std::binary_search, std::lower_bound, and std::upper_bound require a sorted range. The results on unsorted input are undefined.

8.10 Summary

std::vector is your default container: dynamic, contiguous, fast. Use it unless you have a specific reason to use something else.

std::array is the modern replacement for C arrays: fixed size, stack-allocated, works with all algorithms.

std::map gives sorted key-value storage in O(log n). std::unordered_map gives hash-based storage in O(1) average. Use find() to check existence without inserting.

std::string owns character data. std::string_view is a non-owning view — prefer it for read-only string parameters.

The <algorithm> header contains reusable operations on ranges: sort, find, transform, accumulate, count_if, remove_if, and many more. Learn the 15 most common ones.

Ranges (C++20) provide a composable, lazy pipeline interface that makes complex data transformations readable.

In Chapter 9 we look at error handling — what to do when things go wrong.

All code for this chapter is in the GitHub repository:
<TODO: book code repository URL>/tree/main/chapter08