5 The C++ Standard Library

The C++ Standard Library: Containers, Iterators, Algorithms, Tuples, Function Objects and Other Useful Features
Author

Daniel Schwarzenbach

Containers

The STL provides a variety of containers to store and manage collections of elements. Different containers have different properties — choosing the right one is essential for performance.

Container Structure Access Insert/Delete
array fixed array O(1) random —
vector dynamic array O(1) random O(1) back, O(n) middle
deque double-ended queue O(1) random O(1) front & back
list doubly linked list O(n) O(1) anywhere
forward_list singly linked list O(n) O(1) after iterator
set sorted BST O(log n) O(log n)
unordered_set hash table O(1) avg O(1) avg
map sorted BST O(log n) O(log n)
unordered_map hash table O(1) avg O(1) avg

However this chart is kind of a lie since it does not account for cache coherence and memory locality. For example, a vector is usually much faster than a list for iterating over elements, even though the list has O(1) access time for each element. Thats why there is almost no reason to use a list in modern C++. Even inserting and deleting elements in a vector is usually faster than in a list, because the vector is more cache friendly. Only use a list if you constantly need to insert and delete elements from a very large collection of elements and you don’t care about iterating over them.

Iterators allow algorithms to work on any container uniformly, independent of element layout in memory.

list and forward_list

list implements a doubly linked list: elements are not contiguous in memory, so pointer arithmetic doesn’t work, but insertion and deletion anywhere are O(1).

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

int main() {
    list<string> poem;
    poem.push_back("i");                      // [i]
    auto it = poem.begin();
    poem.insert(it, "ends");                  // [ends, i]
    poem.insert(it, "with");                  // [ends, with, i]
    poem.push_front("pi");                    // [pi, ends, with, i]

    for (const string& word : poem)
        cout << word << ' ';                  // pi ends with i
}

forward_list is a singly linked list — slightly more memory-efficient, but can only iterate forward. It uses insert_after instead of insert.

#include <forward_list>
forward_list<int> fl = {1, 2, 3};
fl.push_front(0);
fl.insert_after(fl.begin(), 10);  // {0, 10, 1, 2, 3}
  • Advantage: Fast O(1) insertion and deletion at any position.
  • Disadvantage: No random access — can’t do fl[2].

set and unordered_set

set stores unique elements in sorted order, typically implemented as a red-black tree. Elements cannot be mutated in-place.

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

int main() {
    set<string> s = {"pi", "ends", "with", "i", "and", "not", "with", "y"};
    // "with" is only inserted once — sets store unique elements

    for (const string& word : s)
        cout << word << ' ';   // and ends i not pi with y  (sorted!)
}

unordered_set uses a hash table instead of a tree — O(1) average lookup but no guaranteed ordering.

#include <unordered_set>
unordered_set<int> us = {3, 1, 4, 1, 5, 9};
// stores {1, 3, 4, 5, 9} in unspecified order
cout << us.count(4);  // 1 (found)
cout << us.count(7);  // 0 (not found)

Use set when you need sorted iteration. Use unordered_set when you only need fast membership checks.

map and unordered_map

map stores unique key-value pairs in sorted key order, implemented as a red-black tree.

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

int main() {
    map<string, int> wordcount;
    vector<string> poem = {"pi", "ends", "with", "i", "and", "not", "with", "y"};

    for (const string& word : poem)
        ++wordcount[word];     // inserts 0 if key not present, then increments

    // classic iterator access
    for (auto it = wordcount.begin(); it != wordcount.end(); ++it)
        cout << it->first << ": " << it->second << "\n";

    // modern structured binding (C++17)
    for (const auto& [key, value] : wordcount)
        cout << key << ": " << value << "\n";
}

unordered_map uses hashing for O(1) average access — prefer it when ordering doesn’t matter.

#include <unordered_map>
unordered_map<string, int> scores;
scores["alice"] = 95;
scores["bob"]   = 87;
cout << scores["alice"];  // 95

pair, tuple, and optional

pair groups two values of (possibly different) types:

#include <utility>
pair<int, string> id_name = make_pair(1, "bob");
cout << id_name.second << " has ID " << id_name.first << "\n";

// C++17 structured binding
auto [num, name] = id_name;

tuple generalizes pair to any fixed number of elements:

#include <tuple>
// chess move: piece, from-col, from-row, to-col, to-row
tuple<char, char, int, char, int> move('K', 'c', 1, 'd', 2);
cout << "Piece: " << get<0>(move) << "\n";

// structured binding (C++17)
auto [piece, fc, fr, tc, tr] = move;

optional avoids sentinel values like -1 or nullptr for “no result”:

#include <optional>
optional<int> find_index(const vector<int>& v, int x) {
    for (int i = 0; i < (int)v.size(); ++i)
        if (v[i] == x) return i;
    return nullopt;
}

if (auto idx = find_index(v, 30); idx.has_value())
    cout << "Found at index " << *idx << "\n";

Iterators

An iterator is an object that abstracts traversal over a container’s elements — similar to a pointer, but works for any container regardless of how elements are laid out in memory.

All STL containers provide iterators via .begin() and .end(). begin() points to the first element; end() points one past the last (a sentinel).

vector<int> v = {2, 3, 7, 11, 13};
for (auto it = v.begin(); it != v.end(); ++it)
    cout << *it << ' ';

// same pattern works for set — no index-based access possible here
set<string> s = {"hello", "cruel", "world"};
for (auto it = s.begin(); it != s.end(); ++it)
    cout << *it << ' ';

Range-based for loops are syntactic sugar over iterators:

for (auto num : v) { cout << num; }
// expands to:
for (auto it = v.begin(); it != v.end(); ++it) {
    auto num = *it;
    cout << num;
}

Iterator Categories

There are five iterator categories, each a superset of the previous:

# Category Extra Operations Supported by
1 Input =*it, ++it istream_iterator
2 Output *it=, ++it ostream_iterator
3 Forward *, ->, ++, ==, != forward_list, unordered_set
4 Bidirectional adds -- list, map, set
5 Random Access adds +, -, [], <, > array, vector, string, deque

Adapters (stack, queue, priority_queue) expose no iterators at all.

Algorithms declare which category they require: - find, count → Input Iterator - replace, min_element → Forward Iterator - reverse → Bidirectional Iterator - sort, random_shuffle → Random Access Iterator

Reverse and const Iterators

Containers also provide rbegin()/rend() for reverse traversal and cbegin()/cend() for read-only access:

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

for (auto it = v.rbegin(); it != v.rend(); ++it)
    cout << *it << ' ';   // 5 4 3 2 1

// const iterator — cannot modify elements
for (auto it = v.cbegin(); it != v.cend(); ++it)
    cout << *it << ' ';

Algorithms

The <algorithm> header provides over 100 generic algorithms that operate on iterator ranges, independent of the container type.

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

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

    // searching
    auto it = find(v.begin(), v.end(), 8);
    if (it != v.end())
        cout << "found 8 at index " << distance(v.begin(), it) << '\n';

    cout << "min: " << *min_element(v.begin(), v.end()) << '\n';
    cout << "max: " << *max_element(v.begin(), v.end()) << '\n';
    cout << "count of 3: " << count(v.begin(), v.end(), 3) << '\n';

    // sorting
    sort(v.begin(), v.end());
    for (int x : v) cout << x << ' ';   // 1 2 3 5 7 8 9
}
// transforming and filtering
reverse(v.begin(), v.end());
replace(v.begin(), v.end(), 5, 50);

// erase-remove idiom — removes all 4s in-place
v.erase(remove(v.begin(), v.end(), 4), v.end());

// copy elements matching a predicate into another container
vector<int> evens;
copy_if(v.begin(), v.end(), back_inserter(evens),
        [](int x) { return x % 2 == 0; });

Sorting with Custom Comparators

sort accepts a comparison function or lambda as a third argument:

vector<string> words = {"banana", "fig", "apple", "cherry", "kiwi"};

// sort by length, then alphabetically within same length
sort(words.begin(), words.end(), [](const string& a, const string& b) {
    if (a.size() != b.size()) return a.size() < b.size();
    return a < b;
});
// fig kiwi apple banana cherry

Tuples

tuple is a fixed-size heterogeneous collection. Beyond basic usage, tuples support lexicographic comparison and concatenation via tuple_cat.

A common use case is returning multiple values from a function cleanly:

#include <tuple>
#include <string>
using namespace std;

tuple<bool, int, string> parse_result(const string& input) {
    if (input.empty()) return {false, 0, "empty input"};
    return {true, (int)input.size(), input};
}

int main() {
    auto [ok, len, text] = parse_result("hello");
    if (ok) cout << '"' << text << "\" (" << len << " chars)\n";

    // tuple comparison is lexicographic
    auto t1 = make_tuple(1, "abc");
    auto t2 = make_tuple(1, "xyz");
    cout << (t1 < t2 ? "t1 < t2" : "t1 >= t2") << '\n';

    // concatenate two tuples
    auto t3 = tuple_cat(make_tuple(1, 2), make_tuple("three", 4.0));
    cout << get<2>(t3) << '\n';   // "three"
}

Function Objects

A function object (or functor) is any type that overloads operator(). They can carry state unlike plain function pointers, and the compiler can inline them efficiently.

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

struct Adder {
    int n;
    Adder(int n) : n(n) {}
    int operator()(int x) const { return x + n; }
};

int main() {
    vector<int> v = {1, 2, 3, 4, 5};
    transform(v.begin(), v.end(), v.begin(), Adder(10));
    // v = {11, 12, 13, 14, 15}
}

Lambda Expressions

Lambdas (C++11) are anonymous function objects defined inline. They can capture variables from the enclosing scope:

[capture](parameters) -> return_type { body }
Capture Meaning
[] capture nothing
[=] capture all by value
[&] capture all by reference
[x, &y] x by value, y by reference 
int threshold = 5;
vector<int> v = {1, 7, 3, 9, 2, 6, 4};

// capture threshold by value
auto big = count_if(v.begin(), v.end(),
                    [threshold](int x) { return x > threshold; });

// accumulate sum by reference capture
int total = 0;
for_each(v.begin(), v.end(), [&total](int x) { total += x; });

// sort descending
sort(v.begin(), v.end(), [](int a, int b) { return a > b; });

Standard Function Objects (<functional>)

The STL ships ready-made function objects for common operations:

#include <functional>
#include <numeric>

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

int product = accumulate(v.begin(), v.end(), 1, multiplies<int>());

Other Useful Features

Regular Expressions (<regex>)

Regular expressions describe flexible text patterns — useful for validation, search, and substitution.

Pattern Syntax Reference

Pattern Matches
. any single character
\d / \D digit / non-digit
\w / \W word char / non-word char
\s / \S whitespace / non-whitespace
a* zero or more a
a+ one or more a
a? zero or one a
a{2,4} two to four a
[abc] a, b, or c
[^abc] anything except a, b, c
[a-z] any lowercase letter
^ / $ start / end of string
\| alternation (or)
(...) capturing group

+ and * match as many characters as possible (greedy). Use +? / *? for non-greedy matching.

Examples

regex r;
r = {"\\d*\\.?\\d+"};    // decimal number with optional decimal point
r = {"\\w+\\.txt"};      // text filename
r = {"[a-h][1-8]"};      // valid chess square
r = {"[A-Z][a-z]*"};     // word with uppercase first letter
r = {"\\d|\\."};         // digit or "."
r = {"^a"};              // "a" at the start
r = {"a$"};              // "a" at the end

Using regex_match, regex_search, regex_replace

#include <iostream>
#include <regex>
#include <string>
using namespace std;

int main() {
    // regex_match: the whole string must match
    regex email{R"(\w+@\w+\.\w+)"};
    cout << regex_match("user@example.com", email) << '\n';  // 1
    cout << regex_match("not-an-email",     email) << '\n';  // 0

    // regex_search: find a match anywhere in the string
    string log = "Error 404: file not found";
    smatch m;
    if (regex_search(log, m, regex{R"(\d+)"}))
        cout << "First number: " << m[0] << '\n';   // 404

    // regex_replace: substitute all matches
    string code = "hello world hello cpp hello";
    cout << regex_replace(code, regex{"hello"}, "hi") << '\n';
    // hi world hi cpp hi
}

Iterating Over All Matches

string text = "alle meine entchen";
regex word{R"(\w+)"};

for (sregex_iterator it(text.begin(), text.end(), word);
     it != sregex_iterator{}; ++it)
    cout << (*it)[0] << '\n';   // alle / meine / entchen

Capturing Groups

regex date{R"((\d{4})-(\d{2})-(\d{2}))"};
smatch match;
if (regex_search("Today is 2024-08-13.", match, date)) {
    cout << "Year: "  << match[1] << '\n';   // 2024
    cout << "Month: " << match[2] << '\n';   // 08
    cout << "Day: "   << match[3] << '\n';   // 13
}

Numeric Algorithms (<numeric>)

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

int main() {
    vector<int> v(7);
    iota(v.begin(), v.end(), 1);             // fill: 1,2,3,4,5,6,7

    int sum  = accumulate(v.begin(), v.end(), 0);
    int prod = accumulate(v.begin(), v.end(), 1, multiplies<int>());
    cout << "Sum:     " << sum  << '\n';    // 28
    cout << "Product: " << prod << '\n';    // 5040

    cout << "GCD: " << gcd(12, 18) << '\n';      // 6
    cout << "LCM: " << lcm(12, 18) << '\n';      // 36
    cout << "Mid: " << midpoint(3, 15) << '\n';  // 9

    // prefix sums
    vector<int> ps(v.size());
    partial_sum(v.begin(), v.end(), ps.begin());
    // ps = 1 3 6 10 15 21 28
}

reduce works like accumulate but can evaluate out of order, enabling parallelism:

#include <numeric>
#include <execution>

// sequential, out-of-order accumulation
int sum = reduce(v.begin(), v.end(), 0);

// parallel (requires linking -ltbb on Linux)
sum = reduce(execution::par_unseq, v.begin(), v.end(), 0);

Math Functions (<cmath>)

#include <cmath>
#include <cerrno>
#include <cstring>
using namespace std;

int main() {
    double x = 2.5;
    cout << abs(x)   << '\n';   // 2.5
    cout << floor(x) << '\n';   // 2
    cout << ceil(x)  << '\n';   // 3
    cout << sqrt(x)  << '\n';   // 1.58114
    cout << pow(x,3) << '\n';   // 15.625
    cout << log(x)   << '\n';   // natural log
    cout << sin(x)   << '\n';   // also: cos, tan, sinh, ...

    // error handling via errno
    errno = 0;
    double bad = sqrt(-1.0);
    if (errno == EDOM) cerr << "Domain error: " << strerror(errno) << '\n';

    errno = 0;
    double huge = pow(2, 1e20);
    if (errno == ERANGE) cerr << "Range error\n";
}

Limits and Constants

<limits> provides type min/max values; <numbers> (C++20) provides mathematical constants:

#include <limits>
#include <numbers>
using namespace std;

cout << numeric_limits<int>::max()        << '\n';  // 2147483647
cout << numeric_limits<int>::min()        << '\n';  // -2147483648
cout << numeric_limits<double>::epsilon() << '\n';  // 2.22045e-16

using namespace std::numbers;
cout << pi  << '\n';  // 3.14159...
cout << e   << '\n';  // 2.71828...
cout << phi << '\n';  // 1.61803...

// templated for mixed precision
float area = pi_v<float> * r * r;

Random Numbers (<random>)

The modern C++ approach separates the engine (generator) from the distribution, giving full control over randomness quality and statistical properties.

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

int main() {
    random_device rd;   // hardware entropy source
    mt19937 gen(rd());  // Mersenne Twister — high quality

    uniform_int_distribution<int>     dice(1, 6);
    uniform_real_distribution<double> unit(0.0, 1.0);
    normal_distribution<double>       norm(0.0, 1.0);

    for (int i = 0; i < 5; ++i) cout << dice(gen) << ' ';
    cout << '\n' << unit(gen) << '\n' << norm(gen) << '\n';

    // fixed seed for reproducible results (e.g. testing)
    mt19937 fixed_gen(42);
    cout << dice(fixed_gen) << '\n';   // always the same value
}

Available distributions include: uniform_int_distribution, uniform_real_distribution, normal_distribution, binomial_distribution, poisson_distribution, exponential_distribution.

The old rand() % n approach has unequal probabilities when n does not divide RAND_MAX. Prefer <random> for any serious use.

Time Measurement (<chrono>)

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

int main() {
    vector<int> v(1'000'000);
    // ... fill v ...

    auto t1 = high_resolution_clock::now();
    sort(v.begin(), v.end());
    auto t2 = high_resolution_clock::now();

    auto ms = duration_cast<milliseconds>(t2 - t1).count();
    auto us = duration_cast<microseconds>(t2 - t1).count();
    cout << "Sort took: " << ms << " ms (" << us << " µs)\n";
}

Use high_resolution_clock for benchmarking. system_clock gives wall-clock time. C++20 adds full calendar and timezone support via std::chrono::year_month_day etc.

Complex Numbers (<complex>)

#include <complex>
#include <numbers>
using namespace std;
using namespace std::complex_literals;

complex<double> z0 = 1.0 + 2i;
complex<double> z1 = 3.0 - 1i;

cout << z0 + z1 << '\n';   // (4, 1)
cout << z0 * z1 << '\n';   // (5, 5)
cout << abs(z0) << '\n';   // magnitude
cout << arg(z0) << '\n';   // angle in radians

// Euler's formula: e^(i*pi) + 1 = 0
complex<double> euler = exp(1i * numbers::pi);
cout << euler << '\n';     // (-1, ~0)

Vector Arithmetic (<valarray>)

vector<T> is a general-purpose container and does not support element-wise arithmetic. valarray is designed for numerical array operations:

#include <valarray>
using namespace std;

valarray<double> a = {1.0, 2.0, 3.0, 4.0};
valarray<double> b = {10.0, 20.0, 30.0, 40.0};

auto c = 2.0 * a + b;   // element-wise: {12, 24, 36, 48}
auto d = sqrt(c);       // element-wise sqrt

cout << c.sum() << '\n';  // 120
cout << c.min() << '\n';  // 12
cout << c.max() << '\n';  // 48