C++ STL Algorithms: sort, find, transform, and the Mistakes That Give Wrong Results

STL <algorithm> (plus <numeric> for accumulate and friends) provides sorting, searching, transformation and aggregation over iterator ranges. The algorithms do not know which container they operate on; they only see a pair of iterators [first, last). That design is why one std::sort works for vector, deque and plain arrays, and also why the algorithms cannot change a container’s size, a fact behind several of the mistakes below. This guide covers the frequently used algorithms, the mistakes that produce wrong results, and how to choose between similar functions.

Sorting

std::sort is ascending by default and takes a comparator to change the order. It is guaranteed O(n log n) comparisons since C++11 and is not stable; stable_sort keeps equal elements in their original order, partial_sort sorts only the first k, and nth_element finds the k-th element in O(n) on average.

#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
    sort(v.begin(), v.end());                          // ascending
    sort(v.begin(), v.end(), greater<int>());          // descending
    partial_sort(v.begin(), v.begin() + 3, v.end());   // smallest 3 at the front, sorted
    stable_sort(v.begin(), v.end());                   // equal elements keep their order
}

The one rule that causes real bugs is that the comparator must be a strict weak ordering: comp(a, a) must be false, so write <, never <=. With <=, std::sort can read past the end of the range on inputs with many equal elements, which shows up as a crash only on some data. When a sort crashes on production data but never in tests, that comparator is the first thing I check. How the four sorting functions differ (introsort vs merge sort, stability, the cost of a partial sort, choosing a median with nth_element) is covered with examples in C++ Sorting: std::sort, stable_sort, partial_sort and nth_element.

Searching

Linear search with find / find_if is O(n) suitable for finding once, and when finding multiple times, sort range first then O(log n) search with binary_search / lower_bound is possible. Be careful using binary_search on unsorted range gives wrong results.

vector<int> v = {1, 2, 3, 4, 5};

// find
auto it = find(v.begin(), v.end(), 3);
if (it != v.end()) {
    cout << "Found: " << *it << endl;
}

// find_if
auto it2 = find_if(v.begin(), v.end(), [](int x) { return x > 3; });

// binary_search (when sorted)
sort(v.begin(), v.end());
bool found = binary_search(v.begin(), v.end(), 3);

binary_search only answers yes or no, which is rarely enough. lower_bound returns an iterator to the first element that is not less than the value, so it tells you both whether the value exists (it != v.end() && *it == value) and where to insert it to keep the range sorted. equal_range returns the whole run of equal elements. For associative containers such as std::set and std::map, use their member find and lower_bound: the free functions work on them too, but set and map iterators are not random-access, so the free lower_bound degrades to linear time.

transform applies a function or lambda to each element of one range (or pairs of elements from two ranges) and writes the results to an output iterator. The algorithm does not grow the output: it assumes there is already room. Either size the destination first (vector<int> result(v.size());, as below) or pass back_inserter(result), which calls push_back for each write. Combining reserve with back_inserter avoids repeated reallocations. Writing to result.begin() of an empty vector is undefined behavior, and it is one of the most common algorithm bugs because it compiles cleanly.

vector<int> v = {1, 2, 3, 4, 5};
vector<int> result(v.size());

// transform
transform(v.begin(), v.end(), result.begin(), [](int x) {
    return x * x;
});

for (int x : result) {
    cout << x << " ";  // 1 4 9 16 25
}

Practical Examples

Example 1: Data Processing Pipeline

struct Person {
    string name;
    int age;
    double salary;
};

int main() {
    vector<Person> people = {
        {"Alice", 25, 50000},
        {"Bob", 30, 60000},
        {"Charlie", 35, 70000},
        {"David", 28, 55000}
    };
    
    // Filter age >= 30
    vector<Person> filtered;
    copy_if(people.begin(), people.end(), back_inserter(filtered),
            [](const Person& p) { return p.age >= 30; });
    
    // Sort by salary
    sort(filtered.begin(), filtered.end(),
         [](const Person& a, const Person& b) { return a.salary > b.salary; });
    
    // Extract names
    vector<string> names;
    transform(filtered.begin(), filtered.end(), back_inserter(names),
              [](const Person& p) { return p.name; });
    
    for (const auto& name : names) {
        cout << name << endl;  // Charlie, Bob
    }
}

Each step makes a new container, which is easy to read but copies every surviving Person. For large data you can sort a vector of indices or pointers instead, or in C++20 use ranges: people | views::filter(...) | views::transform(...) evaluates lazily without intermediate vectors (though you still need a real container to sort). Note that the comparator here uses > on salary for descending order; that is still a valid strict weak ordering, unlike >=.

Example 2: Statistics Calculation

vector<int> scores = {85, 92, 78, 95, 88, 76, 90};

// Sum
int sum = accumulate(scores.begin(), scores.end(), 0);

// Average
double avg = sum / (double)scores.size();

// Max/Min
auto [minIt, maxIt] = minmax_element(scores.begin(), scores.end());

cout << "Sum: " << sum << endl;
cout << "Average: " << avg << endl;
cout << "Min: " << *minIt << endl;
cout << "Max: " << *maxIt << endl;

// Median
sort(scores.begin(), scores.end());
double median = scores[scores.size() / 2];
cout << "Median: " << median << endl;

accumulate lives in <numeric>, not <algorithm>, and a missing include is a common compile error here. Its result type is the type of the initial value, so accumulate(v.begin(), v.end(), 0) sums in int even for a vector<double>, truncating each partial sum. The median line is correct only for an odd number of elements; for an even count you would average scores[n/2 - 1] and scores[n/2]. And a full sort is more than a median needs: nth_element(scores.begin(), scores.begin() + n/2, scores.end()) places the middle element correctly in linear average time.

Example 3: Remove Duplicates

vector<int> v = {1, 2, 2, 3, 3, 3, 4, 5, 5};

// Sort (unique requires sorting)
sort(v.begin(), v.end());

// Remove duplicates
auto last = unique(v.begin(), v.end());

// Actually delete
v.erase(last, v.end());

for (int x : v) {
    cout << x << " ";  // 1 2 3 4 5
}

unique only collapses adjacent duplicates, which is why sorting comes first. Like remove, it cannot shrink the vector; it moves the kept elements forward and returns the new logical end, and the elements after it have unspecified values. If you need to keep the original order and still drop duplicates, sorting will not do; a std::unordered_set of seen values is the usual approach.

Example 4: Partition

vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

// Separate even/odd
auto pivot = partition(v.begin(), v.end(), [](int x) {
    return x % 2 == 0;
});

cout << "Even: ";
for (auto it = v.begin(); it != pivot; ++it) {
    cout << *it << " ";  // the even numbers, in unspecified order
}
cout << endl;

cout << "Odd: ";
for (auto it = pivot; it != v.end(); ++it) {
    cout << *it << " ";  // the odd numbers, in unspecified order
}

partition guarantees only which side each element ends up on, not the order within each side; with libstdc++ this input typically prints the evens as 10 2 8 4 6. Use stable_partition if the original relative order must survive. The returned iterator is the boundary, and partition_point can find it again later on an already-partitioned range.

Set Operations

For two sorted ranges, use set_union, set_intersection, set_difference for union, intersection, and difference. Input ranges must be sorted for correct results. Pass container for results with back_inserter(result).

vector<int> a = {1, 2, 3, 4, 5};
vector<int> b = {3, 4, 5, 6, 7};
vector<int> result;

// Union
set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));

// Intersection
result.clear();
set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));

// Difference
result.clear();
set_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));

Results: union 1 2 3 4 5 6 7, intersection 3 4 5, difference 1 2. These functions walk both ranges once, like the merge step of merge sort, so they are O(n + m). That speed is exactly why they require sorted input: on unsorted data they do not fail, they quietly return wrong answers. If your data is unsorted and you only need an intersection once, putting one side into an unordered_set may be simpler than sorting both.

Modifying Algorithms

When changing range in-place, use fill, generate, replace, reverse, rotate, etc. remove/remove_if do not delete elements but only gather “elements to keep” to front, so must use with erase to reduce logical size (erase-remove idiom).

vector<int> v = {1, 2, 3, 4, 5};

// fill
fill(v.begin(), v.end(), 0);

// generate
generate(v.begin(), v.end(), []() {
    static int n = 0;
    return n++;
});

// replace
replace(v.begin(), v.end(), 3, 99);

// reverse
reverse(v.begin(), v.end());

// rotate
rotate(v.begin(), v.begin() + 2, v.end());

The generate lambda uses a static counter, which is a shortcut for the example: the counter is shared by every call of that lambda for the rest of the program, so running the code twice continues from 5. std::iota(v.begin(), v.end(), 0) from <numeric> does the same job without hidden state. rotate(first, middle, last) makes middle the new first element; here {4, 99, 2, 1, 0} becomes {2, 1, 0, 4, 99}.

Common Problems

Problem 1: Erase-Remove Idiom

// ❌ Using only remove
vector<int> v = {1, 2, 3, 2, 4, 2, 5};
remove(v.begin(), v.end(), 2);  // Size does not decrease!

// ✅ Erase-remove
v.erase(remove(v.begin(), v.end(), 2), v.end());

After the bare remove, v still has 7 elements: the first four are 1 3 4 5 and the last three are leftovers with unspecified values. Because ignoring the return value is almost always a bug, MSVC and libc++ mark remove as [[nodiscard]] and warn about it. Since C++20 you can write std::erase(v, 2); or std::erase_if(v, pred);, which do both steps and return the number of removed elements.

Problem 2: Binary Search on Unsorted

// ❌ Not sorted
vector<int> v = {3, 1, 4, 1, 5};
bool found = binary_search(v.begin(), v.end(), 3);  // Wrong result

// ✅ After sorting
sort(v.begin(), v.end());
found = binary_search(v.begin(), v.end(), 3);

On unsorted input the result is not an error but whatever the halving happens to hit, so the same code can return the right answer for some values and the wrong one for others. The same applies when you sort with one comparator and search with another, for example sorting descending with greater<int>() and then calling binary_search without it; pass the same comparator to both.

Problem 3: Range Error

// ❌ Range overflow
vector<int> v(5);
transform(v.begin(), v.end(), v.begin() + 10, [](int x) { return x * 2; });

// ✅ Correct range
vector<int> result(v.size());
transform(v.begin(), v.end(), result.begin(), [](int x) { return x * 2; });

v.begin() + 10 is already past the end of a 5-element vector, so the output writes land in memory the vector does not own. Nothing checks this in a release build. Building with -D_GLIBCXX_DEBUG (libstdc++) or MSVC’s debug iterators turns many of these into an immediate assertion, and AddressSanitizer reports them as heap-buffer-overflow. Transforming in place (transform(v.begin(), v.end(), v.begin(), ...)) is allowed and needs no extra space.

Rules of Thumb

• erase-remove: To delete elements matching condition, don’t use only remove_if, use erase-remove idiom v.erase(remove_if(...), v.end()). remove does not change size.
• binary_search family: Use binary_search, lower_bound, upper_bound only on sorted ranges. Unsorted gives wrong results.
• accumulate initial value: When summing double, use 0.0 not 0. 0 is int so precision may drop at each step.
• Search once vs multiple times: When finding once, find (O(n)) may be better than sort (O(n log n)) + binary_search. Consider binary search after sorting only when finding multiple times.
• Set operations: set_union, set_intersection, set_difference assume input is sorted. Unsorted gives wrong results.

FAQ

Q1: Why use STL algorithms?

A: Verified implementation reduces bugs, can receive compiler/library optimizations, and good readability showing “intent”. Easier maintenance and reuse than manual loops.

Q2: How is performance vs manual loops?

A: Usually the same. Algorithms are templates, so with optimization enabled the lambda is inlined and the generated code matches a hand-written loop. Some algorithms can be faster because the library specializes them, for example copy or fill on trivially copyable types becoming a memmove/memset. In unoptimized debug builds algorithms can be noticeably slower because of the extra function layers, which is worth knowing before you benchmark a debug build.

Q3: Which algorithms to learn first?

A: Starting with sort, find/find_if, transform, accumulate naturally expands to copy_if, remove_if+erase, binary_search/lower_bound. Also helpful to see next_permutation in Permutation Algorithm.

Q4: Lambda vs function object, when to use which?

A: Simple condition/transformation used in one place is easier to read with lambda. For reuse in multiple places or when state is needed, use function object (or std::function).

Q5: How to find needed algorithm?

A: Search cppreference.com - algorithm for “sort”, “search”, “transform”, etc., or include <algorithm> in IDE and autocomplete with std:: to choose by purpose.

---

Related Posts

• C++ next_permutation and prev_permutation: All Permutations, Duplicates and Combinations
• C++ count, count_if, all_of, any_of and none_of: Counting and Checking Conditions
• C++ Range-Based for: auto, References, and Temporaries
• C++ Algorithm Partition
• C++ Algorithm Sort
• C++ Algorithm Copy

---

Quick Reference

// Sorting
sort(v.begin(), v.end());                    // Ascending
sort(v.begin(), v.end(), greater<int>());    // Descending
stable_sort(v.begin(), v.end());             // Stable sort

// Searching
find(v.begin(), v.end(), value);             // Linear search
binary_search(v.begin(), v.end(), value);    // Binary search (sorted)
lower_bound(v.begin(), v.end(), value);      // First >= value
upper_bound(v.begin(), v.end(), value);      // First > value

// Transformation
transform(v.begin(), v.end(), out, func);    // Apply function
copy_if(v.begin(), v.end(), out, pred);      // Copy if predicate

// Aggregation
accumulate(v.begin(), v.end(), 0);           // Sum
count(v.begin(), v.end(), value);            // Count value
count_if(v.begin(), v.end(), pred);          // Count if predicate

// Modification
fill(v.begin(), v.end(), value);             // Fill with value
reverse(v.begin(), v.end());                 // Reverse
unique(v.begin(), v.end());                  // Remove consecutive duplicates
v.erase(remove(v.begin(), v.end(), val), v.end());  // Erase-remove idiom

// Min/Max
min_element(v.begin(), v.end());             // Iterator to min
max_element(v.begin(), v.end());             // Iterator to max
minmax_element(v.begin(), v.end());          // Pair of min/max iterators

---