C++ STL Algorithms: Sort, Search, Transform and Clean Data in One Pipeline

You can write five separate loops for a data-cleaning task, but then you must maintain every ordering assumption, iterator boundary and cleanup step yourself. A composed STL pipeline exposes those contracts during sorting, threshold search, calibration, noise removal and summation. The cleaned readings will be {11, 20, 20, 27, 34, 45, 45}, with total 202 and average about 28.86. The goal is not shorter code for its own sake, but correct composition with explicit preconditions.

Related reading: STL containers and iterators and sorting complexity.

C++ STL algorithms work on ranges, preconditions and returned positions

Most STL algorithms receive a half-open range [first, last), including first but excluding last. std::sort, std::lower_bound, std::transform and std::remove_if come from <algorithm>. std::accumulate comes from <numeric>. A std::vector<int> has random-access iterators, fitting sorting and fast binary searching. If vectors, iterators or lambdas are unfamiliar, begin with the C++ Tutorial.

The calls retain their contracts. Ascending order satisfies the search precondition, remove_if does not resize a vector, and the accumulate initial value controls its accumulator type.

C++ STL data-cleaning task: nine readings and five exact operations

Start with this input:

std::vector<int> readings{42, -5, 17, 42, 8, 31, -2, 17, 24};

The task has five ordered steps: sort ascending, find the first uncalibrated reading at least 20, add a calibration offset of 3 to every element, remove calibrated values below 10, then sum the retained values and compute their mean.

That sequence is observable. The threshold query describes the original readings, while the cleanup rule applies to calibrated readings. We must save the found index and value before mutation, and never carry its iterator through compaction and erasure. Duplicates stay because neither the requirement nor these algorithms asks for deduplication.

std::sort and std::lower_bound: establish order before binary search

Sorting produces an exact ascending range:

std::sort(readings.begin(), readings.end());
// {-5, -2, 8, 17, 17, 24, 31, 42, 42}

auto first20 = std::lower_bound(readings.begin(), readings.end(), 20);

first20 points to 24 at zero-based index 5. Both 17s are below the key, so 24 is the first value not less than 20. Extract it only after checking:

if (first20 != readings.end()) {
    auto index = std::distance(readings.begin(), first20);
    int value = *first20;
}

A threshold above 42 returns readings.end(), which cannot be dereferenced. Sorting costs O(n log n) and vector search takes O(log n), so the phase is O(n log n). Sorting dominates the pipeline, but its exact comparison count depends on the implementation. Algorithms Header in C++: Sort, Search and Transform with Runnable Examples is the earlier canonical first pass across binary search, bounds, inspection algorithms and erase-remove. The nine-reading pipeline instead composes five dependent calls while preserving saved values, accumulator types and invariants at each boundary.

std::transform and the erase-remove idiom: mutate, compact, then shrink

Apply the calibration in place:

std::transform(readings.begin(), readings.end(), readings.begin(),
               [](int x) { return x + 3; });
// {-2, 1, 11, 20, 20, 27, 34, 45, 45}

Adding the same constant is monotonic, so ascending order survives. A non-monotonic transform, such as absolute value, could break the order and require another sort before binary search.

Removal has two distinct steps:

auto newEnd = std::remove_if(readings.begin(), readings.end(),
                             [](int x) { return x < 10; });
readings.erase(newEnd, readings.end());

After remove_if, the retained prefix is {11, 20, 20, 27, 34, 45, 45} and newEnd is at index 7. The two valid tail slots contain unspecified values and are not data. erase reduces the physical size from nine to seven.

transform invokes its lambda nine times and remove_if tests nine values. Compaction plus vector erasure remains linear. In C++20, std::erase_if(readings, predicate) expresses the same result concisely.

std::accumulate: choose the accumulator type and verify the arithmetic

Use a wide initial value when the sum may exceed the range of int:

long long total = std::accumulate(readings.begin(), readings.end(), 0LL);

The arithmetic is 11 + 20 + 20 + 27 + 34 + 45 + 45 = 202. Therefore, average = static_cast<double>(total) / readings.size() = 202 / 7 = 28.857142..., displayed as about 28.86. If cleaning might produce an empty vector, guard the division with readings.empty().

The initial value is also a type decision. Starting with 0 makes the running result an int; starting with 0LL makes it long long. The fold performs seven additions after cleaning and costs O(n).

C++ STL pipeline and the invariants between calls

The pipeline is:

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>

int main() {
    std::vector<int> readings{42, -5, 17, 42, 8, 31, -2, 17, 24};

    std::sort(readings.begin(), readings.end());
    auto first20 = std::lower_bound(readings.begin(), readings.end(), 20);
    if (first20 != readings.end()) {
        auto index = std::distance(readings.begin(), first20);
        int value = *first20;
        std::cout << "index " << index << ", value " << value << '\n';
    }

    std::transform(readings.begin(), readings.end(), readings.begin(),
                   [](int x) { return x + 3; });
    auto newEnd = std::remove_if(readings.begin(), readings.end(),
                                 [](int x) { return x < 10; });
    readings.erase(newEnd, readings.end());

    long long total = std::accumulate(readings.begin(), readings.end(), 0LL);
    double average = readings.empty() ? 0.0
                                      : static_cast<double>(total) / readings.size();

    for (int x : readings) std::cout << x << ' ';
    std::cout << "\ntotal " << total << ", average "
              << std::fixed << std::setprecision(2) << average << '\n';
}

Its output includes index 5, value 24, the seven final readings, total 202 and average 28.86. Three invariants make the composition correct: the range is sorted before lower_bound; adding 3 preserves ascending order; and the threshold iterator is not reused after remove_if or erase. Overall time is O(n log n), dominated by sorting. Every later pass is linear except the logarithmic search.

C++ STL algorithm traps in tests and interviews

Tests often ask for the iterator offset and dominant complexity before asking for code. In this trace, lower_bound(20) returns offset 5, and sorting dominates at O(n log n). Interviews add contract questions: std::sort is not stable, so equal-key records that must preserve relative order require std::stable_sort. For placement-style C++ and algorithm practice, continue with Coding For Placements.

C++ STL algorithms and the next step

Use the same sequence every time: establish the precondition, call the algorithm on an explicit range, inspect its returned iterator, and update the container only when required. Now retry with threshold 30 and calibration +5. Before calibration, lower_bound(30) finds 31 at index 6. After calibration and removal below 10, the vector is {13, 22, 22, 29, 36, 47, 47}, totalling 216.

Use C++ Programming for a structured language route, or browse Coding & DSA for the broader catalogue. If you need only this concept, first reproduce both traces without looking.