Filtering sequences: understand algorithm rearrangement and container erasure separately

Requirements before container tricks

To remove cancelled items from a sequence of tasks, first ask whether the original input should be retained, whether the order of surviving items should be kept, and who owns the result. The book repeatedly changes the implementation through student classification, showing that the same business rule can be expressed with different containers and algorithms. The interface contract does not change, but costs and invalidation rules do.

This example reduces tasks to integers, with non-negative values as the items to keep. copy_if writes into another vector and leaves the original sequence completely untouched; in-place remove_if stably moves the kept items to the front, suitable when modifying the original sequence is allowed. Both use the same predicate meaning and do not let storage details decide the business rule.

The logical end is not the container's end

remove_if returns the end of the kept prefix. After the call, size has not yet shrunk; the trailing elements still exist, but their concrete values cannot be interpreted as a list of deleted items. A subsequent container erase then destroys the trailing elements and updates the size; this is the result of the algorithm and the container each taking half the responsibility.

The example does not inspect what happens to be left in the tail; it checks the complete sequence after erase. Empty input naturally forms an empty range; when everything is rejected the logical end equals begin. Do not first keep an iterator pointing at some business object and then assume that after rearrangement and erasure it still represents the same task: even if a position remains accessible, the value at that position may already have been swapped.

Modern shorthand does not replace understanding the contract

C++20's std::erase_if(vector, predicate) can directly express in-place filtering; the two-step formulation is retained here to show that the remove algorithm does not own the container's structure. If both groups are needed while preserving order within each group, one can copy to two destinations, or use stable_partition to obtain the boundary and then decide whether to split into two containers.

The original book is a C++98-era work; function objects and the iterator protocol still have teaching value, but old-style adapters should not be transplanted directly. Lambdas make local predicates more intuitive, and the standard copy_if is already provided; this does not mean the algorithm will check the output range for you. Writing through a raw begin into an empty destination is still invalid; the example uses back_inserter to create new elements.

Pitfalls

• remove_if does not change vector::size; omitting erase will treat the meaningless tail as valid records and continue processing them.
• copy_if writing to the begin of an empty vector is an out-of-bounds write; use back_inserter, or first create enough destination elements.

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

#include <algorithm>
#include <cassert>
#include <iterator>
#include <vector>
void discard_negative(std::vector<int>& tasks) {
    const auto end = std::remove_if(tasks.begin(), tasks.end(),
        [](int value) { return value < 0; });
    tasks.erase(end, tasks.end());
}
int main() {
    const std::vector<int> original{3, -1, 0, -2, 3};
    std::vector<int> selected;
    std::copy_if(original.begin(), original.end(), std::back_inserter(selected),
        [](int value) { return value >= 0; });
    const std::vector<int> expected{3, 0, 3};
    assert(selected == expected);
    auto modified = original;
    discard_negative(modified);
    assert(modified == expected && original[1] == -1);
    std::vector<int> empty;
    discard_negative(empty);
    assert(empty.empty());
    std::vector<int> rejected{-1, -2};
    discard_negative(rejected);
    assert(rejected.empty());
}

Compile locally

g++ -std=c++11 -Wall -Wextra -Wpedantic -pthread books-accelerated-cpp.cpp -o example && ./example

Expected result

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

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

Change it to delete even numbers, keep the original order of odd numbers, and also keep negative odd numbers.

Check the sources

• Accelerated C++：§5.3、§6.3 学生分类与删除
• std::remove / remove_if

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