Standard Template Library

STL Overview

The Standard Template Library provides generic, reusable components.

Container Categories

std::vector

Dynamic array with automatic resizing. The most commonly used container.

Creating Vectors

#include <vector>

std::vector<int> v1;                    // Empty
std::vector<int> v2(5);                 // 5 zeros
std::vector<int> v3(5, 10);             // 5 tens
std::vector<int> v4 = {1, 2, 3, 4, 5};  // Initializer list
std::vector<int> v5(v4);                // Copy
std::vector<int> v6(v4.begin(), v4.end());  // From iterators

Basic Operations

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

// Add elements
v.push_back(4);         // {1, 2, 3, 4}
v.emplace_back(5);      // {1, 2, 3, 4, 5} - constructs in place

// Access
v[0];                   // 1 (no bounds check)
v.at(0);                // 1 (with bounds check)
v.front();              // 1 (first element)
v.back();               // 5 (last element)

// Remove
v.pop_back();           // {1, 2, 3, 4}
v.erase(v.begin());     // {2, 3, 4}
v.clear();              // {}

// Size
v.size();               // Number of elements
v.capacity();           // Allocated storage
v.empty();              // true if empty
v.resize(10);           // Change size
v.reserve(100);         // Pre-allocate (no resize)

Iterating

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

// Range-based for (preferred)
for (int x : v) {
    std::cout << x << " ";
}

// With reference to modify
for (int& x : v) {
    x *= 2;
}

// Iterator-based
for (auto it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << " ";
}

// Index-based
for (size_t i = 0; i < v.size(); i++) {
    std::cout << v[i] << " ";
}

Insertion and Deletion

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

// Insert at position
v.insert(v.begin() + 2, 10);     // {1, 2, 10, 3, 4, 5}
v.insert(v.end(), {6, 7, 8});    // {1, 2, 10, 3, 4, 5, 6, 7, 8}

// Erase range
v.erase(v.begin(), v.begin() + 3);  // Remove first 3

// Remove-erase idiom (remove all 3s)
v.erase(std::remove(v.begin(), v.end(), 3), v.end());

2D Vector

// Create 3x4 matrix filled with zeros
std::vector<std::vector<int>> matrix(3, std::vector<int>(4, 0));

// Access
matrix[1][2] = 5;

// Add row
matrix.push_back({1, 2, 3, 4});

// Iterate
for (const auto& row : matrix) {
    for (int val : row) {
        std::cout << val << " ";
    }
    std::cout << "\n";
}

std::list and std::forward_list

Doubly-linked (list) and singly-linked (forward_list) lists.

std::list

#include <list>

std::list<int> lst = {1, 2, 3, 4, 5};

// Efficient insertion/deletion anywhere
lst.push_front(0);          // {0, 1, 2, 3, 4, 5}
lst.push_back(6);           // {0, 1, 2, 3, 4, 5, 6}

auto it = lst.begin();
std::advance(it, 3);        // Move iterator
lst.insert(it, 99);         // Insert before position

// No random access!
// lst[0];                  // Error!

// Special list operations
lst.reverse();              // Reverse in place
lst.sort();                 // Sort
lst.unique();               // Remove consecutive duplicates

// Merge sorted lists
std::list<int> other = {10, 20, 30};
lst.merge(other);           // other is now empty

std::forward_list (C++11)

#include <forward_list>

std::forward_list<int> flist = {1, 2, 3, 4, 5};

// Only forward iteration
flist.push_front(0);
flist.insert_after(flist.begin(), 99);  // Insert after position

// More memory efficient than list
// No size() method (use std::distance)

When to Use

• vector: Random access, mostly add to end
• list: Frequent insert/delete in middle
• forward_list: Memory-constrained, forward iteration only

std::deque

Double-ended queue with efficient insertion at both ends.

#include <deque>

std::deque<int> dq = {2, 3, 4};

// Efficient at both ends
dq.push_front(1);     // {1, 2, 3, 4}
dq.push_back(5);      // {1, 2, 3, 4, 5}
dq.pop_front();       // {2, 3, 4, 5}
dq.pop_back();        // {2, 3, 4}

// Random access (like vector)
dq[0] = 10;
dq.at(1) = 20;

// Unlike vector, doesn't invalidate iterators
// when adding at front

std::stack and std::queue

Container adapters that restrict the interface.

std::stack (LIFO)

#include <stack>

std::stack<int> stk;

// Add/remove from top
stk.push(1);
stk.push(2);
stk.push(3);

stk.top();      // 3 (peek)
stk.pop();      // Remove 3
stk.top();      // 2

stk.empty();    // false
stk.size();     // 2

std::queue (FIFO)

#include <queue>

std::queue<int> q;

// Add to back, remove from front
q.push(1);
q.push(2);
q.push(3);

q.front();      // 1 (first in)
q.back();       // 3 (last in)
q.pop();        // Remove 1
q.front();      // 2

std::priority_queue

#include <queue>

// Max-heap by default
std::priority_queue<int> maxPQ;
maxPQ.push(3);
maxPQ.push(1);
maxPQ.push(4);
maxPQ.top();    // 4 (largest)

// Min-heap
std::priority_queue<int, std::vector<int>, std::greater<int>> minPQ;
minPQ.push(3);
minPQ.push(1);
minPQ.push(4);
minPQ.top();    // 1 (smallest)

std::set and std::multiset

Sorted containers with unique (set) or duplicate (multiset) elements.

std::set

#include <set>

std::set<int> s = {3, 1, 4, 1, 5, 9};  // {1, 3, 4, 5, 9} - sorted, unique

// Insert
s.insert(2);        // {1, 2, 3, 4, 5, 9}
s.insert(3);        // No effect (already exists)

// Check membership
if (s.count(4)) {
    std::cout << "Found\n";
}

// C++20: contains()
if (s.contains(4)) { /* ... */ }

// Find
auto it = s.find(4);
if (it != s.end()) {
    std::cout << *it << "\n";
}

// Erase
s.erase(3);         // Remove 3
s.erase(s.begin()); // Remove first

// Bounds
s.lower_bound(4);   // First element >= 4
s.upper_bound(4);   // First element > 4

std::multiset

#include <set>

std::multiset<int> ms = {1, 2, 2, 3, 3, 3};

ms.count(3);        // 3 (occurrences)
ms.erase(3);        // Removes ALL 3s

// Remove only one occurrence
auto it = ms.find(2);
if (it != ms.end()) {
    ms.erase(it);   // Removes one 2
}

Custom Comparison

// Descending order
std::set<int, std::greater<int>> descSet = {1, 5, 3};
// {5, 3, 1}

// Custom comparator
struct Person {
    std::string name;
    int age;
};

auto cmp = [](const Person& a, const Person& b) {
    return a.age < b.age;
};
std::set<Person, decltype(cmp)> people(cmp);

std::map and std::multimap

Sorted key-value containers.

std::map

#include <map>

std::map<std::string, int> ages;

// Insert
ages["Alice"] = 30;
ages["Bob"] = 25;
ages.insert({"Charlie", 35});
ages.emplace("Dave", 28);

// Access
std::cout << ages["Alice"];     // 30
std::cout << ages.at("Bob");    // 25 (throws if not found)

// Check existence
if (ages.count("Eve") == 0) {
    std::cout << "Eve not found\n";
}

// Iterate (sorted by key)
for (const auto& [name, age] : ages) {  // C++17 structured binding
    std::cout << name << ": " << age << "\n";
}

// Find
auto it = ages.find("Charlie");
if (it != ages.end()) {
    std::cout << it->first << ": " << it->second << "\n";
}

// Erase
ages.erase("Bob");

std::multimap

#include <map>

std::multimap<std::string, int> scores;
scores.insert({"Alice", 100});
scores.insert({"Alice", 95});   // Same key, different value
scores.insert({"Alice", 88});

// Get all values for a key
auto range = scores.equal_range("Alice");
for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->second << " ";  // 100 95 88
}

Useful Patterns

// Word frequency counter
std::map<std::string, int> wordCount;
std::vector<std::string> words = {"apple", "banana", "apple"};

for (const auto& word : words) {
    wordCount[word]++;  // Auto-creates with 0, then increments
}
// {"apple": 2, "banana": 1}

// Group by category
std::map<char, std::vector<std::string>> byFirstLetter;
byFirstLetter['A'].push_back("Apple");
byFirstLetter['A'].push_back("Avocado");
byFirstLetter['B'].push_back("Banana");

Unordered Containers

Hash-based containers with O(1) average time complexity.

std::unordered_set

#include <unordered_set>

std::unordered_set<int> us = {3, 1, 4, 1, 5};  // No guaranteed order

us.insert(2);
us.count(4);        // 1 or 0
us.find(4);         // Iterator or end()
us.erase(3);

// Hash table info
us.bucket_count();  // Number of buckets
us.load_factor();   // Elements per bucket ratio

std::unordered_map

#include <unordered_map>

std::unordered_map<std::string, int> um;

um["one"] = 1;
um["two"] = 2;

// Same interface as map, but:
// - No ordering
// - O(1) average lookup
// - O(n) worst case (hash collisions)

Custom Hash

struct Point {
    int x, y;
    
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

struct PointHash {
    size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

std::unordered_set<Point, PointHash> points;
std::unordered_map<Point, std::string, PointHash> pointNames;

When to Use

Iterators

Iterators provide a uniform way to traverse containers.

Iterator Types

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

// begin/end - normal iteration
auto it = v.begin();    // Points to first element
auto end = v.end();     // Points past last element

// rbegin/rend - reverse iteration
auto rit = v.rbegin();  // Points to last element
auto rend = v.rend();   // Points before first element

// cbegin/cend - const iteration (C++11)
auto cit = v.cbegin();  // Can't modify elements

// Iterate forward
for (auto it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << " ";
}

// Iterate backward
for (auto it = v.rbegin(); it != v.rend(); ++it) {
    std::cout << *it << " ";
}

Iterator Categories

// Input Iterator: Read, single-pass (istream_iterator)
// Output Iterator: Write, single-pass (ostream_iterator)
// Forward Iterator: Read/write, multi-pass (forward_list)
// Bidirectional Iterator: + backwards (list, set, map)
// Random Access Iterator: + arithmetic (vector, deque, array)

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

// Random access operations (vector, deque)
it += 3;        // Jump forward
it -= 1;        // Jump backward
it[2];          // Access relative element
auto diff = v.end() - v.begin();  // Distance

// Bidirectional only (list, set, map)
++it;           // Forward
--it;           // Backward

// Forward only
++it;           // Forward only

Iterator Helpers

#include <iterator>

std::list<int> lst = {1, 2, 3, 4, 5};
auto it = lst.begin();

std::advance(it, 3);          // Move it forward 3 positions
int dist = std::distance(lst.begin(), it);  // 3

auto next_it = std::next(it, 2);    // Return iterator 2 ahead
auto prev_it = std::prev(it, 1);    // Return iterator 1 behind

Stream Iterators

#include <iterator>

// Output iterator
std::ostream_iterator<int> out(std::cout, " ");
*out++ = 1;     // Prints "1 "
*out++ = 2;     // Prints "2 "

// Input iterator
std::istream_iterator<int> in(std::cin);
std::istream_iterator<int> eof;

std::vector<int> nums(in, eof);  // Read until EOF

// Copy vector to cout
std::copy(v.begin(), v.end(), 
          std::ostream_iterator<int>(std::cout, " "));

Algorithms

Generic algorithms that work with any container through iterators.

Searching

#include <algorithm>

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

// Find element
auto it = std::find(v.begin(), v.end(), 5);
if (it != v.end()) {
    std::cout << "Found: " << *it << "\n";
}

// Find with predicate
auto it2 = std::find_if(v.begin(), v.end(), [](int x) {
    return x > 6;
});

// Count
int count = std::count(v.begin(), v.end(), 5);
int count_if = std::count_if(v.begin(), v.end(), [](int x) {
    return x % 2 == 0;
});

// All/any/none
bool all = std::all_of(v.begin(), v.end(), [](int x) { return x > 0; });
bool any = std::any_of(v.begin(), v.end(), [](int x) { return x > 5; });
bool none = std::none_of(v.begin(), v.end(), [](int x) { return x < 0; });

// Binary search (requires sorted range)
std::sort(v.begin(), v.end());
bool found = std::binary_search(v.begin(), v.end(), 5);
auto lb = std::lower_bound(v.begin(), v.end(), 5);
auto ub = std::upper_bound(v.begin(), v.end(), 5);

Sorting

std::vector<int> v = {5, 2, 8, 1, 9, 3};

// Sort ascending
std::sort(v.begin(), v.end());

// Sort descending
std::sort(v.begin(), v.end(), std::greater<int>());

// Stable sort (preserves order of equal elements)
std::stable_sort(v.begin(), v.end());

// Partial sort (only sort first N elements)
std::partial_sort(v.begin(), v.begin() + 3, v.end());

// Nth element (find median, etc.)
std::nth_element(v.begin(), v.begin() + v.size()/2, v.end());

// Custom comparison
std::vector<std::string> words = {"apple", "Banana", "cherry"};
std::sort(words.begin(), words.end(), [](const auto& a, const auto& b) {
    return a.size() < b.size();  // Sort by length
});

Modifying

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

// Transform
std::transform(v.begin(), v.end(), v.begin(), [](int x) {
    return x * 2;
});  // {2, 4, 6, 8, 10}

// Replace
std::replace(v.begin(), v.end(), 4, 40);  // Replace 4s with 40
std::replace_if(v.begin(), v.end(), 
    [](int x) { return x > 5; }, 0);  // Replace if > 5 with 0

// Remove (doesn't actually remove, returns new end)
auto new_end = std::remove(v.begin(), v.end(), 2);
v.erase(new_end, v.end());  // Actually remove

// Unique (remove consecutive duplicates)
std::sort(v.begin(), v.end());
auto uniq_end = std::unique(v.begin(), v.end());
v.erase(uniq_end, v.end());

// Reverse
std::reverse(v.begin(), v.end());

// Rotate
std::rotate(v.begin(), v.begin() + 2, v.end());  // Move first 2 to end

// Shuffle
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(v.begin(), v.end(), g);

Copying and Moving

std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst(5);

// Copy
std::copy(src.begin(), src.end(), dst.begin());

// Copy with condition
std::copy_if(src.begin(), src.end(), std::back_inserter(dst),
    [](int x) { return x % 2 == 0; });

// Copy N elements
std::copy_n(src.begin(), 3, dst.begin());

// Move
std::vector<std::string> strings = {"hello", "world"};
std::vector<std::string> moved(2);
std::move(strings.begin(), strings.end(), moved.begin());

Numeric Algorithms

#include <numeric>

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

// Sum
int sum = std::accumulate(v.begin(), v.end(), 0);  // 15

// Product
int product = std::accumulate(v.begin(), v.end(), 1, 
    std::multiplies<int>());  // 120

// Inner product
std::vector<int> w = {1, 2, 3, 4, 5};
int dot = std::inner_product(v.begin(), v.end(), w.begin(), 0);

// Partial sum
std::vector<int> prefix(5);
std::partial_sum(v.begin(), v.end(), prefix.begin());
// {1, 3, 6, 10, 15}

// Adjacent difference
std::vector<int> diff(5);
std::adjacent_difference(v.begin(), v.end(), diff.begin());
// {1, 1, 1, 1, 1}

// Iota (fill with increasing values)
std::iota(v.begin(), v.end(), 10);  // {10, 11, 12, 13, 14}

Min/Max

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

// Min/Max element
auto min_it = std::min_element(v.begin(), v.end());
auto max_it = std::max_element(v.begin(), v.end());

// Minmax (both at once)
auto [min, max] = std::minmax_element(v.begin(), v.end());

// Values directly
int a = 5, b = 3;
int minimum = std::min(a, b);
int maximum = std::max(a, b);
auto [lo, hi] = std::minmax(a, b);

// Clamp (C++17)
int clamped = std::clamp(10, 0, 5);  // 5 (clamped to range)

Function Objects (Functors)

Objects that can be called like functions.

Standard Functors

#include <functional>

// Arithmetic
std::plus<int>()(5, 3);        // 8
std::minus<int>()(5, 3);       // 2
std::multiplies<int>()(5, 3);  // 15
std::divides<int>()(6, 3);     // 2
std::modulus<int>()(5, 3);     // 2
std::negate<int>()(5);         // -5

// Comparison
std::less<int>()(3, 5);         // true
std::greater<int>()(3, 5);      // false
std::equal_to<int>()(3, 3);     // true

// Logical
std::logical_and<bool>()(true, false);  // false
std::logical_or<bool>()(true, false);   // true
std::logical_not<bool>()(true);          // false

Custom Functors

class Multiplier {
private:
    int factor;
public:
    Multiplier(int f) : factor(f) {}
    
    int operator()(int x) const {
        return x * factor;
    }
};

std::vector<int> v = {1, 2, 3, 4, 5};
std::transform(v.begin(), v.end(), v.begin(), Multiplier(3));
// {3, 6, 9, 12, 15}

std::function

#include <functional>

// Holds any callable
std::function<int(int, int)> op;

op = [](int a, int b) { return a + b; };
std::cout << op(5, 3);  // 8

op = std::multiplies<int>();
std::cout << op(5, 3);  // 15

int multiply(int a, int b) { return a * b; }
op = multiply;
std::cout << op(5, 3);  // 15

std::bind

#include <functional>

int subtract(int a, int b) { return a - b; }

// Bind first argument
auto sub5 = std::bind(subtract, 5, std::placeholders::_1);
std::cout << sub5(3);  // 5 - 3 = 2

// Swap argument order
auto reverse_sub = std::bind(subtract, std::placeholders::_2, 
                                        std::placeholders::_1);
std::cout << reverse_sub(5, 3);  // 3 - 5 = -2

// Prefer lambdas in modern C++
auto sub5_lambda = [](int x) { return subtract(5, x); };

Ranges (C++20)

A modern, composable approach to algorithms.

#include <ranges>

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

// Views are lazy and composable
auto result = v 
    | std::views::filter([](int n) { return n % 2 == 0; })
    | std::views::transform([](int n) { return n * n; })
    | std::views::take(3);

// result: 4, 16, 36 (first 3 even numbers squared)

for (int x : result) {
    std::cout << x << " ";
}

// Range-based algorithms
std::ranges::sort(v);
auto it = std::ranges::find(v, 5);
int count = std::ranges::count_if(v, [](int x) { return x > 5; });

// Views
std::views::iota(1, 10);        // 1, 2, 3, ..., 9
std::views::reverse(v);         // Reversed view
std::views::drop(v, 3);         // Skip first 3
std::views::take(v, 3);         // Take first 3