STL Algorithms & Ranges

The C++ Standard Library provides a comprehensive suite of algorithms in the <algorithm> and <numeric> headers. By decoupling data storage (containers) from data manipulation (algorithms) via iterators, the STL allows you to write highly optimized, reusable logic that is often faster and less bug-prone than manual loops.

---

1. Non-Modifying Algorithms

These algorithms inspect a range of elements without modifying their values.

1. Searching: std::find and std::find_if

std::find searches for a specific value. std::find_if searches for an element satisfying a boolean predicate (such as a lambda expression).

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

int main() {
    std::vector<int> nums = {12, 5, 8, 23, 19};

    // Find value 8
    auto it = std::find(nums.begin(), nums.end(), 8);
    if (it != nums.end()) {
        std::cout << "Found value: " << *it << "\n";
    }

    // Find the first value greater than 15 using a lambda predicate
    auto it_gt = std::find_if(nums.begin(), nums.end(), [](int n) {
        return n > 15;
    });

    if (it_gt != nums.end()) {
        std::cout << "First value > 15: " << *it_gt << "\n"; // Prints 23
    }

    return 0;
}

2. Verification: std::all_of, std::any_of, std::none_of

These inspect if all, any, or none of the elements in a range satisfy a condition.

#include <algorithm>
#include <vector>

void verify() {
    std::vector<int> nums = {1, 2, 3};
    bool all_positive = std::all_of(nums.begin(), nums.end(), [](int n) { return n > 0; });
}

---

2. Modifying Sequence Algorithms

These algorithms copy, move, replace, or transform elements in a range.

1. Element Mapping: std::transform

Applies a function to all elements in a input range and stores the result in a destination range (which can be the same container).

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

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

    // Square every element in-place
    std::transform(numbers.begin(), numbers.end(), numbers.begin(), [](int n) {
        return n * n;
    });

    // numbers is now: {1, 4, 9, 16}
    return 0;
}

2. In-Place Modifications: std::replace_if and std::fill

• std::fill sets all elements to a uniform value.
• std::replace_if replaces elements satisfying a condition.

  #include <algorithm>
  #include <vector>
  
  void modify() {
      std::vector<int> nums = {-1, 2, -3};
      // Replace all negative numbers with 0
      std::replace_if(nums.begin(), nums.end(), [](int n) { return n < 0; }, 0);
  }
  

---

3. Sorting and Binary Search

C++ algorithms are highly optimized. std::sort typically uses Introsort (a hybrid of Quicksort, Heapsort, and Insertion Sort) with a complexity of $O(n \log n)$.

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

int main() {
    std::vector<int> data = {9, 2, 5, 1, 7};

    // 1. Sort ascending
    std::sort(data.begin(), data.end()); 
    // data is now: {1, 2, 5, 7, 9}

    // 2. Sort descending using a standard comparator
    std::sort(data.begin(), data.end(), std::greater<int>());
    // data is now: {9, 7, 5, 2, 1}

    // 3. Binary Search (Requires range to be sorted first)
    std::sort(data.begin(), data.end());
    bool has_five = std::binary_search(data.begin(), data.end(), 5); // O(log n)
    std::cout << "Has 5: " << std::boolalpha << has_five << "\n";

    return 0;
}

---

4. Numeric Algorithms (<numeric>)

These algorithms focus on arithmetic operations over ranges.

• std::accumulate: Sums up a range (or accumulates values using a custom binary operation).
• std::reduce (C++17): Similar to std::accumulate, but supports parallel execution because it does not guarantee left-to-right evaluation order.

#include <numeric>
#include <vector>
#include <iostream>

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

    // Calculate sum of elements (initial value is 0)
    int sum = std::accumulate(nums.begin(), nums.end(), 0); // 15

    // Calculate product of elements (initial value is 1)
    int product = std::accumulate(nums.begin(), nums.end(), 1, std::multiplies<int>()); // 120

    return 0;
}

---

5. Modern C++20 Ranges and Views

C++20 introduced the Ranges Library, which completely modernizes how algorithms are used in three ways:

1. No Iterator Boilerplate: You can pass the entire container directly instead of vec.begin(), vec.end().
2. Piping Syntax (|): Allows you to chain operations like filter and map in a readable pipeline.
3. Lazy Evaluation (Views): Operations are evaluated only when the elements are iterated over. No temporary vectors or duplicate allocations are created in memory, yielding zero memory overhead.

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

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

    // 1. Direct container sorting
    std::ranges::sort(numbers);

    // 2. Chained lazy evaluations
    // Filter even numbers and square them
    auto pipeline = numbers 
                  | std::views::filter([](int n) { return n % 2 == 0; })
                  | std::views::transform([](int n) { return n * n; });

    // Elements are computed one-by-one only during the iteration
    for (int n : pipeline) {
        std::cout << n << " "; // Prints: 4 16 36 64 100
    }
    std::cout << "\n";

    return 0;
}

---

Related Guides

• STL Containers — The containers that hold the data for these algorithms.
• Functions — Lambdas and callables configuration.