STL Algorithms, Containers and Complexity

The Standard Template Library, usually shortened to STL, is the container, iterator and algorithm style within the C++ standard library. A container owns elements. An iterator identifies a position in a sequence. An algorithm performs a reusable operation over positions or, with C++20 ranges overloads, a range directly.

Think in operations before choosing a container. Do you mostly append and scan? Need sorted keys? Need frequent lookup without ordering? Complexity describes how work grows with input size, usually using big-O notation. O(n) means linear growth; O(log n) grows much more slowly. These are bounds on operations, not stopwatch predictions.

Pick a container for its workload

Amortized O(1) append means that occasional expensive reallocations are spread across a sequence of appends; one append can still take O(n). String comparison and hashing also cost work proportional to the examined text. A container's operation count alone is not the complete cost of long keys.

Build a deterministic frequency report

Save as algorithms.cpp:

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

int main() {
    std::istringstream input{"cpp go cpp rust go cpp"};
    std::map<std::string, int> counts;
    std::string word;
    while (input >> word) {
        ++counts[word];
    }
    std::vector<std::pair<std::string, int>> ranked(counts.begin(), counts.end());
    std::ranges::sort(ranked, [](const auto& left, const auto& right) {
        if (left.second != right.second) {
            return left.second > right.second;
        }
        return left.first < right.first;
    });
    const int minimum{2};
    const auto frequent = std::ranges::count_if(ranked, [minimum](const auto& item) {
        return item.second >= minimum;
    });
    const int total = std::accumulate(ranked.begin(), ranked.end(), 0,
        [](int sum, const auto& item) { return sum + item.second; });
    for (const auto& [name, count] : ranked) {
        std::cout << name << ": " << count << '\n';
    }
    std::cout << "Frequent: " << frequent << ", total: " << total << '\n';
}

clang++ -std=c++20 -Wall -Wextra -Wpedantic -g algorithms.cpp -o algorithms
./algorithms

The output lists cpp: 3, go: 2, rust: 1, then Frequent: 2, total: 6. Counts fit in int because this example has exactly six tokens. An unbounded file processor would need a range policy.

counts[word] inserts an absent key with a zero-initialized count before incrementing it. For read-only lookup, use find or contains; operator[] can unexpectedly mutate a map. Structured bindings give names to the two fields of each pair.

Understand algorithm contracts

A lambda is an unnamed function object. The sorting lambda captures nothing; the filtering lambda copies minimum into its closure. A reference capture would instead borrow a local variable, bringing lifetime concerns if the lambda escaped its scope.

The sort comparator defines a strict weak ordering. In particular, an element must not precede itself. Replacing > with >= breaks that requirement. The name tie-break makes equal-frequency output deterministic. sort does not preserve the input order of equivalent elements; choose stable_sort when that property matters.

Iterator algorithms generally describe a half-open range: the first position is included and the end position is excluded. Never dereference the end iterator. find and find_if return end when they find no match. lower_bound requires the range to be partitioned for its comparison; sorting with the same ordering establishes that precondition. Random-access ranges allow logarithmic iterator movement as well as logarithmic comparisons.

For n tokens and k distinct words, this report uses O(n log k) map operations, O(k log k) sorting comparisons and O(k) reporting storage, excluding text lengths. Rehashing an unordered container invalidates its iterators, though references to surviving elements remain valid. Choose an ordered map when its deterministic key ordering is itself useful.

Practice and solution guidance

1. Report only counts at least two. Guidance: use the same predicate while printing, or erase unwanted entries before sorting with C++20 std::erase_if.
2. Switch to unordered_map. Guidance: keep the final sort; do not rely on hash-table iteration order. Explain average and worst-case lookup separately.
3. Search a sorted vector for a missing key. Guidance: compare lower_bound with end before dereferencing, then check equality to distinguish an insertion position from a match.

Primary references

• WG21 C++20 draft: algorithm requirements.
• GCC standard-library algorithms overview.
• GCC standard-library containers overview.

Next: Classes, Invariants and RAII in C++.