Chapter 16: STL: Iterators and Algorithms in C++

Previous chapter: Chapter 15: Standard Template Library (STL): Containers in C++

While containers (Chapter 15) store data, Iterators and Algorithms are the mechanisms that make the STL truly powerful, allowing you to manipulate the data stored in those containers efficiently and uniformly.

1. Iterators: The General Pointer

An iterator is a concept in C++ that acts like a generic pointer. It abstracts the method of accessing elements in a container, allowing algorithms to work on any container type (vector, list, map, etc.) without knowing the container's internal structure.

Key Iterator Functions

Every STL container provides methods to get iterators:

Function	Description
.begin()	Returns an iterator pointing to the first element.
.end()	Returns an iterator pointing to one position past the last element.

Using Iterators to Traverse

Iterators are manipulated using standard pointer operators: * (dereference) and ++ (move to the next element).

#include <vector>

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

// Iterate and print using an iterator
for (auto it = data.begin(); it != data.end(); ++it) {
    std::cout << *it << " "; // Dereference to get the value
}
// Output: 1 2 3 4

2. STL Algorithms

Algorithms are generic functions (defined in the <algorithm> header) that perform common operations on ranges of elements, defined by a pair of iterators (a beginning and an end).

Algorithm	Description	Example
std::sort	Sorts a range of elements.	std::sort(v.begin(), v.end());
std::find	Finds the first occurrence of a value.	auto it = std::find(v.begin(), v.end(), 5);
std::reverse	Reverses the order of elements.	std::reverse(v.begin(), v.end());
std::copy	Copies elements from one range to another.	std::copy(v1.begin(), v1.end(), v2.begin());

Example: Sorting a Vector

#include <algorithm>
#include <vector>

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

std::sort(numbers.begin(), numbers.end());

// numbers is now {1, 2, 5, 8}

3. Range-based `for` Loop (Modern C++)

For simple traversal, C++ offers the range-based for loop, which implicitly uses iterators but provides much cleaner syntax:

std::vector<std::string> names = {"Amy", "Ben", "Carl"};

// Read as: for each element (name) in names
for (const std::string& name : names) {
    std::cout << name << std::endl;
}

4. Customizing Algorithms with Lambda Functions

Many algorithms (like std::sort) accept a custom function or a Lambda Function to define specific comparison logic. Lambda functions are small, unnamed functions defined inline, making them incredibly powerful for generic programming.

// Sorts numbers in descending order using a lambda
std::sort(numbers.begin(), numbers.end(), [](int a, int b) {
    return a > b; // Custom logic: true if 'a' should come before 'b'
});