Algorithms

STL Algorithms

The STL provides a rich set of algorithms that work with containers. This chapter covers the most commonly used algorithms.

Algorithm Categories

┌─────────────────────────────────────────────────────────────┐
│                  STL Algorithm Categories                    │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  Non-modifying     →  for_each, find, count, equal        │
│  Modifying        →  copy, transform, replace, remove     │
│  Sorting          →  sort, stable_sort, partial_sort      │
│  Binary Search    →  lower_bound, upper_bound, equal_range│
│  Set Operations   →  set_union, set_intersection          │
│  Heap Operations  →  make_heap, push_heap, pop_heap        │
│  Numeric          →  accumulate, inner_product             │
│                                                             │
└─────────────────────────────────────────────────────────────┘

Non-Modifying Algorithms

for_each

Apply function to each element:

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    std::for_each(vec.begin(), vec.end(),
        [](int n) { std::cout << n << " "; });
    // Output: 1 2 3 4 5
}

find / find_if

Find first element matching condition:

std::vector<int> vec = {10, 20, 30, 40, 50};

// Find value
auto it = std::find(vec.begin(), vec.end(), 30);
if (it != vec.end()) {
    std::cout << "Found at position: " << (it - vec.begin());
}

// Find with condition
auto it2 = std::find_if(vec.begin(), vec.end(),
    [](int n) { return n > 25; });

count / count_if

Count elements:

std::vector<int> vec = {1, 2, 3, 2, 4, 2, 5};

int twos = std::count(vec.begin(), vec.end(), 2);  // 3
int evens = std::count_if(vec.begin(), vec.end(),
    [](int n) { return n % 2 == 0; });  // 4

Modifying Algorithms

copy

Copy elements to another range:

std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dest(5);

std::copy(src.begin(), src.end(), dest.begin());

// Copy to output stream
std::copy(src.begin(), src.end(),
    std::ostream_iterator<int>(std::cout, " "));

transform

Apply transformation:

std::vector<int> input = {1, 2, 3, 4, 5};
std::vector<int> output(input.size());

// Double each element
std::transform(input.begin(), input.end(), output.begin(),
    [](int n) { return n * 2; });
// output: {2, 4, 6, 8, 10}

remove / remove_if

Remove elements (returns new end):

std::vector<int> vec = {1, 2, 3, 4, 5, 6};

// Remove value 3
auto newEnd = std::remove(vec.begin(), vec.end(), 3);
vec.erase(newEnd, vec.end());  // {1, 2, 4, 5, 6}

// Remove even numbers
auto newEnd2 = std::remove_if(vec.begin(), vec.end(),
    [](int n) { return n % 2 == 0; });
vec.erase(newEnd2, vec.end());  // {1, 3, 5}

Sorting Algorithms

sort

O(n log n) sorting:

std::vector<int> vec = {5, 2, 8, 1, 9, 3};

std::sort(vec.begin(), vec.end());  // {1, 2, 3, 5, 8, 9}

// Custom comparator
std::sort(vec.begin(), vec.end(),
    [](int a, int b) { return a > b; });  // Descending

// Sort in place
std::stable_sort(vec.begin(), vec.end());  // Maintains equal element order

partial_sort

Sort first N elements:

std::vector<int> vec = {9, 5, 2, 7, 1, 8, 3};

std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());
// First 3 are smallest: {1, 2, 3}

nth_element

Partition around nth element:

std::vector<int> vec = {5, 2, 8, 1, 9, 3};

std::nth_element(vec.begin(), vec.begin() + 3, vec.end());
// Elements before position 3 are smaller, after are larger

Binary Search (on sorted ranges)

std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};

// Binary search
bool found = std::binary_search(vec.begin(), vec.end(), 5);  // true

// Lower bound (first not less than value)
auto lb = std::lower_bound(vec.begin(), vec.end(), 5);
// Points to 5

// Upper bound (first greater than value)
auto ub = std::upper_bound(vec.begin(), vec.end(), 5);
// Points to 6

// Equal range (both bounds)
auto [first, last] = std::equal_range(vec.begin(), vec.end(), 5);

Heap Operations

std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};

// Make heap
std::make_heap(vec.begin(), vec.end());
// Now: largest element at front

// Add element
vec.push_back(10);
std::push_heap(vec.begin(), vec.end());

// Remove largest
std::pop_heap(vec.begin(), vec.end());
vec.pop_back();  // Remove 10

Numeric Algorithms

accumulate

Sum or fold elements:

#include <numeric>
#include <vector>

std::vector<int> vec = {1, 2, 3, 4, 5};

int sum = std::accumulate(vec.begin(), vec.end(), 0);  // 15

// With custom operation
int product = std::accumulate(vec.begin(), vec.end(), 1,
    [](int a, int b) { return a * b; });  // 120

inner_product

Dot product of two vectors:

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

int dot = std::inner_product(a.begin(), a.end(), b.begin(), 0);
// 1*4 + 2*5 + 3*6 = 32

Complete Example: Processing Data

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <string>

int main() {
    std::vector<int> numbers = {5, 2, 8, 1, 9, 3, 7, 4, 6};

    // Print original
    std::cout << "Original: ";
    std::copy(numbers.begin(), numbers.end(),
        std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";

    // Count even numbers
    int evens = std::count_if(numbers.begin(), numbers.end(),
        [](int n) { return n % 2 == 0; });
    std::cout << "Even numbers: " << evens << "\n";

    // Transform: square each number
    std::vector<int> squared(numbers.size());
    std::transform(numbers.begin(), numbers.end(), squared.begin(),
        [](int n) { return n * n; });

    std::cout << "Squared: ";
    std::copy(squared.begin(), squared.end(),
        std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";

    // Sort
    std::sort(numbers.begin(), numbers.end());
    std::cout << "Sorted: ";
    std::copy(numbers.begin(), numbers.end(),
        std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";

    // Find
    auto it = std::find(numbers.begin(), numbers.end(), 5);
    if (it != numbers.end()) {
        std::cout << "Found 5 at position: " << (it - numbers.begin()) << "\n";
    }

    // Accumulate
    int sum = std::accumulate(numbers.begin(), numbers.end(), 0);
    std::cout << "Sum: " << sum << "\n";

    // Min/Max
    auto minIt = std::min_element(numbers.begin(), numbers.end());
    auto maxIt = std::max_element(numbers.begin(), numbers.end());
    std::cout << "Min: " << *minIt << ", Max: " << *maxIt << "\n";

    // Reverse
    std::reverse(numbers.begin(), numbers.end());
    std::cout << "Reversed: ";
    std::copy(numbers.begin(), numbers.end(),
        std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";

    return 0;
}

Using Lambdas with Algorithms

Lambdas are commonly used with STL algorithms:

std::vector<int> vec = {1, 2, 3, 4, 5};

// Filter and collect
std::vector<int> result;
std::copy_if(vec.begin(), vec.end(), std::back_inserter(result),
    [](int n) { return n > 3; });

// Sort by custom criteria
std::vector<std::string> words = {"apple", "banana", "cherry"};
std::sort(words.begin(), words.end(),
    [](const std::string& a, const std::string& b) {
        return a.length() < b.length();
    });

Key Takeaways

• STL algorithms work on ranges defined by iterators
• Non-modifying algorithms don’t change container contents
• Modifying algorithms can change or remove elements
• Sorting algorithms have O(n log n) complexity
• Use lambdas for custom comparison and transformation logic
• Algorithms work with any container supporting the required iterators

Next Steps

Let’s learn about iterators.

Next Chapter: 18_iterators.md - Iterators and Ranges