18.3 — Introduction to standard library algorithms

In this lesson, you'll learn about the C++ Standard Template Library (STL) algorithms, which provide powerful, ready-to-use functions for common operations like searching, sorting, and transforming data. These algorithms work seamlessly with iterators and containers.

What are STL algorithms?

STL algorithms are template functions in the C++ standard library that perform common operations on sequences of elements. They work with iterators, making them compatible with all STL containers and even raw arrays.

Think of STL algorithms like specialized tools in a workshop:

• std::sort: A powerful sorting machine that can arrange any collection
• std::find: A search tool that locates specific items
• std::count: A counting device that tallies occurrences
• std::transform: A converter that modifies each element

Why use STL algorithms?

STL algorithms offer significant advantages over writing your own loops:

1. Tested and optimized: Written by experts and thoroughly tested
2. Expressive: Code clearly states intent (std::sort vs nested loops)
3. Efficient: Often use advanced techniques for better performance
4. Generic: Work with any compatible container or iterator
5. Less error-prone: Reduce chances of off-by-one errors and bugs

Including algorithms

STL algorithms are found in the <algorithm> header:

#include <algorithm>  // Most algorithms
#include <numeric>    // Numeric algorithms like std::accumulate

Categories of STL algorithms

Non-modifying sequence operations

These algorithms read data without changing it:

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

int main()
{
    std::vector<int> numbers = {1, 3, 5, 3, 7, 3, 9};
    
    // std::find - find first occurrence
    auto it = std::find(numbers.begin(), numbers.end(), 5);
    if (it != numbers.end())
    {
        std::cout << "Found 5 at position: " << (it - numbers.begin()) << std::endl;
    }
    
    // std::count - count occurrences
    int count = std::count(numbers.begin(), numbers.end(), 3);
    std::cout << "Number 3 appears " << count << " times" << std::endl;
    
    // std::all_of - check if all elements satisfy condition
    bool allPositive = std::all_of(numbers.begin(), numbers.end(), 
                                   [](int n) { return n > 0; });
    std::cout << "All numbers positive: " << (allPositive ? "Yes" : "No") << std::endl;
    
    return 0;
}

Output:

Found 5 at position: 2
Number 3 appears 3 times
All numbers positive: Yes

Modifying sequence operations

These algorithms modify the sequence in place:

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

void printVector(const std::vector<int>& vec, const std::string& label)
{
    std::cout << label << ": ";
    for (int n : vec)
        std::cout << n << " ";
    std::cout << std::endl;
}

int main()
{
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    printVector(numbers, "Original");
    
    // std::reverse - reverse the sequence
    std::reverse(numbers.begin(), numbers.end());
    printVector(numbers, "After reverse");
    
    // std::fill - fill with a value
    std::fill(numbers.begin(), numbers.begin() + 3, 99);
    printVector(numbers, "After fill first 3 with 99");
    
    // std::replace - replace all occurrences
    numbers = {1, 2, 3, 2, 4, 2, 5};
    printVector(numbers, "New sequence");
    std::replace(numbers.begin(), numbers.end(), 2, 20);
    printVector(numbers, "After replacing 2 with 20");
    
    return 0;
}

Output:

Original: 1 2 3 4 5 
After reverse: 5 4 3 2 1 
After fill first 3 with 99: 99 99 99 2 1 
New sequence: 1 2 3 2 4 2 5 
After replacing 2 with 20: 1 20 3 20 4 20 5 

Sorting and related operations

These algorithms reorder elements:

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

int main()
{
    std::vector<int> numbers = {64, 25, 12, 22, 11, 90, 5};
    
    std::cout << "Original: ";
    for (int n : numbers)
        std::cout << n << " ";
    std::cout << std::endl;
    
    // std::sort - sort in ascending order
    std::sort(numbers.begin(), numbers.end());
    std::cout << "Sorted ascending: ";
    for (int n : numbers)
        std::cout << n << " ";
    std::cout << std::endl;
    
    // std::sort with custom comparison - descending order
    std::sort(numbers.begin(), numbers.end(), std::greater<int>());
    std::cout << "Sorted descending: ";
    for (int n : numbers)
        std::cout << n << " ";
    std::cout << std::endl;
    
    // std::partial_sort - partially sort (first 3 elements)
    std::vector<int> partial = {64, 25, 12, 22, 11, 90, 5};
    std::partial_sort(partial.begin(), partial.begin() + 3, partial.end());
    std::cout << "Partial sort (first 3): ";
    for (int n : partial)
        std::cout << n << " ";
    std::cout << std::endl;
    
    return 0;
}

Output:

Original: 64 25 12 22 11 90 5 
Sorted ascending: 5 11 12 22 25 64 90 
Sorted descending: 90 64 25 22 12 11 5 
Partial sort (first 3): 5 11 12 64 25 90 22 

Working with predicates and lambda expressions

Many STL algorithms accept predicates - functions that return true or false. Modern C++ uses lambda expressions for convenient inline predicates:

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

int main()
{
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    std::cout << "Original numbers: ";
    for (int n : numbers)
        std::cout << n << " ";
    std::cout << std::endl;
    
    // std::find_if - find first element matching condition
    auto evenIt = std::find_if(numbers.begin(), numbers.end(),
                               [](int n) { return n % 2 == 0; });
    if (evenIt != numbers.end())
    {
        std::cout << "First even number: " << *evenIt << std::endl;
    }
    
    // std::count_if - count elements matching condition
    int evenCount = std::count_if(numbers.begin(), numbers.end(),
                                  [](int n) { return n % 2 == 0; });
    std::cout << "Count of even numbers: " << evenCount << std::endl;
    
    // std::remove_if - remove elements matching condition (returns new end)
    auto newEnd = std::remove_if(numbers.begin(), numbers.end(),
                                 [](int n) { return n % 2 == 0; });
    numbers.erase(newEnd, numbers.end()); // Actually remove elements
    
    std::cout << "After removing even numbers: ";
    for (int n : numbers)
        std::cout << n << " ";
    std::cout << std::endl;
    
    return 0;
}

Output:

Original numbers: 1 2 3 4 5 6 7 8 9 10 
First even number: 2
Count of even numbers: 5
After removing even numbers: 1 3 5 7 9 

Binary search operations (require sorted data)

These algorithms work efficiently on sorted sequences:

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

int main()
{
    std::vector<int> numbers = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    
    std::cout << "Sorted array: ";
    for (int n : numbers)
        std::cout << n << " ";
    std::cout << std::endl;
    
    // std::binary_search - check if element exists
    bool found = std::binary_search(numbers.begin(), numbers.end(), 7);
    std::cout << "Is 7 in the array? " << (found ? "Yes" : "No") << std::endl;
    
    found = std::binary_search(numbers.begin(), numbers.end(), 8);
    std::cout << "Is 8 in the array? " << (found ? "Yes" : "No") << std::endl;
    
    // std::lower_bound - find first position where value could be inserted
    auto lower = std::lower_bound(numbers.begin(), numbers.end(), 8);
    std::cout << "Position to insert 8: " << (lower - numbers.begin()) << std::endl;
    
    // std::upper_bound - find last position where value could be inserted
    auto upper = std::upper_bound(numbers.begin(), numbers.end(), 7);
    std::cout << "Position after last 7: " << (upper - numbers.begin()) << std::endl;
    
    return 0;
}

Output:

Sorted array: 1 3 5 7 9 11 13 15 17 19 
Is 7 in the array? Yes
Is 8 in the array? No
Position to insert 8: 4
Position after last 7: 4

Transforming algorithms

These algorithms apply operations to transform elements:

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

int main()
{
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    std::vector<int> squares(numbers.size());
    
    // std::transform - apply function to each element
    std::transform(numbers.begin(), numbers.end(), squares.begin(),
                   [](int n) { return n * n; });
    
    std::cout << "Original: ";
    for (int n : numbers)
        std::cout << n << " ";
    std::cout << std::endl;
    
    std::cout << "Squares: ";
    for (int n : squares)
        std::cout << n << " ";
    std::cout << std::endl;
    
    // Transform strings to uppercase
    std::vector<std::string> words = {"hello", "world", "cpp", "algorithms"};
    std::cout << "\nOriginal words: ";
    for (const std::string& word : words)
        std::cout << word << " ";
    std::cout << std::endl;
    
    // Transform each string to uppercase
    std::transform(words.begin(), words.end(), words.begin(),
                   [](std::string s) {
                       std::transform(s.begin(), s.end(), s.begin(), ::toupper);
                       return s;
                   });
    
    std::cout << "Uppercase: ";
    for (const std::string& word : words)
        std::cout << word << " ";
    std::cout << std::endl;
    
    return 0;
}

Output:

Original: 1 2 3 4 5 
Squares: 1 4 9 16 25 

Original words: hello world cpp algorithms 
Uppercase: HELLO WORLD CPP ALGORITHMS 

Numeric algorithms

The <numeric> header provides algorithms for mathematical operations:

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

int main()
{
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    std::cout << "Numbers: ";
    for (int n : numbers)
        std::cout << n << " ";
    std::cout << std::endl;
    
    // std::accumulate - sum all elements
    int sum = std::accumulate(numbers.begin(), numbers.end(), 0);
    std::cout << "Sum: " << sum << std::endl;
    
    // std::accumulate with custom operation - product
    int product = std::accumulate(numbers.begin(), numbers.begin() + 4, 1,
                                  [](int a, int b) { return a * b; });
    std::cout << "Product of first 4: " << product << std::endl;
    
    // std::partial_sum - running totals
    std::vector<int> runningSum(numbers.size());
    std::partial_sum(numbers.begin(), numbers.end(), runningSum.begin());
    
    std::cout << "Running sums: ";
    for (int n : runningSum)
        std::cout << n << " ";
    std::cout << std::endl;
    
    // std::adjacent_difference - differences between adjacent elements
    std::vector<int> differences(numbers.size());
    std::adjacent_difference(numbers.begin(), numbers.end(), differences.begin());
    
    std::cout << "Adjacent differences: ";
    for (int n : differences)
        std::cout << n << " ";
    std::cout << std::endl;
    
    return 0;
}

Output:

Numbers: 1 2 3 4 5 6 7 8 9 10 
Sum: 55
Product of first 4: 24
Running sums: 1 3 6 10 15 21 28 36 45 55 
Adjacent differences: 1 1 1 1 1 1 1 1 1 1 

Combining multiple algorithms

STL algorithms can be chained together for powerful data processing:

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

int main()
{
    std::vector<int> data = {15, 3, 8, 1, 12, 7, 4, 9, 6, 11, 2, 10, 5, 14, 13};
    
    std::cout << "Original data: ";
    for (int n : data)
        std::cout << n << " ";
    std::cout << std::endl;
    
    // Chain multiple operations:
    // 1. Remove odd numbers
    // 2. Sort the remaining even numbers  
    // 3. Calculate their sum
    
    // Step 1: Remove odd numbers
    auto newEnd = std::remove_if(data.begin(), data.end(),
                                 [](int n) { return n % 2 != 0; });
    data.erase(newEnd, data.end());
    
    std::cout << "After removing odd numbers: ";
    for (int n : data)
        std::cout << n << " ";
    std::cout << std::endl;
    
    // Step 2: Sort the even numbers
    std::sort(data.begin(), data.end());
    
    std::cout << "After sorting: ";
    for (int n : data)
        std::cout << n << " ";
    std::cout << std::endl;
    
    // Step 3: Calculate sum
    int sum = std::accumulate(data.begin(), data.end(), 0);
    std::cout << "Sum of even numbers: " << sum << std::endl;
    
    return 0;
}

Output:

Original data: 15 3 8 1 12 7 4 9 6 11 2 10 5 14 13 
After removing odd numbers: 8 12 4 6 2 10 14 
After sorting: 2 4 6 8 10 12 14 
Sum of even numbers: 56

Algorithm performance considerations

Understanding algorithm complexity helps you choose the right tool:

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

// Function to measure execution time
template<typename Func>
void timeFunction(Func func, const std::string& description)
{
    auto start = std::chrono::high_resolution_clock::now();
    func();
    auto end = std::chrono::high_resolution_clock::now();
    
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    std::cout << description << " took: " << duration.count() << " microseconds" << std::endl;
}

int main()
{
    const size_t SIZE = 10000;
    std::vector<int> data(SIZE);
    
    // Fill with random-like data
    for (size_t i = 0; i < SIZE; ++i)
    {
        data[i] = (SIZE - i) % 1000;
    }
    
    // Compare different approaches
    std::vector<int> copy1 = data;
    timeFunction([&copy1]() {
        std::sort(copy1.begin(), copy1.end());
    }, "std::sort (O(n log n))");
    
    std::vector<int> copy2 = data;
    timeFunction([&copy2]() {
        // Find minimum manually (similar to selection sort)
        for (size_t i = 0; i < copy2.size() - 1; ++i)
        {
            auto minIt = std::min_element(copy2.begin() + i, copy2.end());
            std::swap(copy2[i], *minIt);
        }
    }, "Selection sort simulation (O(n²))");
    
    // Search comparisons
    std::sort(data.begin(), data.end());
    int target = 500;
    
    timeFunction([&data, target]() {
        auto it = std::find(data.begin(), data.end(), target);
        (void)it; // Suppress unused variable warning
    }, "Linear search (O(n))");
    
    timeFunction([&data, target]() {
        bool found = std::binary_search(data.begin(), data.end(), target);
        (void)found; // Suppress unused variable warning
    }, "Binary search (O(log n))");
    
    return 0;
}

Sample Output:

std::sort (O(n log n)) took: 1245 microseconds
Selection sort simulation (O(n²)) took: 15678 microseconds
Linear search (O(n)) took: 125 microseconds
Binary search (O(log n)) took: 8 microseconds

Best practices for using STL algorithms

1. Prefer algorithms over raw loops

// Instead of this:
std::vector<int> numbers = {1, 2, 3, 4, 5};
bool found = false;
for (size_t i = 0; i < numbers.size(); ++i)
{
    if (numbers[i] == 3)
    {
        found = true;
        break;
    }
}

// Write this:
auto it = std::find(numbers.begin(), numbers.end(), 3);
bool found = (it != numbers.end());

2. Use const iterators when not modifying

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

// Good - using const iterators for read-only operations
int sum = std::accumulate(numbers.cbegin(), numbers.cend(), 0);

// Also good - using const range
for (const int& num : numbers)
{
    std::cout << num << " ";
}

3. Combine algorithms effectively

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

// Process in one clear chain:
// Remove odd numbers, then double the remaining even numbers
auto newEnd = std::remove_if(data.begin(), data.end(),
                             [](int n) { return n % 2 != 0; });
data.erase(newEnd, data.end());

std::transform(data.begin(), data.end(), data.begin(),
               [](int n) { return n * 2; });

4. Use appropriate algorithm variants

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

// Use _if variants when you have a condition
int evenCount = std::count_if(numbers.begin(), numbers.end(),
                              [](int n) { return n % 2 == 0; });

// Use _copy variants when you want to preserve the original
std::vector<int> doubled(numbers.size());
std::transform(numbers.begin(), numbers.end(), doubled.begin(),
               [](int n) { return n * 2; });

Common mistakes and how to avoid them

1. Forgetting that some algorithms don't actually remove elements

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

// Wrong - remove doesn't actually erase elements
auto newEnd = std::remove(numbers.begin(), numbers.end(), 2);
// numbers might still contain the old elements at the end!

// Correct - use the erase-remove idiom
auto newEnd = std::remove(numbers.begin(), numbers.end(), 2);
numbers.erase(newEnd, numbers.end());

2. Using algorithms on empty containers

std::vector<int> empty;

// Dangerous - undefined behavior if empty
// int min = *std::min_element(empty.begin(), empty.end());

// Safe - check first
if (!empty.empty())
{
    int min = *std::min_element(empty.begin(), empty.end());
    std::cout << "Minimum: " << min << std::endl;
}

3. Modifying containers while iterating with algorithms

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

// Dangerous - don't modify the container during algorithm execution
std::for_each(numbers.begin(), numbers.end(), [&numbers](int n) {
    if (n % 2 == 0)
    {
        numbers.push_back(n * 2); // Don't do this!
    }
});

Summary

STL algorithms are powerful tools that make C++ programming more expressive and efficient:

• Non-modifying algorithms like std::find, std::count, and std::all_of examine data without changing it
• Modifying algorithms like std::sort, std::reverse, and std::transform modify sequences in place
• Numeric algorithms like std::accumulate and std::partial_sum perform mathematical operations
• Binary search algorithms work efficiently on sorted data
• Lambda expressions make it easy to customize algorithm behavior
• Algorithm chaining enables powerful data processing pipelines

Key benefits:

• Proven correctness: Thoroughly tested and optimized implementations
• Expressive code: Clear intent and reduced boilerplate
• Performance: Often faster than hand-written loops
• Generic design: Works with all STL containers and custom types

In the next lesson, you'll learn how to measure and analyze the performance of your code, which will help you make informed decisions about when to use different algorithms and data structures.

Quiz

1. What header file contains most of the STL algorithms?
2. What is the difference between std::find and std::find_if?
3. Why do you need to call erase() after std::remove()?
4. What is the time complexity of std::binary_search compared to std::find?
5. Which algorithm would you use to apply a function to every element in a container and store the results in another container?

Practice exercises

Try these exercises to master STL algorithms:

1. Data processing pipeline: Given a vector of integers, write a program that removes negative numbers, sorts the remaining numbers, and calculates both their sum and average using STL algorithms.

2. String manipulation: Create a program that takes a vector of strings, converts them all to lowercase, removes duplicates, and sorts them alphabetically using appropriate STL algorithms.

3. Statistical analysis: Write functions using STL algorithms to find the minimum, maximum, mean, and count of elements in a dataset that meet certain criteria (e.g., values above a threshold).

4. Custom sorting: Create a program that sorts a vector of custom objects (e.g., Student with name and grade) using different criteria with std::sort and custom comparison functions or lambda expressions.