STL: Containers & Algorithms

The parcel desk asks different questions

A parcel desk records deliveries. Sometimes it needs the delivery at position five. Sometimes it needs all parcels grouped by destination, in destination order. Sometimes it only needs to know whether a tracking code has been seen before. These are different questions, and a representation that answers one conveniently may make another expensive.

The standard library separates containers, which organize data, from algorithms, which operate on ranges. Learning the library is not remembering a list of names. It is matching the operations a program needs to the guarantees those types and algorithms provide. This lesson uses parcel records throughout; the lab uses other data and other tasks.

You need vectors, references, lifetime and the basic cost analysis from module 9. We stay in C++17. Ranges and views are useful later, but code here uses iterator pairs, ordinary algorithms and lambdas. Every example includes each standard header it uses rather than relying on one header happening to include another.

The obvious loop can hide the wrong representation

Suppose the desk stores every tracking code in a vector. Each arriving parcel requires a membership test. Scanning the vector takes linear comparisons in the number of earlier codes in the worst case. Repeating that work for many arrivals can create quadratic total comparisons. The loop is correct, but the representation is answering membership through a positional sequence.

A set can express uniqueness directly. An ordered set (std::set) finds a key with a number of key comparisons logarithmic in its number of elements. An unordered set (std::unordered_set) finds a key in constant time on average, where the average assumes the hash function spreads the keys across the table. In the worst case, when many keys collide, a lookup is linear in the number of elements.

Both bounds count key operations, and a key operation is not always one step. Hashing a long string reads every character. Comparing two long strings reads characters until they differ, so each of the logarithmically many comparisons in an ordered set can cost up to the key's length. A model that treats each key operation as constant hides both costs.

Changing containers does not automatically improve every operation. A vector still offers contiguous storage and constant-time indexed access. It is often a good choice for scanning and sorting a batch. State the workload before declaring a container “fast.” A container has a menu of operation costs, not one universal speed.

Choose by the questions you ask

For a weight per destination, a map associates each destination key with a number. For a delivery sequence, a vector preserves positional order. For a membership filter, a set stores each key once. A map does not preserve arrival order unless the key itself encodes that order. An unordered map does not promise any iteration order at all.

#include <map>
#include <string>
#include <vector>

struct Parcel {
    std::string city;
    int kg;
};

int main() {
    std::vector<Parcel> arrivals{{"Oslo", 4}, {"Lima", 9}, {"Oslo", 3},
                                 {"Cairo", 8}, {"Lima", 1}};
    std::map<std::string, int> kg_to;
    for (const Parcel& parcel : arrivals) {
        kg_to[parcel.city] += parcel.kg;  // [] makes a missing key, value 0
    }
    std::string report;
    for (const auto& entry : kg_to) {  // keys come out sorted
        report += entry.first + ":" + std::to_string(entry.second) + " ";
    }
    return report == "Cairo:8 Lima:10 Oslo:7 " ? 0 : 1;
}

Oslo arrived first and is reported last, because the map's order is the key order. If the desk promises alphabetical destinations, that order belongs in the specification, and either an ordered map or an explicit sort of the output must deliver it. A frequent error is to let the chosen container decide the product's output order by accident. Tests should insert keys in several orders so that agreement on one lucky example cannot pass for a guarantee.

Containers also differ in what a change does to references you already hold. Module 9 showed that a vector's growth moves its elements, so every iterator, reference and pointer into it is invalidated. Inserting into a std::map or std::set invalidates none of them. The unordered containers sit in between: when an insertion makes the table rehash, all iterators are invalidated, but references and pointers to the elements themselves stay valid. Erasing an element from any of these associative containers invalidates only what referred to the erased element.

A range says where an algorithm may work

An iterator pair [first, last) describes a half-open range. The first iterator belongs to the range; the last marks the position just past it. An empty range has equal endpoints. This convention handles empty containers without inventing a negative “last index.”

std::find searches for a value and returns last if none is found. std::count_if visits the elements and counts those satisfying a predicate. std::accumulate, declared in <numeric>, combines a sequence with an initial value. The type of that initial value is the type of the running total, so an initial 0 makes an int total even when the elements are long long or double.

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

int main() {
    std::vector<int> weights{4, 9, 3, 8};
    auto heavy = std::count_if(weights.begin(), weights.end(),
                               [](int x) { return x >= 8; });
    long long total = std::accumulate(weights.begin(), weights.end(), 0LL);
    return heavy == 2 && total == 24 ? 0 : 1;
}

The lambda gives the predicate at its point of use. The algorithm owns traversal; the function owns the decision. Keeping these responsibilities separate makes the code easier to inspect: there is no index increment to get wrong, and the condition is visible where the count is requested.

Sorting expresses a relationship

A comparator answers whether its first argument must appear before its second. It must define a strict weak ordering. In particular, an element does not come before itself. Using <= as the comparison violates that requirement, and the standard then says nothing about what std::sort does: the behavior is undefined.

Strictness is necessary but not sufficient. If a goes before b, then b must not go before a. The relationship must be transitive, and so must the equivalence it induces: when neither of two values precedes the other, they are equivalent, and equivalence has to chain as well. A comparator that uses random choices, toggles its decision on each call, or reads state that changes during the sort breaks the algorithm's assumptions even if it uses < somewhere.

The desk sorts parcels by urgency, most urgent first, and breaks ties by destination name.

#include <algorithm>
#include <string>
#include <vector>

struct Parcel {
    std::string city;
    int urgency;
};

int main() {
    std::vector<Parcel> queue{{"Cairo", 4}, {"Oslo", 7},
                              {"Bergen", 4}, {"Lima", 2}};
    std::sort(queue.begin(), queue.end(), [](const Parcel& a, const Parcel& b) {
        if (a.urgency != b.urgency) {
            return a.urgency > b.urgency;  // the first key decides if it differs
        }
        return a.city < b.city;  // only a tie reaches the second key
    });
    return queue[0].city == "Oslo" && queue[1].city == "Bergen"
           && queue[2].city == "Cairo" ? 0 : 1;
}

Cairo and Bergen have equal urgency. Without the last line of the lambda they would be equivalent, and std::sort does not promise to keep equivalent elements in their original order. If arrival order is the tie policy, either store an arrival number and compare it as the second key, or use std::stable_sort, whose contract is that equivalent elements keep their relative order. A secondary key is not cosmetic: it can be what makes repeated runs produce the promised result.

For n elements, std::sort makes O(n log n) comparisons in the worst case. std::stable_sort makes O(n log n) comparisons when it can allocate a temporary buffer and O(n log² n) when it cannot. These bounds count comparator calls. Comparing or moving one element can cost more than constant time, so take the comparator's arguments by reference and compare keys rather than copying whole records.

Trace a destination order

The figure shows the input and the required result of the program above, not an internal trace of a particular sorting implementation. A sort may compare the same pair more than once and may pass through many intermediate arrangements. Tests should inspect the ordering property and the tie policy rather than assert one undocumented comparison sequence.

The ordering invariant

Why can we delegate sorting? The library guarantees that the result is a permutation of the input in which no element precedes an earlier one under the comparator, provided the comparator is a strict weak ordering. That part is the library's proof. The application's part is to show that its comparator is one and that it expresses the intended policy.

For the two-key policy the argument is short. A parcel never precedes itself: its urgency equals its own, and its city is not less than itself. If a precedes b, either a is more urgent, so b cannot precede a on urgency, or the urgencies tie and a's city is smaller, so b's is not. Transitivity follows the same two cases. Two parcels are equivalent only when both keys are equal, so if the two keys together identify a parcel there is exactly one valid output.

Comparator state may record a measurement but must not change the answer. Incrementing a comparison count does not change which parcel precedes another. Reading a threshold that changes during the sort would: the same pair could be compared under two policies, and consistency is gone. Keep the policy fixed for the whole call.

Captures are another lifetime contract

A capture [limit] stores a copy of limit inside the lambda object, taken when the lambda is created. A capture [&checks] stores a reference to the original. Changing the original afterward is seen through the reference capture and not through the copy. This is module 3's copy-versus-reference distinction inside a callable object.

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> weights{4, 9, 3, 8, 12};
    int limit = 8;
    int checks = 0;
    auto is_heavy = [limit, &checks](int kg) {
        checks += 1;         // counts into main's variable
        return kg >= limit;  // the limit as it was at creation
    };
    limit = 100;  // too late: the lambda holds its own copy, still 8
    auto heavy = std::count_if(weights.begin(), weights.end(), is_heavy);
    return heavy == 3 && checks == 5 ? 0 : 1;
}

A lambda cannot modify a by-value capture at all unless it is declared mutable, and then it modifies its own copy. An algorithm is also allowed to copy the function object it is given. A mutable by-value counter is therefore not a shared counter: after the call, the caller's variable is unchanged. To count comparator or predicate calls, capture the counter by reference.

A reference capture is safe only while the referenced object lives. A lambda returned from a function must not hold references to that function's local variables, which are gone when it returns. A lambda used immediately by an algorithm, as above, can borrow a local counter that outlives the call. The lifetime analysis depends on where the callable goes, not on how short its syntax looks.

Capturing everything with [&] can conceal dependencies. Prefer explicit captures when they make the policy clearer: copy the fixed threshold, borrow only the counter.

Search requires the right arrangement

std::lower_bound returns the first position whose element is not less than the target. Its range must be partitioned for that target: every element less than the target comes before every element that is not. A fully sorted range is the usual way to satisfy that for every target. Calling it on unsorted values compiles and returns some iterator, but the result means nothing.

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> codes{1204, 1377, 1377, 1502, 1990};  // sorted
    auto at = std::lower_bound(codes.begin(), codes.end(), 1400);
    bool is_end = at == codes.end();
    bool found = !is_end && *at == 1400;  // test for the end before reading
    auto past = std::lower_bound(codes.begin(), codes.end(), 2500);
    return !found && *at == 1502 && at - codes.begin() == 3
           && past == codes.end() ? 0 : 1;
}

The search for 1400 returns a valid position holding 1502. That is where 1400 would be inserted, not evidence that 1400 is present. The search for 2500 returns the end iterator, which must not be read. Before reading a result, test for the end; before claiming an exact match, compare the found element with the target.

For a range of n elements std::lower_bound makes at most about log₂ n + 1 comparisons, whatever the iterator type. The number of iterator steps is another matter. With random-access iterators (a vector) each jump is constant time. With bidirectional iterators (a map, a set, a list) the algorithm has to walk, so it takes a number of steps linear in n. For an ordered map or set, use the member function lower_bound instead: it is guaranteed logarithmic in the container's size because it uses the container's internal structure, which in practice is a balanced tree.

Measure the workload honestly

A full scan performs one check per element. A halving search performs a logarithmic number of comparisons. A sort performs on the order of n log n. The block below counts comparisons at three sizes. Both algorithms are stand-ins, not the C++ library: the search is Python's bisect_left, which answers the same question as std::lower_bound, and the sort is a merge sort written out so that every comparison is visible. std::sort is a different algorithm with the same worst-case order of growth.

import bisect
import math

class Code:
    """A tracking code that counts every `<` asked of it."""
    comparisons = 0

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        Code.comparisons += 1
        return self.value < other.value

def merge_sort(items):
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left, right = merge_sort(items[:mid]), merge_sort(items[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if right[j] < left[i]:
            out.append(right[j])
            j += 1
        else:
            out.append(left[i])
            i += 1
    return out + left[i:] + right[j:]

measured = {}
for n in (1000, 4000, 16000):
    scrambled = [Code((i * 7919 + 13) % n) for i in range(n)]  # n distinct codes
    Code.comparisons = 0
    in_order = merge_sort(scrambled)
    sort_count = Code.comparisons
    assert [code.value for code in in_order] == list(range(n))
    worst_search = 0
    for target in range(-1, n + 1):
        Code.comparisons = 0
        bisect.bisect_left(in_order, Code(target))
        worst_search = max(worst_search, Code.comparisons)
    assert worst_search == math.floor(math.log2(n)) + 1
    measured[n] = (worst_search, sort_count, round(sort_count / (n * math.log2(n)), 2))

assert measured[1000] == (10, 8413, 0.84)
assert measured[4000] == (12, 38578, 0.81)
assert measured[16000] == (14, 196866, 0.88)

# The numbers in the lesson's C++ examples and its figure.
weights = [4, 9, 3, 8]
assert sum(w >= 8 for w in weights) == 2 and sum(weights) == 24
assert sum(kg >= 8 for kg in [4, 9, 3, 8, 12]) == 3
kg_to = {}
for city, kg in [("Oslo", 4), ("Lima", 9), ("Oslo", 3), ("Cairo", 8), ("Lima", 1)]:
    kg_to[city] = kg_to.get(city, 0) + kg
assert sorted(kg_to.items()) == [("Cairo", 8), ("Lima", 10), ("Oslo", 7)]
queue = [("Cairo", 4), ("Oslo", 7), ("Bergen", 4), ("Lima", 2)]
ordered = sorted(queue, key=lambda parcel: (-parcel[1], parcel[0]))
assert [c[0] + ":" + str(u) for c, u in ordered] == ["O:7", "B:4", "C:4", "L:2"]
assert bisect.bisect_left([1204, 1377, 1377, 1502, 1990], 1400) == 3

Scan and Search are worst-case comparisons to find one code; Sort is the comparisons this merge sort made; the ratio divides that by n log₂ n. Sixteen times the data costs the scan sixteen times the comparisons and the search four more. The ratio stays near one constant, which is what n log n growth looks like. These are counts for this merge sort on these inputs, not a statement about std::sort's constant. Hash lookups are absent from the table on purpose: their average depends on the hash function and the keys, so one number would mislead.

Do not judge a container choice by wall-clock differences between tiny examples. Browser scheduling, compiler loading and allocation noise dominate. Count the operation the claim is about.

A problem that looks different

A clinic's waiting-room screen shows who is called next: the higher triage level first, and among equal levels whoever took a ticket earlier. A nurse can raise a waiting patient's level at any moment. Which part of this is a comparator, and what makes it strict? Which key guarantees that no two patients are equivalent? What goes wrong if a level changes while a sort is running, and where would you apply the change instead?

Practise

The lab chooses a counting representation, completes a two-key comparator and repairs a capture, writes the halving search that std::lower_bound performs and replays it frame by frame, and assembles a top-k result with a declared tie policy. The final challenge changes the story, so you must work out which operations matter before choosing containers and algorithms; its checks count the work your choice does.

Recap

You can now: choose containers by the operations a program asks for, use iterator ranges, predicates and captures, and defend an ordering's tie policy and a search's preconditions.

Invariant: output follows its declared relation, with explicit equivalence and tie behavior.

Complexity achieved: a scan is linear. std::sort makes O(n log n) comparisons in the worst case. std::lower_bound makes O(log n) comparisons but needs random-access iterators for logarithmic time. Ordered lookup is logarithmic; hashed lookup is constant on average and linear in the worst case. All of these count key operations, which are not constant for long keys.

Failure mode: unordered traversal becomes accidental product order, a comparator that is not a strict weak ordering makes std::sort undefined, or a copied capture hides the real counter.

In real software: the C++ standard fixes what std::sort returns and how many comparisons it may make, not which algorithm it runs. Code that depends on where equivalent elements land depends on one library's implementation, not on the language.

Retrieval: from module 9: why can push_back invalidate a reference to v[0], and what did the vector do to make that happen?

Check yourself

1. Why does a container's iteration order belong in a program's specification?
2. What changes when lower_bound receives bidirectional rather than random-access iterators?
3. A comparator uses < on every key. What else must you show before handing it to std::sort?

Original SciMigo course material. C++ examples target C++17.