Algorithms and adapters: prove the ranges first, then compose operations

Output adapters change the meaning of the operation

After reading the insert-iterator source, first ask where assignment actually writes. An ordinary vector iterator denotes the position of an existing element; assigning to it does not increase size. back_inserter holds an access relationship to the container and interprets assignment as appending an element. The algorithm is responsible for when to output; the container is responsible for storing the new object; the two duties can therefore be composed.

This example generates new records that own their data from read-only original records. The output container starts empty, so use back_inserter rather than treating begin as ready-made space. Even reserving in advance does not change this conclusion. The conversion copies the name because the result needs to own it independently; one must not return a reference to a short-lived working object just to avoid a copy.

Both sorting and reverse traversal have precise bounds

The comparator orders first by score descending, then by name ascending, so ties are reproducible. When both fields are equal, the comparator must return false; using greater-than-or-equal would break strict weak ordering. The standard constrains the relation among elements; it does not require that comparing any adjacent pair return true, nor does it guarantee an unspecified tie order.

A reverse iterator stores a forward bound and, when dereferenced, accesses the preceding element. Thus rbegin().base() equals end(), but rbegin and end do not denote the same dereferenceable object. The example asserts the last element and the bound relationship, but never reads end or rend; dangerous runtime results that appear in the book cannot be transplanted as a normal example.

Composed calls do not mean automatic write-back

for_each invokes a callable but does not automatically write the function’s return value back into the element. Choose transform when output must be generated; when explicit side effects are needed, let the callback take a writable reference. This example first transforms records, then uses mem_fn to call a read-only member of each record and collect results, keeping mutation and observation separate.

mem_fn is one modern replacement for the old mem_fun family and can handle different forms of object access; a lambda is usually more straightforward. C++17 invoke unifies member-pointer invocation rules, and C++20 ranges algorithms adopt the corresponding call semantics. Classic for_each still cannot treat a raw member-function pointer as an ordinary function call; when adapting the expression one must still check arity, const, and object lifetime.

Pitfalls

• reserve does not create elements; begin of an empty vector cannot serve as the direct output range of a non-empty transform.
• A reverse iterator’s base is the forward bound, not the same element; end/rend are not dereferenceable.
• A sort comparator must not use >= in place of >; equivalent elements must yield false in both directions.

Minimum C++17 · complete program · Download .cpp

#include <algorithm>
#include <cassert>
#include <functional>
#include <iterator>
#include <string>
#include <vector>

struct Record {
    std::string name;
    int score;
    int points() const { return score; }
};

int main() {
    const std::vector<Record> input{{"Bea", 4}, {"Ari", 4}, {"Cy", 2}};
    std::vector<Record> ranked;
    std::transform(input.begin(), input.end(), std::back_inserter(ranked),
        [](const Record& r) { return Record{r.name, r.score + 1}; });
    const auto before = [](const Record& a, const Record& b) {
        if (a.score != b.score) return a.score > b.score;
        return a.name < b.name;
    };
    std::sort(ranked.begin(), ranked.end(), before);
    assert(ranked[0].name == "Ari" && ranked[1].name == "Bea");
    assert(!before(ranked[0], ranked[0]));
    assert(input[0].score == 4 && ranked[0].score == 5);

    auto last = ranked.rbegin();
    assert(last.base() == ranked.end());
    assert(last->name == "Cy");

    std::vector<int> scores;
    const auto points = std::mem_fn(&Record::points);
    std::for_each(ranked.begin(), ranked.end(),
        [&](const Record& r) { scores.push_back(points(r)); });
    assert((scores == std::vector<int>{5, 5, 3}));
    const auto found = std::find_if(ranked.begin(), ranked.end(),
        [](const Record& r) { return r.name == "Bea"; });
    assert(found != ranked.end());
    assert(std::invoke(&Record::points, *found) == 5);
}

Compile locally

g++ -std=c++17 -Wall -Wextra -Wpedantic -pthread books-stl-source-analysis.cpp -o example && ./example

Expected result

Expected: exit 0, no output; every assert holds.

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

Change scores so it is generated in the reverse order of ranked, without introducing any new container. Write the complete replacement statements and give the assertion; is it necessary to shrink rend?

Check the sources

• C++ draft: back_insert_iterator
• C++ draft: reverse_iterator
• C++ draft: sorting and strict weak ordering
• C++ draft: for_each

Drafts and official chapters change. The version mark is only the example’s minimum.