C++ / Intermediate / Lesson 9

Algorithms, iterators, and containers

Compose standard algorithms over valid iterator ranges, honor their preconditions, and choose containers by required operations rather than familiarity.

About 4 min readContent reviewed 2026-10-23

On this page

Lesson goals

Explain half-open iterator ranges and past-the-end positions.
Apply sorting, accumulation, and erase-remove correctly.
Select containers using ordering, lookup, and stability needs.

A valid range excludes its end

A classic algorithm commonly accepts a half-open range [first, last). first identifies the first element, and last identifies a position just beyond the final element. An empty range has equal endpoints. Never dereference the past-the-end iterator. Iterators from unrelated containers do not form a valid range even if their printed addresses appear nearby. Iterator categories describe supported traversal capabilities: sort needs random access, while many searches work with weaker categories. Match the algorithm requirements to the container instead of assuming every iterator supports addition and subtraction.

Separate order from aggregation

The first example sorts a vector and then accumulates its values. std::sort changes element order and does not promise stability for equivalent elements. Its comparator must define a strict weak ordering, so less-than-or-equal is not a valid substitute for less-than. accumulate starts with the initial value type; using zero selects int arithmetic here. For large totals, choose and validate a wider accumulator deliberately. Algorithms do not remove numeric overflow risks, and the standard library cannot infer a domain-specific maximum from the container contents.

cpp Sort, then reduce a small sequence

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
int main() {
    std::vector<int> values{4, 1, 3, 2};
    std::sort(values.begin(), values.end());
    for (int value : values) { std::cout << value << " "; }
    std::cout << "sum=" << std::accumulate(values.begin(), values.end(), 0) << "\n";
}

Expected output

1 2 3 4 sum=10

The values become ascending and the total is ten. The integer inputs avoid equivalent-order and overflow ambiguity.

An algorithm cannot resize its container

std::remove_if moves retained elements toward the beginning and returns the new logical end. It does not change vector size. The trailing elements remain valid but have unspecified values, so do not interpret them as the removed records. Erasing the returned tail performs structural removal. The second example names the logical end and erases exactly that tail. C++20 also offers std::erase_if for several standard containers, but understanding the two-step pattern explains older code and distinguishes algorithm-level rearrangement from container-level lifetime changes.

cpp Erase even numbers without invalid traversal

#include <algorithm>
#include <iostream>
#include <vector>
int main() {
    std::vector<int> values{1, 2, 3, 4, 5};
    const auto logical_end = std::remove_if(values.begin(), values.end(),
        [](int value) { return value % 2 == 0; });
    values.erase(logical_end, values.end());
    for (int value : values) { std::cout << value << " "; }
    std::cout << "size=" << values.size() << "\n";
}

Expected output

1 3 5 size=3

The predicate selects two and four for removal. The retained relative order is one, three, five, and erasing the tail sets size to three.

Choose the operations you actually need

vector is a strong default for contiguous traversal and compact storage. map keeps keys ordered and supports logarithmic lookup; unordered_map offers average constant-time lookup with no useful iteration-order guarantee and possible worst-case linear behavior. list keeps iterators to other elements stable across many insertions but pays allocation and locality costs. Complexity describes growth with input size, not a measured speed ranking. Check invalidation rules, memory overhead, and ordering requirements together. Calling operator[] on a map can insert a missing key, so use find when observation must not mutate the container.

Check preconditions before trusting results

Binary search needs a range ordered under the same comparison used for searching. lower_bound returns the first position not less than the target, which may be end and may not be an equal element. Validate both conditions before reporting a hit. Predicates should be readable and should not invalidate the range they inspect. When modifying a container during traversal, use the erase return value where the API requires it. Debug iterator modes can detect many mistakes, but they complement rather than replace a proof that the range and lifetime remain valid.

Common errors and fixes

remove_if leaves the vector size unchanged.

Why it happens: The algorithm only compacts the logical range.
How to fix it: Erase from its returned iterator through end.
Prevent it next time: Separate rearrangement from structural container changes.

A comparator uses <= and sorting misbehaves.

Why it happens: The comparison is not irreflexive.
How to fix it: Use a strict ordering such as < with coherent tie handling.
Prevent it next time: Check compare(x, x) is false and review ordering laws.

A search result is dereferenced at end.

Why it happens: The no-match case was omitted.
How to fix it: Compare against end before element access.
Prevent it next time: Test empty ranges and missing targets explicitly.

Check your understanding

1. Search sorted values 2, 5, 8 with lower_bound for six. Explain the returned position and whether it proves membership.

Show worked solution

The returned iterator identifies eight, the first element not less than six. It differs from end but does not equal the requested value, so six is absent. A complete membership check requires iterator != end and *iterator == target. Searching for nine instead returns end and must not dereference it.

2. A reporting job needs ordered traversal and frequent reads of named totals. Choose map or unordered_map and explain when that choice could change.