STL Algorithms in C++

Table of Contents

1. •Introduction to STL Algorithms
2. •Non-Modifying Algorithms
3. •Modifying Algorithms
4. •Sorting Algorithms
5. •Searching Algorithms
6. •Partitioning Algorithms
7. •Numeric Algorithms
8. •Set Algorithms
9. •Heap Algorithms
10. •Min/Max Algorithms
11. •Permutation Algorithms
12. •C++17/20 Parallel Algorithms
13. •Best Practices

---

Introduction to STL Algorithms

STL algorithms are powerful, reusable functions that operate on containers through iterators.

Why Use STL Algorithms?

General Syntax

#include <algorithm>
#include <numeric>  // For numeric algorithms

// Most algorithms follow this pattern:
algorithm_name(begin_iterator, end_iterator, [optional_args]);

// With output:
algorithm_name(input_begin, input_end, output_begin, [optional_args]);

Iterator Categories

Algorithms require specific iterator types:

---

Non-Modifying Algorithms

These algorithms read but don't modify the container.

#include <algorithm>

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

// ═══════════════════════════════════════════════════════════
// for_each - apply function to all elements
// ═══════════════════════════════════════════════════════════
for_each(v.begin(), v.end(), [](int x) { cout << x << " "; });

// C++20: for_each with projection
// for_each(v.begin(), v.end(), [](int& x) { x *= 2; });

// ═══════════════════════════════════════════════════════════
// find / find_if / find_if_not - find first match
// ═══════════════════════════════════════════════════════════
auto it = find(v.begin(), v.end(), 3);  // Find value 3
if (it != v.end()) cout << "Found: " << *it;

auto it2 = find_if(v.begin(), v.end(), [](int x) { return x > 3; });
auto it3 = find_if_not(v.begin(), v.end(), [](int x) { return x < 3; });

// ═══════════════════════════════════════════════════════════
// count / count_if - count occurrences
// ═══════════════════════════════════════════════════════════
int n = count(v.begin(), v.end(), 2);                         // Count 2s
int n2 = count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; }); // Count evens

// ═══════════════════════════════════════════════════════════
// all_of, any_of, none_of - boolean checks (C++11)
// ═══════════════════════════════════════════════════════════
bool allPositive = all_of(v.begin(), v.end(), [](int x) { return x > 0; });
bool hasNegative = any_of(v.begin(), v.end(), [](int x) { return x < 0; });
bool noZeros = none_of(v.begin(), v.end(), [](int x) { return x == 0; });

// ═══════════════════════════════════════════════════════════
// equal - compare two ranges
// ═══════════════════════════════════════════════════════════
vector<int> v2 = {1, 2, 3, 4, 5};
bool same = equal(v.begin(), v.end(), v2.begin());

// With custom comparator
bool sameAbs = equal(v.begin(), v.end(), v2.begin(),
                     [](int a, int b) { return abs(a) == abs(b); });

// ═══════════════════════════════════════════════════════════
// mismatch - find first difference
// ═══════════════════════════════════════════════════════════
vector<int> a = {1, 2, 3, 4, 5};
vector<int> b = {1, 2, 9, 4, 5};
auto [it_a, it_b] = mismatch(a.begin(), a.end(), b.begin());
// *it_a == 3, *it_b == 9

// ═══════════════════════════════════════════════════════════
// adjacent_find - find consecutive duplicates
// ═══════════════════════════════════════════════════════════
vector<int> nums = {1, 2, 2, 3, 3, 3};
auto adj = adjacent_find(nums.begin(), nums.end());  // Points to first 2

---

Modifying Algorithms

These algorithms modify container contents.

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

// ═══════════════════════════════════════════════════════════
// copy / copy_if / copy_n / copy_backward
// ═══════════════════════════════════════════════════════════
vector<int> dest(5);
copy(v.begin(), v.end(), dest.begin());

// Copy only matching elements
vector<int> evens;
copy_if(v.begin(), v.end(), back_inserter(evens),
        [](int x) { return x % 2 == 0; });

// Copy first n elements
copy_n(v.begin(), 3, dest.begin());  // Copy first 3

// Copy backward (for overlapping ranges)
copy_backward(v.begin(), v.end() - 1, v.end());

// ═══════════════════════════════════════════════════════════
// move / move_backward - move semantics
// ═══════════════════════════════════════════════════════════
vector<string> src = {"a", "b", "c"};
vector<string> dst(3);
move(src.begin(), src.end(), dst.begin());  // src strings now empty

// ═══════════════════════════════════════════════════════════
// transform - apply function, store result
// ═══════════════════════════════════════════════════════════
// Unary transform
transform(v.begin(), v.end(), v.begin(),
          [](int x) { return x * 2; });

// Binary transform (two inputs)
vector<int> a = {1, 2, 3};
vector<int> b = {4, 5, 6};
vector<int> result(3);
transform(a.begin(), a.end(), b.begin(), result.begin(),
          [](int x, int y) { return x + y; });  // {5, 7, 9}

// ═══════════════════════════════════════════════════════════
// fill / fill_n - assign value to range
// ═══════════════════════════════════════════════════════════
fill(v.begin(), v.end(), 0);        // All zeros
fill_n(v.begin(), 3, 42);           // First 3 elements = 42

// ═══════════════════════════════════════════════════════════
// generate / generate_n - fill with function results
// ═══════════════════════════════════════════════════════════
int counter = 0;
generate(v.begin(), v.end(), [&counter]() { return counter++; });
// v = {0, 1, 2, 3, 4}

generate_n(v.begin(), 3, []() { return rand() % 100; });

// ═══════════════════════════════════════════════════════════
// replace / replace_if / replace_copy / replace_copy_if
// ═══════════════════════════════════════════════════════════
replace(v.begin(), v.end(), 3, 99);  // Replace all 3s with 99

replace_if(v.begin(), v.end(),
           [](int x) { return x < 0; }, 0);  // Replace negatives with 0

// Non-mutating versions
vector<int> replaced;
replace_copy_if(v.begin(), v.end(), back_inserter(replaced),
                [](int x) { return x < 0; }, 0);

// ═══════════════════════════════════════════════════════════
// remove / remove_if (IMPORTANT: doesn't actually erase!)
// ═══════════════════════════════════════════════════════════
// remove() moves elements, returns new "logical" end
auto newEnd = remove(v.begin(), v.end(), 3);
v.erase(newEnd, v.end());  // Actually erase the removed elements

// One-liner: Erase-Remove idiom
v.erase(remove(v.begin(), v.end(), 3), v.end());

// With condition
v.erase(remove_if(v.begin(), v.end(), [](int x) { return x < 0; }), v.end());

// C++20: std::erase / std::erase_if (simpler!)
// erase(v, 3);                                    // Remove all 3s
// erase_if(v, [](int x) { return x < 0; });       // Remove negatives

// ═══════════════════════════════════════════════════════════
// unique - remove consecutive duplicates
// ═══════════════════════════════════════════════════════════
vector<int> nums = {1, 1, 2, 2, 2, 3, 3};
auto uniqueEnd = unique(nums.begin(), nums.end());
nums.erase(uniqueEnd, nums.end());  // nums = {1, 2, 3}

// Tip: Sort first if you want to remove all duplicates
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

// ═══════════════════════════════════════════════════════════
// reverse / reverse_copy
// ═══════════════════════════════════════════════════════════
reverse(v.begin(), v.end());

vector<int> reversed;
reverse_copy(v.begin(), v.end(), back_inserter(reversed));

// ═══════════════════════════════════════════════════════════
// rotate / rotate_copy - circular shift
// ═══════════════════════════════════════════════════════════
// {1, 2, 3, 4, 5} -> rotate to start at element 3 -> {3, 4, 5, 1, 2}
vector<int> rot = {1, 2, 3, 4, 5};
rotate(rot.begin(), rot.begin() + 2, rot.end());  // {3, 4, 5, 1, 2}

// ═══════════════════════════════════════════════════════════
// shuffle - randomize order (C++11)
// ═══════════════════════════════════════════════════════════
#include <random>
random_device rd;
mt19937 gen(rd());
shuffle(v.begin(), v.end(), gen);

// ═══════════════════════════════════════════════════════════
// swap_ranges - swap elements between containers
// ═══════════════════════════════════════════════════════════
vector<int> x = {1, 2, 3};
vector<int> y = {4, 5, 6};
swap_ranges(x.begin(), x.end(), y.begin());
// Now x = {4, 5, 6}, y = {1, 2, 3}

---

Sorting Algorithms

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

// ═══════════════════════════════════════════════════════════
// sort - general purpose sort (O(n log n) average)
// ═══════════════════════════════════════════════════════════
sort(v.begin(), v.end());                        // Ascending

sort(v.begin(), v.end(), greater<int>());        // Descending

// Custom comparator
sort(v.begin(), v.end(), [](int a, int b) {
    return abs(a) < abs(b);  // Sort by absolute value
});

// ═══════════════════════════════════════════════════════════
// stable_sort - preserves relative order of equal elements
// ═══════════════════════════════════════════════════════════
struct Person {
    string name;
    int age;
};
vector<Person> people = {{"Alice", 30}, {"Bob", 30}, {"Charlie", 25}};

// Sort by age, but Alice stays before Bob (both age 30)
stable_sort(people.begin(), people.end(),
            [](const Person& a, const Person& b) { return a.age < b.age; });

// ═══════════════════════════════════════════════════════════
// partial_sort - sort only first n elements
// ═══════════════════════════════════════════════════════════
vector<int> nums = {5, 3, 1, 4, 2};
partial_sort(nums.begin(), nums.begin() + 3, nums.end());
// First 3 elements sorted: {1, 2, 3, ...rest unsorted}

// Useful for "Top K" problems
partial_sort(scores.begin(), scores.begin() + 10, scores.end(), greater<int>());
// Top 10 scores

// ═══════════════════════════════════════════════════════════
// nth_element - partition around nth element (O(n))
// ═══════════════════════════════════════════════════════════
vector<int> data = {5, 3, 1, 4, 2, 6, 7};
nth_element(data.begin(), data.begin() + 3, data.end());
// data[3] is now the median (4th smallest)
// Elements before it are smaller, after are larger (unsorted)

// Find median efficiently
size_t mid = data.size() / 2;
nth_element(data.begin(), data.begin() + mid, data.end());
int median = data[mid];

// ═══════════════════════════════════════════════════════════
// is_sorted / is_sorted_until
// ═══════════════════════════════════════════════════════════
bool sorted = is_sorted(v.begin(), v.end());

auto sortedUntil = is_sorted_until(v.begin(), v.end());
// Returns iterator to first out-of-order element

---

Searching Algorithms

On Sorted Ranges (Binary Search - O(log n))

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

// ═══════════════════════════════════════════════════════════
// binary_search - returns bool (just existence check)
// ═══════════════════════════════════════════════════════════
bool found = binary_search(v.begin(), v.end(), 5);  // true

// ═══════════════════════════════════════════════════════════
// lower_bound - first element >= value
// ═══════════════════════════════════════════════════════════
auto lb = lower_bound(v.begin(), v.end(), 5);
// Points to 5 (if exists) or first element > 5

// Useful for insertion point
auto insertPos = lower_bound(v.begin(), v.end(), 3);
v.insert(insertPos, 3);  // Insert maintaining sorted order

// ═══════════════════════════════════════════════════════════
// upper_bound - first element > value
// ═══════════════════════════════════════════════════════════
auto ub = upper_bound(v.begin(), v.end(), 5);
// Points to first element after all 5s

// ═══════════════════════════════════════════════════════════
// equal_range - range of equal elements [lower, upper)
// ═══════════════════════════════════════════════════════════
vector<int> nums = {1, 2, 2, 2, 3, 4, 5};
auto [first, last] = equal_range(nums.begin(), nums.end(), 2);
int count = distance(first, last);  // 3 (three 2s)

// Iterate over all 2s
for (auto it = first; it != last; ++it) {
    cout << *it << " ";  // 2 2 2
}

On Any Range (Linear Search - O(n))

// ═══════════════════════════════════════════════════════════
// find, find_if, find_if_not (see Non-Modifying section)
// ═══════════════════════════════════════════════════════════

// ═══════════════════════════════════════════════════════════
// find_first_of - find any element from a set
// ═══════════════════════════════════════════════════════════
vector<char> text = {'h', 'e', 'l', 'l', 'o'};
vector<char> vowels = {'a', 'e', 'i', 'o', 'u'};

auto it = find_first_of(text.begin(), text.end(),
                        vowels.begin(), vowels.end());
// Points to 'e' (first vowel found)

// ═══════════════════════════════════════════════════════════
// search - find subsequence (pattern matching)
// ═══════════════════════════════════════════════════════════
vector<int> haystack = {1, 2, 3, 4, 5, 6};
vector<int> needle = {3, 4, 5};

auto it2 = search(haystack.begin(), haystack.end(),
                  needle.begin(), needle.end());
if (it2 != haystack.end()) {
    // Found at position distance(haystack.begin(), it2)
}

// ═══════════════════════════════════════════════════════════
// find_end - find last occurrence of subsequence
// ═══════════════════════════════════════════════════════════
vector<int> data = {1, 2, 3, 1, 2, 3, 1, 2, 3};
vector<int> pattern = {1, 2, 3};
auto last = find_end(data.begin(), data.end(),
                     pattern.begin(), pattern.end());
// Points to last occurrence of {1, 2, 3}

// ═══════════════════════════════════════════════════════════
// search_n - find n consecutive copies
// ═══════════════════════════════════════════════════════════
vector<int> nums = {1, 2, 2, 2, 3, 3};
auto it3 = search_n(nums.begin(), nums.end(), 3, 2);
// Points to first 2 (we have three consecutive 2s)

---

Partitioning Algorithms

Partition divides elements into two groups based on a predicate.

// ═══════════════════════════════════════════════════════════
// partition - rearrange so matching elements come first
// ═══════════════════════════════════════════════════════════
vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};

auto partPoint = partition(v.begin(), v.end(),
                           [](int x) { return x % 2 == 0; });
// Evens first: {8, 2, 6, 4, 5, 3, 7, 1, 9} (order may vary)
// partPoint points to first odd

// ═══════════════════════════════════════════════════════════
// stable_partition - preserves relative order within groups
// ═══════════════════════════════════════════════════════════
vector<int> nums = {1, 2, 3, 4, 5, 6};
stable_partition(nums.begin(), nums.end(),
                 [](int x) { return x % 2 == 0; });
// {2, 4, 6, 1, 3, 5} - order preserved within each group

// ═══════════════════════════════════════════════════════════
// is_partitioned - check if already partitioned
// ═══════════════════════════════════════════════════════════
bool partitioned = is_partitioned(v.begin(), v.end(),
                                  [](int x) { return x % 2 == 0; });

// ═══════════════════════════════════════════════════════════
// partition_point - find the partition boundary
// ═══════════════════════════════════════════════════════════
// (Only works on already-partitioned range)
auto boundary = partition_point(v.begin(), v.end(),
                                [](int x) { return x % 2 == 0; });

// ═══════════════════════════════════════════════════════════
// partition_copy - partition into two separate containers
// ═══════════════════════════════════════════════════════════
vector<int> evens, odds;
partition_copy(v.begin(), v.end(),
               back_inserter(evens), back_inserter(odds),
               [](int x) { return x % 2 == 0; });

---

Numeric Algorithms

#include <numeric>

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

// ═══════════════════════════════════════════════════════════
// accumulate - sum (or fold with custom operation)
// ═══════════════════════════════════════════════════════════
int sum = accumulate(v.begin(), v.end(), 0);  // 15

// With custom operation
int product = accumulate(v.begin(), v.end(), 1, multiplies<int>());  // 120

// String concatenation
vector<string> words = {"Hello", " ", "World"};
string sentence = accumulate(words.begin(), words.end(), string(""));

// Custom lambda
int sumSquares = accumulate(v.begin(), v.end(), 0,
                            [](int acc, int x) { return acc + x*x; });

// ═══════════════════════════════════════════════════════════
// reduce (C++17) - parallel-friendly accumulate
// ═══════════════════════════════════════════════════════════
#include <execution>
int sum2 = reduce(execution::par, v.begin(), v.end());  // Parallel sum

// ═══════════════════════════════════════════════════════════
// inner_product - dot product of two vectors
// ═══════════════════════════════════════════════════════════
vector<int> a = {1, 2, 3};
vector<int> b = {4, 5, 6};
int dot = inner_product(a.begin(), a.end(), b.begin(), 0);
// 1*4 + 2*5 + 3*6 = 32

// Custom operations
int result = inner_product(a.begin(), a.end(), b.begin(), 0,
                           plus<int>(),        // Outer operation
                           [](int x, int y) { return x + y; });  // Inner

// ═══════════════════════════════════════════════════════════
// partial_sum - running sum
// ═══════════════════════════════════════════════════════════
vector<int> psum(5);
partial_sum(v.begin(), v.end(), psum.begin());
// v = {1, 2, 3, 4, 5}
// psum = {1, 3, 6, 10, 15}

// ═══════════════════════════════════════════════════════════
// adjacent_difference - difference between consecutive elements
// ═══════════════════════════════════════════════════════════
vector<int> prices = {100, 102, 99, 105, 103};
vector<int> changes(5);
adjacent_difference(prices.begin(), prices.end(), changes.begin());
// changes = {100, 2, -3, 6, -2}  (first element is unchanged)

// ═══════════════════════════════════════════════════════════
// iota - fill with incrementing values
// ═══════════════════════════════════════════════════════════
vector<int> sequence(10);
iota(sequence.begin(), sequence.end(), 1);
// sequence = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

// ═══════════════════════════════════════════════════════════
// gcd / lcm (C++17)
// ═══════════════════════════════════════════════════════════
int g = gcd(12, 18);  // 6
int l = lcm(4, 6);    // 12

// ═══════════════════════════════════════════════════════════
// transform_reduce (C++17) - transform + reduce in one
// ═══════════════════════════════════════════════════════════
// Sum of squares (parallel-friendly)
int sumSq = transform_reduce(v.begin(), v.end(), 0,
                             plus<int>(),
                             [](int x) { return x * x; });

// ═══════════════════════════════════════════════════════════
// inclusive_scan / exclusive_scan (C++17)
// ═══════════════════════════════════════════════════════════
vector<int> inc(5), exc(5);
inclusive_scan(v.begin(), v.end(), inc.begin());  // Like partial_sum
// inc = {1, 3, 6, 10, 15}

exclusive_scan(v.begin(), v.end(), exc.begin(), 0);
// exc = {0, 1, 3, 6, 10}

---

Set Algorithms

IMPORTANT: All set algorithms require sorted ranges!

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

// ═══════════════════════════════════════════════════════════
// set_union - elements in either set
// ═══════════════════════════════════════════════════════════
set_union(a.begin(), a.end(), b.begin(), b.end(),
          back_inserter(result));
// result = {1, 2, 3, 4, 5, 6, 7}

// ═══════════════════════════════════════════════════════════
// set_intersection - elements in both sets
// ═══════════════════════════════════════════════════════════
result.clear();
set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                 back_inserter(result));
// result = {3, 4, 5}

// ═══════════════════════════════════════════════════════════
// set_difference - elements in a but not in b
// ═══════════════════════════════════════════════════════════
result.clear();
set_difference(a.begin(), a.end(), b.begin(), b.end(),
               back_inserter(result));
// result = {1, 2}

// ═══════════════════════════════════════════════════════════
// set_symmetric_difference - elements in either but not both
// ═══════════════════════════════════════════════════════════
result.clear();
set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(),
                         back_inserter(result));
// result = {1, 2, 6, 7}

// ═══════════════════════════════════════════════════════════
// includes - check if one set contains another
// ═══════════════════════════════════════════════════════════
vector<int> subset = {3, 4};
bool isSubset = includes(a.begin(), a.end(),
                         subset.begin(), subset.end());  // true

// ═══════════════════════════════════════════════════════════
// merge - merge two sorted ranges
// ═══════════════════════════════════════════════════════════
vector<int> merged;
merge(a.begin(), a.end(), b.begin(), b.end(),
      back_inserter(merged));
// merged = {1, 2, 3, 3, 4, 4, 5, 5, 6, 7}  (duplicates included)

// ═══════════════════════════════════════════════════════════
// inplace_merge - merge adjacent sorted ranges
// ═══════════════════════════════════════════════════════════
vector<int> data = {1, 3, 5, 2, 4, 6};  // Two sorted halves
inplace_merge(data.begin(), data.begin() + 3, data.end());
// data = {1, 2, 3, 4, 5, 6}

---

Heap Algorithms

A heap is a tree structure where parent >= children (max-heap).

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

// ═══════════════════════════════════════════════════════════
// make_heap - turn vector into heap
// ═══════════════════════════════════════════════════════════
make_heap(v.begin(), v.end());  // Max element at front

cout << v.front();  // 9 (max element)

// ═══════════════════════════════════════════════════════════
// push_heap - add element to heap
// ═══════════════════════════════════════════════════════════
v.push_back(10);
push_heap(v.begin(), v.end());  // Restore heap property

// ═══════════════════════════════════════════════════════════
// pop_heap - remove max element
// ═══════════════════════════════════════════════════════════
pop_heap(v.begin(), v.end());   // Moves max to end
int maxVal = v.back();          // Get max value
v.pop_back();                   // Actually remove it

// ═══════════════════════════════════════════════════════════
// sort_heap - sort a heap (heap -> sorted array)
// ═══════════════════════════════════════════════════════════
sort_heap(v.begin(), v.end());

// ═══════════════════════════════════════════════════════════
// is_heap / is_heap_until
// ═══════════════════════════════════════════════════════════
bool valid = is_heap(v.begin(), v.end());
auto heapEnd = is_heap_until(v.begin(), v.end());

// ═══════════════════════════════════════════════════════════
// Example: Priority Queue Implementation
// ═══════════════════════════════════════════════════════════
vector<int> pq;

// Insert with priority
auto enqueue = [&pq](int val) {
    pq.push_back(val);
    push_heap(pq.begin(), pq.end());
};

// Remove highest priority
auto dequeue = [&pq]() {
    pop_heap(pq.begin(), pq.end());
    int val = pq.back();
    pq.pop_back();
    return val;
};

enqueue(3);
enqueue(1);
enqueue(4);
cout << dequeue();  // 4

---

Min/Max Algorithms

// ═══════════════════════════════════════════════════════════
// min / max / minmax
// ═══════════════════════════════════════════════════════════
int smaller = min(3, 5);         // 3
int larger = max(3, 5);          // 5
auto [lo, hi] = minmax(3, 5);    // lo=3, hi=5

// With custom comparator
string s1 = "apple", s2 = "banana";
string shorter = min(s1, s2, [](const string& a, const string& b) {
    return a.length() < b.length();
});

// ═══════════════════════════════════════════════════════════
// min_element / max_element / minmax_element
// ═══════════════════════════════════════════════════════════
vector<int> v = {3, 1, 4, 1, 5, 9};

auto minIt = min_element(v.begin(), v.end());  // Points to first 1
auto maxIt = max_element(v.begin(), v.end());  // Points to 9

auto [minE, maxE] = minmax_element(v.begin(), v.end());
cout << *minE << " " << *maxE;  // 1 9

// ═══════════════════════════════════════════════════════════
// clamp (C++17) - constrain value to range
// ═══════════════════════════════════════════════════════════
int val = 15;
int clamped = clamp(val, 0, 10);  // 10 (clamped to max)
clamped = clamp(-5, 0, 10);       // 0 (clamped to min)
clamped = clamp(5, 0, 10);        // 5 (unchanged)

---

Permutation Algorithms

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

// ═══════════════════════════════════════════════════════════
// next_permutation - next lexicographical permutation
// ═══════════════════════════════════════════════════════════
// Generates all permutations:
sort(v.begin(), v.end());  // Start sorted
do {
    for (int x : v) cout << x << " ";
    cout << "\n";
} while (next_permutation(v.begin(), v.end()));
// Output: 1 2 3 / 1 3 2 / 2 1 3 / 2 3 1 / 3 1 2 / 3 2 1

// ═══════════════════════════════════════════════════════════
// prev_permutation - previous lexicographical permutation
// ═══════════════════════════════════════════════════════════
vector<int> v2 = {3, 2, 1};
prev_permutation(v2.begin(), v2.end());  // {3, 1, 2}

// ═══════════════════════════════════════════════════════════
// is_permutation - check if one is permutation of other
// ═══════════════════════════════════════════════════════════
vector<int> a = {1, 2, 3};
vector<int> b = {3, 1, 2};
bool isPerm = is_permutation(a.begin(), a.end(), b.begin());  // true

// ═══════════════════════════════════════════════════════════
// lexicographical_compare - compare sequences
// ═══════════════════════════════════════════════════════════
vector<int> x = {1, 2, 3};
vector<int> y = {1, 2, 4};
bool xFirst = lexicographical_compare(x.begin(), x.end(),
                                       y.begin(), y.end());  // true (x < y)

---

C++17/20 Parallel Algorithms

C++17 introduced execution policies for parallel algorithms:

#include <execution>

vector<int> v(1000000);
iota(v.begin(), v.end(), 1);

// ═══════════════════════════════════════════════════════════
// Execution Policies
// ═══════════════════════════════════════════════════════════
// execution::seq        - sequential (default)
// execution::par        - parallel
// execution::par_unseq  - parallel + vectorized

// ═══════════════════════════════════════════════════════════
// Parallel sort
// ═══════════════════════════════════════════════════════════
sort(execution::par, v.begin(), v.end());

// ═══════════════════════════════════════════════════════════
// Parallel transform
// ═══════════════════════════════════════════════════════════
transform(execution::par, v.begin(), v.end(), v.begin(),
          [](int x) { return x * 2; });

// ═══════════════════════════════════════════════════════════
// Parallel reduce
// ═══════════════════════════════════════════════════════════
long long sum = reduce(execution::par, v.begin(), v.end(), 0LL);

// ═══════════════════════════════════════════════════════════
// Parallel for_each
// ═══════════════════════════════════════════════════════════
for_each(execution::par, v.begin(), v.end(), [](int& x) {
    x = compute_heavy(x);  // CPU-intensive work
});

C++20 Ranges (Preview)

#include <ranges>

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

// Pipeline syntax with views
auto result = v
    | views::filter([](int x) { return x % 2 == 0; })
    | views::transform([](int x) { return x * x; })
    | views::take(3);

for (int x : result) cout << x << " ";  // 4 16 36

// Ranges algorithms (take whole container)
ranges::sort(v);
auto it = ranges::find(v, 5);

---

Best Practices

✅ Do

// 1. Use erase-remove idiom (or C++20 std::erase)
v.erase(remove_if(v.begin(), v.end(), pred), v.end());

// 2. Use algorithms over raw loops
auto it = find(v.begin(), v.end(), target);  // Not manual loop

// 3. Use back_inserter for dynamic sizing
copy_if(src.begin(), src.end(), back_inserter(dest), pred);

// 4. Check return values
auto it = find(v.begin(), v.end(), x);
if (it != v.end()) { /* found */ }

// 5. Use appropriate algorithm
// - binary_search for sorted ranges (O(log n))
// - find for unsorted (O(n))

// 6. Use parallel execution for large datasets
sort(execution::par, large_vector.begin(), large_vector.end());

❌ Don't

// 1. Don't forget ranges must be sorted for binary_search
vector<int> unsorted = {5, 2, 8, 1};
binary_search(unsorted.begin(), unsorted.end(), 5);  // UNDEFINED!

// 2. Don't use remove() alone
remove(v.begin(), v.end(), x);  // Doesn't actually remove!
// Use erase-remove idiom instead

// 3. Don't modify container during iteration
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it < 0) v.erase(it);  // DANGER! Iterator invalidated
}
// Use erase-remove instead

// 4. Don't assume output size
vector<int> out;  // Empty!
copy(v.begin(), v.end(), out.begin());  // CRASH!
// Use back_inserter or resize first

// 5. Don't use wrong iterator category
forward_list<int> flist;
sort(flist.begin(), flist.end());  // ERROR! Needs random access
// Use flist.sort() for forward_list

---

Algorithm Cheat Sheet

Finding

Counting

Checking

Modifying

Sorting

---

Quick Reference

// Non-modifying
find, find_if, count, count_if
all_of, any_of, none_of
for_each, min_element, max_element
equal, mismatch, adjacent_find

// Modifying
copy, copy_if, copy_n, move
transform, fill, fill_n, generate
replace, replace_if, remove, remove_if
unique, reverse, rotate, shuffle

// Sorting
sort, stable_sort, partial_sort
nth_element, is_sorted

// Searching (sorted ranges)
binary_search, lower_bound, upper_bound
equal_range, search, find_first_of

// Partitioning
partition, stable_partition
partition_copy, partition_point

// Numeric
accumulate, reduce, inner_product
partial_sum, adjacent_difference, iota
gcd, lcm, transform_reduce

// Set operations (sorted ranges)
set_union, set_intersection
set_difference, set_symmetric_difference
includes, merge, inplace_merge

// Heap
make_heap, push_heap, pop_heap
sort_heap, is_heap

// Permutations
next_permutation, prev_permutation
is_permutation, lexicographical_compare

Compile & Run

g++ -std=c++17 -Wall examples.cpp -o examples && ./examples

# For parallel algorithms
g++ -std=c++17 -Wall -ltbb examples.cpp -o examples && ./examples