STL Algorithms in Depth: Captures, Reshaping and Sorted Searches

By the end you can capture variables into a lambda safely, reshape a vector with copy_if, erase-remove and unique, and binary-search sorted data. Fundamentals gave you sort, count_if and empty-bracket lambdas; here the brackets get content.

Captures

[x] captures by value: the lambda keeps a copy made when it is created. [&x] captures by reference: it names the original. An init-capture [buf = std::move(text)] builds a new variable inside the lambda.

int limit = 10;
auto copy = [limit](int v) { return v > limit; };
auto ref  = [&limit](int v) { return v > limit; };
limit = 100;
copy(50);   // true: compares against its copy, 10
ref(50);    // false: sees limit as 100

A reference capture is only safe while the variable lives; returning one is the pointer-to-a-local bug again:

auto makeTest(int limit) {
    return [&limit](int v) { return v > limit; };   // BUG: limit dies at return
}

It reads a dead stack slot; capture by value if the lambda can outlive the scope.

Reshaping data

copy_if and transform write through an output iterator. Aimed at an empty vector's begin() they write past the end; std::back_inserter(out) (<iterator>) calls out.push_back instead:

std::vector<int> temps = {18, -4, 7, 25, 7};
std::vector<int> warm;
std::copy_if(temps.begin(), temps.end(), std::back_inserter(warm),
             [](int t) { return t > 5; });          // warm: 18 7 25 7

Algorithms get iterators, not the container, so they cannot shrink it. remove_if shifts the keepers forward (by move assignment) and returns the new logical end:

std::vector<int> v = {5, 12, 8, 30, 2};
auto newEnd = std::remove_if(v.begin(), v.end(), [](int x) { return x > 10; });
// v: 5 8 2 30 2, size still 5; [newEnd, end) is leftover tail
v.erase(newEnd, v.end());                           // v: 5 8 2, size 3

erase invalidates iterators at and after the spot, as reallocation dangles pointers, so drop newEnd afterwards. std::unique drops only adjacent duplicates and needs the same erase, so sort first:

std::vector<int> d = {3, 1, 3, 3, 2, 1};
std::sort(d.begin(), d.end());                      // 1 1 2 3 3 3
d.erase(std::unique(d.begin(), d.end()), d.end());  // 1 2 3 (unsorted: 3 1 3 2 1)

std::partition moves matches to the front and returns where the rest begins, order not kept.

Ordering

std::sort may reorder equal elements; std::stable_sort keeps input order:

std::vector<std::string> w = {"pear", "fig", "plum", "apple"};
std::stable_sort(w.begin(), w.end(),
    [](const std::string& a, const std::string& b) { return a.size() < b.size(); });
// fig pear plum apple

Up to 16 elements, libstdc++'s sort is an insertion sort that happens to look stable; the bug hides until the input grows. A comparator must be a strict weak ordering: comp(a, a) is false, and comp(a, b) and comp(b, a) are never both true. <= breaks that and sort can run off the array.

Searching sorted data

lower_bound returns the first element not ordered before the value, upper_bound the first ordered after it. For {10, 20, 20, 20, 30, 40}, value 20 gives indexes 1 and 4; value 50 gives end() twice.

Pass the order the range was sorted with. For {40, 30, 20, 20, 20, 10}, lower_bound(v.begin(), v.end(), 20, std::greater<int>()) is index 2 and upper_bound is 5. Without greater the search assumes ascending order and returns 0, silently. For records the comparator takes an element and a value:

auto lo = std::lower_bound(evs.begin(), evs.end(), 5,        // sorted by day
    [](const Ev& e, int day) { return e.day < day; });       // (element, value)
auto hi = std::upper_bound(evs.begin(), evs.end(), 8,
    [](int day, const Ev& e) { return day < e.day; });       // (value, element)

hi - lo counts events on days 5 to 8. std::partition_point is the same search written as a predicate.

Common mistakes

• remove_if without erase. The tail stays: 5 8 2 30 2 instead of 5 8 2.
• sort where ties must keep input order. Ten records look fine; forty with repeated scores shuffle.
• Searching a descending range with the default <. Wrong counts, no error.
• A <= comparator: works on small inputs, crashes on large ones with equal keys.

Your exercise

Filter records with a lambda that captures a cutoff, order them highest score first with ties in input order, and count how many reach each query score. The likely mistake is searching the descending range as if it were ascending.