STL — Algorithms and Iterators

The C++ Standard Template Library ships with more than 100 generic algorithms in the <algorithm> and <numeric> headers. These algorithms operate on ranges defined by a pair of iterators, making them container-agnostic. A single call to std::sort works equally well on a vector, a deque, or a plain array. This design is one of the cleanest pieces of engineering in the entire C++ standard library.

For competitive programmers at platforms like Codeforces, LeetCode, or CodeChef — and for engineers preparing for FAANG interviews at Google India, Amazon Hyderabad, or Microsoft Pune — fluency with STL algorithms is the difference between a 30-line brute-force solution and a clean, idiomatic 5-liner.

---

Understanding Iterators

An iterator is an object that points to an element inside a container. You can think of it as a generalised pointer. The STL defines five iterator categories, and the category of an iterator determines which algorithms can use it.

Iterator Categories

Category	Supports	Typical Container
Input Iterator	Read once, move forward	std::istream_iterator
Output Iterator	Write once, move forward	std::ostream_iterator
Forward Iterator	Read/write, multi-pass forward	std::forward_list
Bidirectional Iterator	Forward + backward (--)	std::list, std::map
Random Access Iterator	Bidirectional + jump (+n, -n, [])	std::vector, std::deque, plain arrays

Random access iterators are the most powerful. Algorithms like std::sort require random access iterators because they need to jump to arbitrary positions in O(1) time.

Obtaining Iterators

Every STL container exposes iterators through member functions:

#include <vector>
#include <iostream>

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

    auto it = v.begin();   // points to first element
    auto end = v.end();    // points one-past-last element

    while (it != end) {
        std::cout << *it << " ";
        ++it;
    }
    // Output: 10 20 30 40 50

    // Reverse iterators
    for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
        std::cout << *rit << " ";
    }
    // Output: 50 40 30 20 10
}

The range [begin, end) is half-open: begin is included, end is excluded. This convention makes empty ranges trivial to express and loop termination natural.

---

The <algorithm> Header

Include <algorithm> and <numeric> to get access to the full set of algorithms.

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

---

Searching Algorithms

std::find

Finds the first element equal to a value. Returns an iterator to the element, or end if not found.

std::vector<int> marks = {72, 85, 91, 60, 88};
auto it = std::find(marks.begin(), marks.end(), 91);

if (it != marks.end()) {
    std::cout << "Found 91 at index " << (it - marks.begin()) << "\n";
} else {
    std::cout << "Not found\n";
}

std::count and std::count_if

std::count counts occurrences of a value. std::count_if counts elements satisfying a predicate.

std::vector<int> scores = {55, 72, 55, 89, 55, 63};

int cnt = std::count(scores.begin(), scores.end(), 55);
std::cout << "55 appears " << cnt << " times\n";  // 3

// Count students who scored above 70 (passed in typical Indian university grading)
int passed = std::count_if(scores.begin(), scores.end(),
    [](int s) { return s > 70; });
std::cout << passed << " students passed\n";  // 2

std::binary_search

Performs a binary search on a sorted range. Returns true if the element exists.

std::vector<int> sorted = {10, 20, 30, 40, 50};
bool found = std::binary_search(sorted.begin(), sorted.end(), 30);
std::cout << std::boolalpha << found << "\n";  // true

---

Sorting Algorithms

std::sort

Sorts elements in ascending order by default. Requires random access iterators.

std::vector<int> v = {5, 2, 8, 1, 9, 3};
std::sort(v.begin(), v.end());
// v is now {1, 2, 3, 5, 8, 9}

std::sort with a Custom Comparator

A comparator is a callable that returns true when its first argument should appear before the second.

// Sort descending
std::sort(v.begin(), v.end(), [](int a, int b) {
    return a > b;  // larger elements come first
});
// v is now {9, 8, 5, 3, 2, 1}

You can also use the built-in std::greater<int>{}:

std::sort(v.begin(), v.end(), std::greater<int>{});

---

Transformation Algorithms

std::transform

Applies a function to each element and writes the result to an output range (which can be the same range).

std::vector<int> celsius = {0, 20, 37, 100};
std::vector<double> fahrenheit(celsius.size());

std::transform(celsius.begin(), celsius.end(), fahrenheit.begin(),
    [](int c) { return c * 9.0 / 5.0 + 32; });

// fahrenheit: {32, 68, 98.6, 212}

std::reverse

Reverses elements in-place.

std::vector<int> v = {1, 2, 3, 4, 5};
std::reverse(v.begin(), v.end());
// v: {5, 4, 3, 2, 1}

std::unique

Removes consecutive duplicate elements. It does not shrink the container — it returns an iterator to the new logical end.

std::vector<int> v = {1, 1, 2, 3, 3, 3, 4};
// v must be sorted for unique to remove all duplicates
auto new_end = std::unique(v.begin(), v.end());
v.erase(new_end, v.end());
// v: {1, 2, 3, 4}

---

Numeric Algorithms

std::accumulate

Computes the sum (or any fold) of a range.

#include <numeric>

std::vector<int> salaries = {80000, 120000, 95000, 150000};  // monthly ₹ figures

int total = std::accumulate(salaries.begin(), salaries.end(), 0);
std::cout << "Total payroll: ₹" << total << "\n";

// Product using a custom binary operation
int product = std::accumulate(salaries.begin(), salaries.end(), 1,
    [](int acc, int val) { return acc * val; });

std::max_element and std::min_element

Returns an iterator to the maximum (or minimum) element.

auto max_it = std::max_element(salaries.begin(), salaries.end());
std::cout << "Highest salary: ₹" << *max_it << "\n";

---

Lambda Predicates — The Key to Expressive Algorithms

A lambda is an anonymous function defined inline. With STL algorithms, lambdas replace the need to write separate comparator structs, making code concise and readable.

std::vector<std::string> cities = {"Mumbai", "Delhi", "Bangalore", "Chennai", "Hyderabad"};

// Sort cities by length, then alphabetically for ties
std::sort(cities.begin(), cities.end(), [](const std::string& a, const std::string& b) {
    if (a.size() != b.size()) return a.size() < b.size();
    return a < b;
});

Lambdas can capture variables from the enclosing scope:

int threshold = 100000;  // ₹1 lakh monthly

int high_earners = std::count_if(salaries.begin(), salaries.end(),
    [threshold](int s) { return s >= threshold; });

---

Worked Example: Sorting Employee Structs by Salary Descending

Imagine you are building an HR analytics dashboard for a mid-sized Indian IT company. You receive a list of employees and need to display them sorted by salary — highest first — to identify top earners for the annual appraisal cycle.

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

struct Employee {
    std::string name;
    std::string department;
    double salary;  // annual CTC in ₹ lakhs
};

void printEmployees(const std::vector<Employee>& employees) {
    std::cout << "\n--- Employee Rankings by CTC ---\n";
    std::cout << "Rank  Name                  Dept          CTC (₹ Lakhs)\n";
    std::cout << "----  --------------------  ------------  -------------\n";
    int rank = 1;
    for (const auto& e : employees) {
        std::cout << rank++ << "     "
                  << e.name << std::string(22 - e.name.size(), ' ')
                  << e.department << std::string(14 - e.department.size(), ' ')
                  << e.salary << "\n";
    }
}

int main() {
    std::vector<Employee> employees = {
        {"Priya Sharma",   "Engineering", 28.5},
        {"Rahul Mehta",    "Product",     22.0},
        {"Ananya Iyer",    "Engineering", 35.0},
        {"Vikram Singh",   "Sales",       18.0},
        {"Deepa Nair",     "Engineering", 42.0},
        {"Karthik Rajan",  "Design",      19.5},
        {"Sneha Gupta",    "Product",     31.0},
    };

    // Sort by salary descending using a lambda comparator
    std::sort(employees.begin(), employees.end(),
        [](const Employee& a, const Employee& b) {
            return a.salary > b.salary;  // descending
        });

    printEmployees(employees);

    // Find the highest-paid employee in Engineering
    auto top_engineer = std::find_if(employees.begin(), employees.end(),
        [](const Employee& e) { return e.department == "Engineering"; });

    if (top_engineer != employees.end()) {
        std::cout << "\nTop engineer: " << top_engineer->name
                  << " at ₹" << top_engineer->salary << " lakhs CTC\n";
    }

    // Count employees earning above ₹25 lakhs
    int above_25 = std::count_if(employees.begin(), employees.end(),
        [](const Employee& e) { return e.salary > 25.0; });
    std::cout << above_25 << " employees earn above ₹25 lakhs CTC\n";

    // Total payroll using accumulate
    double total = std::accumulate(employees.begin(), employees.end(), 0.0,
        [](double sum, const Employee& e) { return sum + e.salary; });
    std::cout << "Total annual payroll: ₹" << total << " lakhs\n";

    return 0;
}

Sample output:

--- Employee Rankings by CTC ---
Rank  Name                  Dept          CTC (₹ Lakhs)
----  --------------------  ------------  -------------
1     Deepa Nair             Engineering   42
2     Ananya Iyer            Engineering   35
3     Sneha Gupta            Product       31
4     Priya Sharma           Engineering   28.5
5     Rahul Mehta            Product       22
6     Karthik Rajan          Design        19.5
7     Vikram Singh           Sales         18

Top engineer: Deepa Nair at ₹42 lakhs CTC
4 employees earn above ₹25 lakhs CTC
Total annual payroll: ₹196 lakhs

---

Common Pitfalls

1. Forgetting to sort before binary_search or unique

Both std::binary_search and std::unique only work correctly on sorted ranges. Calling them on an unsorted container produces wrong results silently.

// WRONG — data is not sorted
std::vector<int> v = {3, 1, 2, 1};
auto it = std::unique(v.begin(), v.end());  // only removes adjacent duplicates!

// CORRECT
std::sort(v.begin(), v.end());
auto it2 = std::unique(v.begin(), v.end());
v.erase(it2, v.end());  // now v = {1, 2, 3}

2. Forgetting to erase after std::unique

std::unique does not resize the container. The elements after the returned iterator are in an unspecified state. Always pair it with erase.

3. Passing wrong iterator order

Passing end before begin is undefined behaviour. Always double-check range order.

4. Modifying a container while iterating with remove_if

std::remove_if does not erase elements; it moves unwanted ones to the end and returns a new end iterator. The erase-remove idiom must follow:

v.erase(std::remove_if(v.begin(), v.end(),
    [](int x) { return x < 0; }), v.end());

5. Off-by-one with accumulate initial value

When accumulating into a double or long long, pass the correct typed initial value (0.0, 0LL) to avoid integer overflow or truncation.

---

Practice Exercises

1. Given a vector<int> of exam scores, use std::sort and then print the top 3 scores. Use std::count_if to count how many students scored above the average.

2. Write a program that reads a list of Indian city names, removes duplicate names using the erase-remove idiom with std::unique, and prints the sorted, deduplicated list.

3. Create a struct Product with fields name (string), price (double), and rating (float). Fill a vector with 10 products. Sort the vector first by rating descending, then by price ascending for ties. Use std::max_element to find the highest-rated product.

4. Use std::transform to convert a vector<string> of lowercase words to uppercase (hint: apply std::toupper to each character).

5. Implement a frequency counter: given a vector<int>, use std::count_if in a loop (or std::sort plus std::unique with distance arithmetic) to find the element that appears most often.

6. Using std::accumulate with a lambda, compute the product of all elements in a vector<int> that are greater than 5.

---

Summary

• Iterators model a pointer to a container element; the five categories (input, output, forward, bidirectional, random access) determine which algorithms can be used.
• All STL algorithms operate on half-open ranges [begin, end) and are container-agnostic.
• std::sort needs random access iterators; std::list must use its own .sort() member.
• std::find and std::binary_search search for values; the latter requires a sorted range.
• std::count and std::count_if count occurrences; count_if accepts a predicate.
• std::transform applies a function element-wise; std::reverse reverses in-place.
• std::unique removes consecutive duplicates — always sort first and erase after.
• std::accumulate folds a range into a single value; it lives in <numeric>.
• Lambda expressions make algorithm predicates and comparators concise and readable.
• Capture variables from the enclosing scope in a lambda using [=] (by value) or [&] (by reference).