Skip to content

Algorithms Overview — Categories, Iterator Requirements, Ranges

DodaTech Updated 2026-06-28 7 min read

In this tutorial, you will learn about Algorithms Overview. We cover key concepts, practical examples, and best practices to help you master this topic.

C++ STL algorithms are generic functions operating on Iterator-defined ranges, categorized into non-modifying, modifying, sorting, Partitioning, numeric, and C++20 ranges operations.

What You'll Learn

You will understand the five algorithm categories (non-modifying, modifying, sorting, numeric, C++20 ranges), identify iterator requirements for each algorithm, use common algorithms effectively, compose algorithms with lambda expressions, and adopt ranges (C++20) for more readable algorithm chains.

Why It Matters

The STL algorithms library eliminates the need to write manual loops for common operations. Using std::find instead of a hand-written search loop makes code more readable, less error-prone, and often faster due to specialized implementations. The ranges library in C++20 takes this further with composable, lazy-evaluated views.

Learning Path

graph LR
    A["35: String & Span"] --> B["36: Algorithms Overview"]
    B --> C["37: Sorting & Searching"]
    C --> D["38: Modifying Algorithms"]
    D --> E["39: Numeric Algorithms"]
    E --> F["40: Ranges Library"]
    style A fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style B fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style C fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style D fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style E fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style F fill:#4a90d9,stroke:#2c5f8a,color:#fff

Algorithm Categories

Category Examples Iterator Requirement
Non-modifying find, count, equal, search Input iterator
Modifying copy, transform, replace, fill Output iterator
Removing remove, unique Forward iterator
Mutating reverse, rotate, shuffle Bidirectional/random
Sorting sort, partial_sort, nth_element Random access
Set set_union, set_intersection Input/output
Heap push_heap, pop_heap, make_heap Random access
Numeric accumulate, inner_product, iota Input iterator
Ranges (C++20) ranges::sort, views::filter Range concept

Iterator Requirements

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <iterator>

int main() {
    std::vector<int> vec = {5, 2, 8, 1, 9};
    std::list<int> lst = {5, 2, 8, 1, 9};
    
    // sort requires random access iterators (vector works, list does NOT)
    std::sort(vec.begin(), vec.end());
    // std::sort(lst.begin(), lst.end());  // Error: list has bidirectional iterators
    
    // find only requires input iterators (works with any container)
    auto it = std::find(lst.begin(), lst.end(), 8);
    
    // Iterator category hierarchy:
    // Input -> Forward -> Bidirectional -> Random Access
    // Output (separate hierarchy)
    
    // Check iterator category (C++20)
    // static_assert(std::random_access_iterator<decltype(vec.begin())>);
    // static_assert(std::bidirectional_iterator<decltype(lst.begin())>);
}

Common Algorithms Cheat Sheet

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

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    
    // Non-modifying
    auto found = std::find(v.begin(), v.end(), 9);
    int cnt = std::count(v.begin(), v.end(), 5);
    bool any = std::any_of(v.begin(), v.end(), [](int x) { return x > 8; });
    
    // Modifying
    std::fill(v.begin(), v.begin() + 3, 0);
    std::transform(v.begin(), v.end(), v.begin(), [](int x) { return x * 2; });
    
    // Sorting and partitioning
    std::sort(v.begin(), v.end());
    std::nth_element(v.begin(), v.begin() + 5, v.end());
    auto mid = std::partition(v.begin(), v.end(), [](int x) { return x < 5; });
    
    // Removing (erase-remove idiom)
    auto newEnd = std::remove(v.begin(), v.end(), 0);
    v.erase(newEnd, v.end());
    
    // Binary search (sorted range)
    bool exists = std::binary_search(v.begin(), v.end(), 5);
    
    // Min/max
    auto [minIt, maxIt] = std::minmax_element(v.begin(), v.end());
    
    // Numeric
    int sum = std::accumulate(v.begin(), v.end(), 0);
    std::vector<int> diff;
    std::adjacent_difference(v.begin(), v.end(), std::back_inserter(diff));
}

Using Lambdas with Algorithms

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

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // Filter using remove_if + lambda
    v.erase(std::remove_if(v.begin(), v.end(),
                [](int x) { return x % 2 == 0; }),
            v.end());
    
    // Transform with stateful lambda
    int offset = 100;
    std::transform(v.begin(), v.end(), v.begin(),
                   [offset](int x) { return x + offset; });
    
    // Sort with custom comparator
    std::sort(v.begin(), v.end(), [](int a, int b) {
        return a > b;  // descending
    });
    
    // for_each
    std::for_each(v.begin(), v.end(), [](int x) {
        std::cout << x << " ";
    });
    std::cout << "\n";
}

Ranges Library Preview (C++20)

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

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // Traditional
    std::vector<int> even1;
    std::copy_if(v.begin(), v.end(), std::back_inserter(even1),
                 [](int x) { return x % 2 == 0; });
    
    // Ranges (composable, lazy)
    auto even = v | std::views::filter([](int x) { return x % 2 == 0; })
                  | std::views::transform([](int x) { return x * 10; });
    
    for (int x : even) {
        std::cout << x << " ";
    }
    std::cout << "\n";
    
    // Ranges algorithms
    std::ranges::sort(v);
    auto it = std::ranges::find(v, 5);
}

Algorithm Naming Conventions

Suffix Meaning Example
_if Takes a predicate instead of a value find_if, remove_if, count_if
_copy Writes result to separate output remove_copy, reverse_copy
_n Takes a count instead of end iterator fill_n, generate_n
_copy_n Both copy and count copy_n

Common Mistakes

Mistake 1: Using sort on Sorted Ranges

If your data is already sorted, use lower_bound or binary_search instead of re-sorting.

Mistake 2: Forgetting the Erase-Remove Idiom

std::remove(v.begin(), v.end(), 5);  // does not erase, only shifts

remove returns the new logical end. You must erase the tail.

Mistake 3: Passing Wrong Iterator Category

std::list<int> lst = {3, 1, 4};
std::sort(lst.begin(), lst.end());  // Error: list iterators are bidirectional

Mistake 4: Modifying Container While Iterating

Some algorithms (like remove_if) work correctly. Others (like for_each with side effects) can invalidate iterators.

Mistake 5: Not Using Projections in Ranges (C++20)

struct Person { std::string name; int age; };
std::ranges::sort(people, {}, &Person::age);  // sort by age using projection

Mistake 6: Assuming Algorithms are Always Faster

For small containers (< 10 elements), a simple loop may be faster than an algorithm due to function call overhead.

Practice Questions

  1. What iterator category does std::sort require? Why?
  2. What is the difference between std::find and std::find_if?
  3. Why must you use the erase-remove idiom to actually delete elements?
  4. Write a lambda that transforms a vector of strings by converting each to uppercase.
  5. What advantage does the ranges library offer over traditional algorithms?

Challenge

Given a vector of strings, use STL algorithms to: (1) sort by string length, (2) remove strings shorter than 3 characters, (3) transform to uppercase, (4) print the result. Do this first with traditional algorithms, then with the ranges library.

FAQ

Why do algorithms use iterators instead of containers?

Iterators decouple algorithms from containers. One implementation of sort works with vector, array, deque, and raw arrays. This is the key insight of the STL.

Are STL algorithms faster than hand-written loops?

Often yes. Library implementations are optimized by experts, may use SIMD instructions, and are easier for compilers to optimize. But always profile for your specific use case.

What is the difference between `std::find` and `std::binary_search`?

find is O(n) linear search. binary_search is O(log n) but requires a sorted range. Use binary_search for larger, pre-sorted collections.

Can I use algorithms with arrays?

Yes. C-style arrays support pointers as iterators: std::sort(arr, arr + size) or std::sort(std::begin(arr), std::end(arr)).

What is the 'shrink_to_fit' concept?

shrink_to_fit is a container operation. In algorithms, the analogous concept is returning a view (ranges) rather than modifying in place.

What are 'projections' in C++20 ranges?

Projections transform elements before comparison. For example, sorting people by their .age field without writing a custom comparator.

Mini Project

Implement a text analysis tool using STL algorithms:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <sstream>
#include <cctype>

std::vector<std::string> tokenize(const std::string& text) {
    std::istringstream stream(text);
    std::vector<std::string> tokens;
    std::string token;
    while (stream >> token) {
        token.erase(std::remove_if(token.begin(), token.end(),
                       [](unsigned char c) { return std::ispunct(c); }),
                    token.end());
        if (!token.empty()) {
            std::transform(token.begin(), token.end(), token.begin(),
                           [](unsigned char c) { return std::tolower(c); });
            tokens.push_back(token);
        }
    }
    return tokens;
}

int main() {
    std::string text = "The quick brown fox jumps over the lazy dog. "
                       "The fox was quick, and the dog was lazy!";
    
    auto words = tokenize(text);
    std::sort(words.begin(), words.end());
    
    std::cout << "Word frequency:\n";
    auto it = words.begin();
    while (it != words.end()) {
        auto range = std::equal_range(words.begin(), words.end(), *it);
        int count = static_cast<int>(std::distance(range.first, range.second));
        std::cout << *it << ": " << count << "\n";
        it = range.second;
    }
}

What's Next

Algorithms are the heart of the STL. The next lesson covers sorting and searching algorithms in depth: sort, stable_sort, partial_sort, binary_search, lower_bound, upper_bound, and when to use each.

← Previous String and Span — std::string_view, std::span, String Operations Next → Sorting and Searching — sort, stable_sort, partial_sort, binary_search, lower_bound

Built by the developers of DodaTech

Doda Browser, DodaZIP & Durga Antivirus Pro

Home Browse Cpp