C++ Algorithm | "STL algorithm" Core Summary

STL <algorithm> provides sorting, searching, transformation, aggregation, etc., for iterator ranges. Better readability than manual loops and verified implementation worth considering first in practice. This guide organizes frequently used algorithms, common mistakes in practice, and selection tips.

Sorting

std::sort is ascending by default, and can change sorting criteria with comparator. Partial sort (sort only top k) uses partial_sort, maintain order of same values uses stable_sort.

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

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
    
    // Ascending
    sort(v.begin(), v.end());
    
    // Descending
    sort(v.begin(), v.end(), greater<int>());
    
    // Partial sort
    partial_sort(v.begin(), v.begin() + 3, v.end());
    
    // Stable sort
    stable_sort(v.begin(), v.end());
}

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);

Transformation

transform transforms elements of one range (or two ranges) with function/lambda and writes to result range. Space for result must be secured beforehand or use back_inserter. Range sizes must match, so output container should be matched with resize or reserve+back_inserter.

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
    }
}

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;

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
}

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 << " ";  // 2 4 6 8 10
}
cout << endl;

cout << "Odd: ";
for (auto it = pivot; it != v.end(); ++it) {
    cout << *it << " ";  // 1 3 5 7 9
}

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));

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());

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());

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);

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; });

Practical Tips

• 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: Mostly similar or faster. Inlining and optimization work well, so good to use algorithms for readability. Consider manual loops only after profiling when bottleneck.

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++ Algorithm Permutation | “Permutation Algorithm” Guide
• C++ Algorithm Count | “Count Algorithm” Guide
• C++ Range-based for | “Range-based for” Guide
• C++ STL Algorithm Basics Complete Guide | sort, find
• C++ Algorithm Partition
• C++ Algorithm Sort
• C++ Algorithm Copy

---

Practical Tips

Tips you can apply immediately in practice.

Debugging Tips

• Check compiler warnings first when problems occur
• Reproduce problem with simple test cases

Performance Tips

• Don’t optimize without profiling
• Set measurable metrics first

Code Review Tips

• Pre-check frequently pointed out parts in code reviews
• Follow team coding conventions

---

Practical Checklist

Items to check when applying this concept in practice.

Before Writing Code

• Is this technique the best way to solve current problem?
• Can team members understand and maintain this code?
• Does it meet performance requirements?

While Writing Code

• Resolved all compiler warnings?
• Considered edge cases?
• Is error handling appropriate?

During Code Review

• Is code intent clear?
• Are test cases sufficient?
• Is it documented?

Use this checklist to reduce mistakes and improve code quality.

---

Keywords

C++, Algorithm, STL, sort, find, transform, accumulate, binary_search, remove_if, unique, partition

---

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