C++ Algorithm | Key Summary of "STL algorithm"

STL <algorithm> provides sorting, searching, transforming, and aggregating operations on iterator ranges. It offers better readability than manual loops and is a verified implementation, making it a strong candidate for practical use. This post summarizes frequently used algorithms, common mistakes in practice, and tips for selection.

Mindset: Prefer naming what you want (sort, find_if, accumulate) over low-level index loops unless profiling proves the algorithm is hot and you need a custom pass. Pair mutating algorithms (remove, unique) with container erase when you actually shrink the sequence.

Sorting

std::sort is ascending by default, but you can change the sorting criteria by providing a comparator. For partial sorting (sorting only the top k elements), use partial_sort, and for stable sorting (preserving the order of equal elements), use stable_sort.

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

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

Searching

For linear search, use find / find_if, which are O(n) and suitable for single searches. For multiple searches, sort the range first and use binary_search or lower_bound for O(log n) searches. Be cautious not to use binary_search on unsorted ranges, as it will yield incorrect 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 applies a function/lambda to elements of one (or two) ranges and writes the result to an output range. Ensure the output range has enough space by pre-allocating it or using back_inserter. The sizes of the input and output ranges must match, so use resize or reserve + back_inserter for the output container.

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 for age >= 30
    vector<Person> filtered;
    copy_if(people.begin(), people.end(), back_inserter(filtered),
            [](const Person& p) { return p.age >= 30; });
    
    // Sort by salary in descending order
    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: Statistical Calculations

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

// Min/Max
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: Removing Duplicates

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

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

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

// Physically erase
v.erase(last, v.end());

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

Example 4: Partitioning

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

// Separate even and odd numbers
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 sorted ranges, use set_union, set_intersection, and set_difference to compute unions, intersections, and differences. The input ranges must be sorted for correct results. Use back_inserter(result) to store the results.

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

To modify ranges in place, use algorithms like fill, generate, replace, reverse, and rotate. Note that remove/remove_if only rearranges elements to “keep” the desired ones at the front and does not actually erase elements. Always pair remove with erase to reduce the 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 Issues

Issue 1: Forgetting the erase-remove idiom

// ❌ Using remove only
vector<int> v = {1, 2, 3, 2, 4, 2, 5};
remove(v.begin(), v.end(), 2);  // Size doesn't change!

// ✅ Correct: erase-remove idiom
v.erase(remove(v.begin(), v.end(), 2), v.end());

Issue 2: Using binary_search on unsorted ranges

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

// ✅ Sort first
sort(v.begin(), v.end());
found = binary_search(v.begin(), v.end(), 3);

Issue 3: Range errors

// ❌ Out-of-range
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 for Use

• Erase-remove idiom: To remove elements that meet a condition, always use v.erase(remove_if(...), v.end()). remove alone does not change the size.
• binary_search family: Use binary_search, lower_bound, and upper_bound only on sorted ranges. Results will be incorrect otherwise.
• accumulate initial value: When calculating a double sum, use 0.0 instead of 0. Using 0 (an int) can lead to precision loss.
• Single vs. multiple searches: For a single search, find (O(n)) may be faster than sorting (O(n log n)) + binary_search. Consider sorting only for multiple searches.
• Set operations: set_union, set_intersection, and set_difference assume sorted input. Results will be incorrect if the input is not sorted.

FAQ

Q1: Why use STL algorithms?

A: They reduce bugs with verified implementations, benefit from compiler/library optimizations, and improve readability by clearly expressing intent. They are easier to maintain and reuse than manual loops.

Q2: How is the performance compared to manual loops?

A: Often similar or better. They are well-optimized and inline efficiently. Use algorithms for readability, and only consider manual loops if profiling reveals performance bottlenecks.

Q3: Which algorithms should I learn first?

A: Start with sort, find/find_if, transform, and accumulate. Then expand to copy_if, remove_if + erase, and binary_search/lower_bound. Permutation algorithms (English) like next_permutation are also helpful.

Q4: When should I use lambdas vs. function objects?

A: Use lambdas for simple, one-off conditions or transformations. Use function objects (or std::function) for reusable or stateful logic.

Q5: How do I find the right algorithm?

A: Check cppreference.com - algorithm by searching for terms like “sorting,” “searching,” or “transforming.” You can also include <algorithm> in your IDE and explore std:: autocomplete suggestions.

---

Related Posts (Internal Links)

English series (deep dives): Copy · Count · Generate · Heap · Minmax · Numeric · Partition · Permutation · Interview patterns

• C++ Algorithm Permutation (English)
• C++ Algorithm Count (English)
• C++ Range-based for
• Same overview in Korean

Practical Tips

Here are some tips you can apply directly in real-world scenarios.

Debugging Tips

• Always check compiler warnings first when issues arise.
• Reproduce the problem with simple test cases.

Performance Tips

• Avoid premature optimization without profiling.
• Define measurable performance goals first.

Code Review Tips

• Ensure the code’s intent is clear.
• Verify that test cases are comprehensive.
• Make sure the code is well-documented.

---

Practical Checklist

Use this checklist to ensure you apply these concepts effectively in your projects.

Before Writing Code

• Is this approach the best solution for the current problem?
• Can your team understand and maintain this code?
• Does it meet performance requirements?

While Writing Code

• Have you resolved all compiler warnings?
• Have you considered edge cases?
• Is error handling appropriate?

During Code Review

• Is the code’s intent clear?
• Are there enough test cases?
• Is the code properly documented?

Use this checklist to minimize errors and improve code quality.

---

Keywords Covered in This Post (Related Searches)

Search for terms like C++, algorithm, STL, sort, and algorithms to find relevant content related to this post.