C++ STL Expansion Guide
Algorithms (<algorithm>) and Iterators (<iterator>)
Iterators ()
Iterators are objects that point to elements within containers. They act as a bridge between containers
and algorithms. Instead of writing separate algorithms for vectors, lists, and maps, C++ algorithms use
iterators to access and traverse elements uniformly regardless of the underlying data structure.
Properties
• Act like pointers: can be dereferenced (*) and incremented (++).
• 5 Main Categories: Input, Output, Forward, Bidirectional, and Random Access iterators.
• Containers provide begin() (points to the first element) and end() (points one past the last
element).
• Support reverse traversal via rbegin() and rend() (Reverse Iterators).
C++ Syntax
std::vector::iterator it = [Link]();
auto it = [Link](); // Modern C++ preference
Essential Functions
std::advance(it, n): Moves the iterator forward (or backward) by n elements.
std::distance(first, last): Returns the number of elements between two
iterators.
std::next(it, n): Returns a new iterator advanced by n positions.
std::prev(it, n): Returns a new iterator decremented by n positions.
inserter(container, it): Creates an output iterator that inserts into a
container.
Common Programming Problems
1. Flatten 2D Vector
Design an iterator to flatten a 2D vector (a vector of vectors).
class Vector2D {
vector<vector<int>>::iterator row, end_row;
int col = 0;
public:
Vector2D(vector<vector<int>>& vec) {
row = [Link]();
end_row = [Link]();
}
int next() {
hasNext(); // Ensure we are at a valid element
return (*row)[col++];
}
bool hasNext() {
2. Peeking Iterator
Design an iterator that supports the peek operation on a list in addition to the hasNext and the next
operations.
class PeekingIterator : public Iterator {
int next_val;
bool has_next;
public:
PeekingIterator(const vector<int>& nums) : Iterator(nums) {
has_next = Iterator::hasNext();
if (has_next) next_val = Iterator::next();
}
int peek() {
return next_val;
}
int next() {
int curr = next_val;
has_next = Iterator::hasNext();
if (has_next) next_val = Iterator::next();
return curr;
}
bool hasNext() const {
return has_next;
}
};
3. Valid Palindrome (using Reverse Iterators)
Check if a string is a palindrome. Iterators make this remarkably concise.
bool isPalindrome(string s) {
// A palindrome reads the same forwards and backwards.
Overview: Iterators are the glue of the STL. By mastering iterators, you decouple your algorithms
from your data structures. Always prefer using 'auto' for iterator types to keep code clean, and rely
on standard iterator functions like std::distance and std::advance instead of raw pointer arithmetic.
Algorithms ()
The library provides a vast collection of functions designed to be used on ranges of elements. These
algorithms operate using iterators, meaning a single algorithm (like std::sort) can be used on vectors,
arrays, deques, and custom data structures.
Properties
• Operates on half-open intervals [first, last) meaning the 'last' element is not included.
• Does not generally change the size of the container (exceptions exist when using inserters).
• Highly optimized by compiler vendors (e.g., IntroSort used for std::sort).
• Can accept custom comparators (lambdas) to modify behavior.
C++ Syntax
std::sort([Link](), [Link]());
std::sort([Link](), [Link](), custom_comparator);
Essential Functions
std::sort(first, last): Sorts the range in ascending order. O(N log N).
std::lower_bound(first, last, val): Binary search. Returns iterator to first
element >= val.
std::upper_bound(first, last, val): Binary search. Returns iterator to first
element > val.
std::reverse(first, last): Reverses the order of elements in the range.
std::next_permutation(first, last): Rearranges elements into the next
lexicographically greater permutation.
std::nth_element(first, nth, last): Partially sorts so the nth element is in its
correct sorted position. O(N).
Common Programming Problems
1. Find First and Last Position of Element in Sorted Array
Find the starting and ending position of a given target value. Solved purely with STL binary search
functions.
vector<int> searchRange(vector<int>& nums, int target) {
// lower_bound finds the first element >= target
auto it1 = lower_bound([Link](), [Link](), target);
2. Permutations
Given an array of distinct integers, return all the possible permutations.
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
// Sort the array to start from the lexicographically smallest permutation
sort([Link](), [Link]());
3. Kth Largest Element in an Array (O(N) Time)
Find the kth largest element in an unsorted array. std::nth_element solves this in O(N) average time.
int findKthLargest(vector<int>& nums, int k) {
// nth_element partially sorts the array such that the element at
Overview: The library is arguably the most powerful part of C++. Before writing a raw loop for
searching, counting, sorting, or modifying data, check if an STL algorithm already exists. It will
almost always be faster, safer, and more readable than manual implementations.