49. STL Algorithms & Iterators

Definition

STL algorithms are a collection of template functions that work with iterators to manipulate data in containers. These algorithms are separate from containers — a concept of separation of concerns — so one algorithm can work with many kinds of containers as long as the iterators provided are compatible.

Understanding iterators and STL algorithms is very important because it lets you write efficient, compact, and expressive code without writing manual loops.

Iterator Categories

The STL defines five iterator categories based on their operation capabilities:

#include <iostream>
#include <vector>
#include <list>
#include <forward_list>
#include <set>
using namespace std;

int main() {
    // Random Access Iterator — vector, deque, array
    vector<int> v = {1, 2, 3, 4, 5};
    auto rit = v.begin();
    rit += 3; // jump 3 elements (O(1))
    cout << "Random Access: " << *rit << endl;

    // Bidirectional Iterator — list, set, map
    list<int> l = {10, 20, 30};
    auto lit = l.end();
    --lit; // move backward (O(1))
    cout << "Bidirectional: " << *lit << endl;

    // Forward Iterator — forward_list, unordered_set
    forward_list<int> fl = {100, 200};
    auto flit = fl.begin();
    ++flit; // move forward (O(1))
    cout << "Forward: " << *flit << endl;

    return 0;
}

Category Explanation

• Input Iterator: read once, forward only (istream_iterator).
• Output Iterator: write once, forward only (ostream_iterator).
• Forward Iterator: read/write, forward only (forward_list, unordered_set).
• Bidirectional Iterator: read/write, forward & backward (list, set, map).
• Random Access Iterator: all capabilities + random jumping (vector, deque, array).

sort — Sorting

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> numbers = {45, 12, 78, 34, 23, 89, 15};

    // Sort ascending (default)
    sort(numbers.begin(), numbers.end());
    cout << "Ascending: ";
    for (int a : numbers) cout << a << " ";
    cout << endl;

    // Sort descending
    sort(numbers.rbegin(), numbers.rend());
    cout << "Descending: ";
    for (int a : numbers) cout << a << " ";
    cout << endl;

    // Sort with a custom comparator
    vector<string> name = {"Anna", "Mike", "John", "Dana"};
    sort(name.begin(), name.end(),
         [](const string& a, const string& b) {
             return a.length() < b.length(); // sort by length
         });
    cout << "By length: ";
    for (const auto& n : name) cout << n << " ";
    cout << endl;

    return 0;
}

Code Explanation

• sort() uses intro sort (quicksort + heapsort + insertion sort) — O(n log n) on average.
• rbegin() and rend() provide reverse iterators for sorting in descending order.
• A custom comparator enables flexible sorting logic.

find — Finding Elements

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> numbers = {10, 25, 30, 45, 50, 65};

    // find — O(n)
    auto it = find(numbers.begin(), numbers.end(), 45);
    if (it != numbers.end()) {
        cout << "Found at index: " << distance(numbers.begin(), it) << endl;
    } else {
        cout << "Not found" << endl;
    }

    // find_if — with a predicate
    auto it2 = find_if(numbers.begin(), numbers.end(),
                       [](int x) { return x > 40; });
    if (it2 != numbers.end()) {
        cout << "First > 40: " << *it2 << endl;
    }

    return 0;
}

Code Explanation

• find() searches for an element using operator== — O(n).
• find_if() searches based on a predicate (a function that returns bool).
• The returned iterator points to the found element or end() if there is none.

count — Counting Occurrences

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    // count — count occurrences of a value
    int count = count(numbers.begin(), numbers.end(), 2);
    cout << "Count of 2: " << count << endl;

    // count_if — count based on a condition
    int even = count_if(numbers.begin(), numbers.end(),
                         [](int x) { return x % 2 == 0; });
    cout << "Bilangan even: " << even << endl;

    return 0;
}

for_each — Iteration with Side Effects

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void print(int x) {
    cout << x << " ";
}

int main() {
    vector<int> numbers = {10, 20, 30, 40, 50};

    // for_each with a function
    for_each(numbers.begin(), numbers.end(), print);
    cout << endl;

    // for_each with a lambda
    for_each(numbers.begin(), numbers.end(), [](int& x) {
        x *= 2; // modify elements directly
    });

    cout << "After doubling: ";
    for_each(numbers.begin(), numbers.end(), [](int x) {
        cout << x << " ";
    });
    cout << endl;

    return 0;
}

Code Explanation

• for_each applies a function to every element in the range.
• A lambda taking a reference (int&) allows modifying the original elements.

transform — Element Transformation

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    vector<int> numbers = {1, 4, 9, 16, 25};

    // Transform: store results in a new container
    vector<double> akar(numbers.size());
    transform(numbers.begin(), numbers.end(), akar.begin(),
              [](int x) { return sqrt(x); });

    cout << "Square root: ";
    for (double a : akar) cout << a << " ";
    cout << endl;

    // Transform with two inputs
    vector<int> a = {1, 2, 3};
    vector<int> b = {10, 20, 30};
    vector<int> result(3);

    transform(a.begin(), a.end(), b.begin(), result.begin(),
              [](int x, int y) { return x + y; });

    cout << "Sum: ";
    for (int h : result) cout << h << " ";
    cout << endl;

    return 0;
}

Code Explanation

• transform with one input: applies a function to each element.
• transform with two inputs: combines elements from two containers.

accumulate — Accumulation

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

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

    // Total sum
    int total = accumulate(numbers.begin(), numbers.end(), 0);
    cout << "Total: " << total << endl;

    // Product
    int product = accumulate(numbers.begin(), numbers.end(), 1, multiplies<int>());
    cout << "Product: " << product << endl;

    // Concatenate strings
    vector<string> word = {"Hello", " ", "World"};
    string gabung = accumulate(word.begin(), word.end(), string(""));
    cout << "Gabungan: " << gabung << endl;

    return 0;
}

Code Explanation

• accumulate() comes from <numeric>. The third parameter is the initial value.
• multiplies<int>() is a functor for multiplication.

Binary Search — Binary Search

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> numbers = {10, 20, 30, 40, 50, 60, 70};

    // binary_search — O(log n), data MUST be sorted
    bool exist = binary_search(numbers.begin(), numbers.end(), 40);
    cout << "40 exist: " << (exist ? "Yes" : "No") << endl;

    // lower_bound — iterator to the first element >= value
    auto lb = lower_bound(numbers.begin(), numbers.end(), 35);
    cout << "lower_bound(35): " << *lb << endl;

    // upper_bound — iterator to the first element > value
    auto ub = upper_bound(numbers.begin(), numbers.end(), 40);
    cout << "upper_bound(40): " << *ub << endl;

    // Count elements between 30 and 60
    auto range_count = upper_bound(numbers.begin(), numbers.end(), 60)
                      - lower_bound(numbers.begin(), numbers.end(), 30);
    cout << "Count element [30, 60]: " << range_count << endl;

    return 0;
}

Code Explanation

• binary_search() returns a bool — whether the element exists.
• lower_bound() finds the correct insertion position to maintain order.
• upper_bound() is like lower_bound but for duplicates.
• Subtracting iterators counts the number of elements in the range.

remove_if — Conditional Removal

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    // Remove-if pattern: the erase-remove idiom
    // Remove all odd numbers
    numbers.erase(
        remove_if(numbers.begin(), numbers.end(),
                  [](int x) { return x % 2 != 0; }),
        numbers.end()
    );

    cout << "Remaining even numbers: ";
    for (int a : numbers) cout << a << " ";
    cout << endl;

    return 0;
}

Code Explanation

• remove_if() moves elements that don't satisfy the predicate to the front, returning an iterator to the "new end".
• erase() actually removes the elements from the container — this is the "erase-remove idiom".

unique — Removing Duplicates

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    // Sort first (unique requires sorted data)
    sort(numbers.begin(), numbers.end());

    // unique moves duplicates to the end
    auto last = unique(numbers.begin(), numbers.end());

    // Remove the remainder
    numbers.erase(last, numbers.end());

    cout << "After unique: ";
    for (int a : numbers) cout << a << " ";
    cout << endl;

    return 0;
}

Code Explanation

• unique() only removes consecutive duplicates — the data must be sorted first.
• Same pattern as erase-remove: erase(unique(...), end()).

reverse — Reversing Order

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    reverse(numbers.begin(), numbers.end());

    cout << "Reversed: ";
    for (int a : numbers) cout << a << " ";
    cout << endl;

    // is_sorted — check whether it is already sorted
    cout << "Sorted: " << (is_sorted(numbers.begin(), numbers.end()) ? "Yes" : "No") << endl;

    return 0;
}

Iterator Invalidation

It's important to understand when an iterator becomes invalid:

#include <iostream>
#include <vector>
using namespace std;

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

    // BAD: Iterator invalidated by push_back
    auto it = v.begin();
    v.push_back(6); // it may no longer be valid!
    // cout << *it; // UNDEFINED BEHAVIOR

    // GOOD: Use an index or obtain the iterator again
    v = {1, 2, 3, 4, 5};
    size_t idx = 2;
    v.push_back(6);
    cout << "Masih safe: " << v[idx] << endl;

    // Watch out for invalidation when erasing while iterating
    vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8};
    for (auto it = nums.begin(); it != nums.end(); ) {
        if (*it % 2 == 0) {
            it = nums.erase(it); // erase returns the next valid iterator
        } else {
            ++it;
        }
    }

    cout << "After removing even numbers: ";
    for (int n : nums) cout << n << " ";
    cout << endl;

    return 0;
}

Code Explanation

• push_back() on a vector can trigger reallocation — all iterators are invalidated.
• erase() returns an iterator to the next valid element.
• Always update the iterator after an operation that may invalidate it.

Case Study: Sorting and Searching Students

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

struct Student {
    string name;
    int grade;
};

int main() {
    vector<Student> students = {
        {"Mike", 85}, {"John", 92}, {"Anna", 78},
        {"Dana", 95}, {"Eric", 88}
    };

    // Sort by score in descending order
    sort(students.begin(), students.end(),
         [](const Student& a, const Student& b) {
             return a.grade > b.grade;
         });

    cout << "Peringkat:" << endl;
    int rank = 1;
    for (const auto& m : students) {
        cout << rank++ << ". " << m.name << " (" << m.grade << ")" << endl;
    }

    // Binary search by name (requires sorting by name first)
    vector<Student> byName = students;
    sort(byName.begin(), byName.end(),
         [](const Student& a, const Student& b) {
             return a.name < b.name;
         });

    string search = "Anna";
    bool found = binary_search(byName.begin(), byName.end(), Student{search, 0},
                                   [](const Student& a, const Student& b) {
                                       return a.name < b.name;
                                   });
    cout << "\n" << search << ": " << (found ? "Found" : "Not found") << endl;

    // Average score
    int total = accumulate(students.begin(), students.end(), 0,
                           [](int sum, const Student& m) {
                               return sum + m.grade;
                           });
    cout << "Average: " << total / students.size() << endl;

    return 0;
}

Case Study: Sales Data Analysis

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

int main() {
    vector<int> penjualan = {150, 200, 120, 300, 250, 180, 400, 90};

    // Total sales
    int total = accumulate(penjualan.begin(), penjualan.end(), 0);
    cout << "Total penjualan: " << total << endl;

    // Average
    double average = static_cast<double>(total) / penjualan.size();
    cout << "Average: " << average << endl;

    // Maximum and minimum
    auto [minIt, maxIt] = minmax_element(penjualan.begin(), penjualan.end());
    cout << "Min: " << *minIt << ", Max: " << *maxIt << endl;

    // Months with sales > 200
    int count = count_if(penjualan.begin(), penjualan.end(),
                         [](int x) { return x > 200; });
    cout << "Months > 200: " << count << endl;

    // Sort for the median
    vector<int> sorted = penjualan;
    sort(sorted.begin(), sorted.end());
    double median;
    size_t mid = sorted.size() / 2;
    if (sorted.size() % 2 == 0) {
        median = (sorted[mid - 1] + sorted[mid]) / 2.0;
    } else {
        median = sorted[mid];
    }
    cout << "Median: " << median << endl;

    return 0;
}

Summary

STL algorithms eliminate boilerplate loops and produce code that is more expressive and easier to maintain. Understanding iterator categories and invalidation rules is crucial for writing correct code. Combining algorithms with lambdas yields code that is compact and powerful.