The C++ Standard Template Library (STL): Containers, Iterators, Algorithms and Function Objects

Finding one number among a million took std::find 765,433 comparisons. std::set::find took 22, and std::unordered_set::find took one. The data was identical in all three; only the container changed. That is the Standard Template Library in one example: a set of containers and algorithms that work together, where the choice of container decides what each operation costs.

This guide explains what the STL is and how its four parts fit together: containers, iterators, algorithms and function objects. It covers container adaptors, iterator categories, the bugs that come from invalidated iterators and std::remove, and the C++20 ranges library that builds on it all. Every program was compiled and run for this article on Ubuntu 24.04 with GCC 13.3 and Clang 18.1.3, against both libstdc++ 13 and libc++ 18, using -std=c++17 (C++20 for two examples) with -Wall -Wextra -pedantic and no warnings. Every output block is captured verbatim, and each program printed the same output on all three toolchains. The code is in a GitHub repository whose build repeats these checks on each commit.

The Short Answer

What is the STL? The part of the C++ standard library that provides generic containers (vector, map and others), algorithms (sort, find and others), and the iterators that connect them. It is written with templates, so the same code works for any element type.

Is the STL the same as the C++ standard library? No. The C++ standard does not use the name “STL”. It is the common name for the containers, iterators and algorithms that came from Alexander Stepanov’s library and were adopted into the standard. The standard library also contains strings, streams, threads, smart pointers and more.

Which container should I use? std::vector, unless you have a measured or structural reason to use something else. The sections below show what those reasons look like.

What Is the Standard Template Library?

The Standard Template Library (STL) is the set of generic containers, iterators, algorithms and function objects in the C++ standard library. Containers store elements, algorithms process them, and iterators connect the two, so a single algorithm such as std::sort works with any container whose iterators meet its requirements. Everything is a template, so the element type is chosen at compile time.

The design came from Alexander Stepanov, working with Meng Lee at Hewlett-Packard. Stepanov presented it to the ANSI/ISO C++ committee in November 1993, the committee approved the final proposal in July 1994, and HP made its implementation freely available that August (history of the STL). The first ISO C++ standard, C++98, included it, and later standards have extended it. The current reference for the containers library lists its families and the rules each one follows.

The central idea is the separation shown in the figure. With M containers and N algorithms, writing each algorithm for each container would need M × N implementations. The STL writes each algorithm once, against an iterator interface, and each container provides iterators. That needs M + N pieces of code instead.

The STL is generic programming, not object-oriented programming. Containers do not share a base class, and algorithms are free functions rather than member functions. What links them is a set of requirements on types, checked at compile time.

The STL and the Rest of the C++ Standard Library

The C++ standard library is everything the C++ standard requires an implementation to provide; the STL is the part of it that holds generic containers and the algorithms that work on them. Code rarely respects the boundary, because the other parts were built to work with the STL’s iterators.

So “which header is std::string in” and “is std::string part of the STL” have different answers: <string>, and not historically, though it behaves like a container. The std::string guide covers it in depth.

A First Look: Containers, Iterators and Algorithms Together

This program uses one container and three algorithms. Each algorithm receives a pair of iterators, begin() and end(), marking the range to work on.

// first_look.cpp - a container, iterators and algorithms working together.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

int main()
{
    std::vector<std::string> words{"iterator", "map", "algorithm", "set",
                                   "vector", "deque", "list", "array"};

    std::sort(words.begin(), words.end());                    // algorithm + iterators

    auto long_words = std::count_if(words.begin(), words.end(),
                                    [](const std::string& w) { return w.size() > 5; });

    std::size_t letters = std::accumulate(words.begin(), words.end(), std::size_t{0},
                                          [](std::size_t sum, const std::string& w) {
                                              return sum + w.size();
                                          });

    for (const auto& w : words)
        std::cout << w << ' ';
    std::cout << "\nwords longer than 5 letters: " << long_words
              << "\ntotal letters: " << letters << '\n';
}

Output:

algorithm array deque iterator list map set vector 
words longer than 5 letters: 3
total letters: 43

std::sort and std::count_if come from <algorithm>, and std::accumulate from <numeric>. None of them knows it is working on a std::vector. The lambda passed to count_if is a function object: it customizes what the algorithm does without changing the algorithm. The std::size_t{0} argument to accumulate matters: the result type is taken from the initial value, and a plain 0 accumulates into an int whatever the element type. In a separate test, summing two long long values of three billion with an initial 0 produced an int result, and GCC 13.3 gave no warning under -Wall -Wextra.

STL Containers

The containers fall into four families. Sequence containers keep elements in the order you insert them. Ordered associative containers keep them sorted by key. Unordered associative containers use a hash table. Container adaptors give a restricted interface over another container.

// containers.cpp - one short example from each container family.
#include <array>
#include <deque>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>

int main()
{
    // Sequence containers keep elements in the order you put them.
    std::vector<int> v{3, 1, 4};
    v.push_back(1);                              // amortized O(1) at the end
    std::deque<int> d{3, 1, 4};
    d.push_front(0);                             // O(1) at either end
    std::list<int> l{3, 1, 4};
    l.insert(std::next(l.begin()), 9);           // O(1) anywhere, given an iterator
    std::array<int, 3> a{3, 1, 4};               // fixed size, no heap allocation

    std::cout << "vector:";
    for (int x : v) std::cout << ' ' << x;
    std::cout << "\ndeque: ";
    for (int x : d) std::cout << ' ' << x;
    std::cout << "\nlist:  ";
    for (int x : l) std::cout << ' ' << x;
    std::cout << "\narray: ";
    for (int x : a) std::cout << ' ' << x;

    // Ordered associative containers keep elements sorted by key.
    std::set<int> s{3, 1, 4, 1, 5};              // duplicates are dropped
    std::map<std::string, int> ages{{"carol", 41}, {"alice", 36}};
    ages["bob"] = 29;

    std::cout << "\nset:   ";
    for (int x : s) std::cout << ' ' << x;
    std::cout << "\nmap:   ";
    for (const auto& [name, age] : ages) std::cout << ' ' << name << '=' << age;

    // Unordered associative containers use hashing; iteration order is unspecified.
    std::unordered_map<std::string, int> stock{{"apples", 4}, {"pears", 0}};
    stock["plums"] = 7;
    std::cout << "\nunordered_map has " << stock.size() << " keys; plums = "
              << stock.at("plums") << '\n';
}

Output:

vector: 3 1 4 1
deque:  0 3 1 4
list:   3 9 1 4
array:  3 1 4
set:    1 3 4 5
map:    alice=36 bob=29 carol=41
unordered_map has 3 keys; plums = 7

The set dropped the duplicate 1 and printed in sorted order; the map printed by key, not by insertion order. The map loop uses C++17 structured bindings to name each key and value. The program prints the unordered_map‘s size rather than its contents, because iteration order in an unordered container is unspecified and can differ between standard libraries.

The next section shows what these complexities mean as numbers.

Container Adaptors: stack, queue and priority_queue

An adaptor wraps a container and exposes only the operations that fit one access pattern:

// adaptors.cpp - stack, queue and priority_queue restrict an underlying container.
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

int main()
{
    std::stack<int> st;                 // LIFO, on std::deque by default
    std::queue<int> q;                  // FIFO, on std::deque by default
    std::priority_queue<int> pq;        // largest first, on std::vector by default

    for (int x : {3, 1, 4, 1, 5}) {
        st.push(x);
        q.push(x);
        pq.push(x);
    }

    std::cout << "stack:         ";
    for (; !st.empty(); st.pop()) std::cout << st.top() << ' ';
    std::cout << "\nqueue:         ";
    for (; !q.empty(); q.pop()) std::cout << q.front() << ' ';
    std::cout << "\npriority_queue:";
    for (; !pq.empty(); pq.pop()) std::cout << ' ' << pq.top();

    // A min-heap: same adaptor, std::greater as the comparison.
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
    for (int x : {3, 1, 4, 1, 5}) min_heap.push(x);
    std::cout << "\nmin-heap:      ";
    for (; !min_heap.empty(); min_heap.pop()) std::cout << min_heap.top() << ' ';
    std::cout << '\n';
}

Output:

stack:         5 1 4 1 3 
queue:         3 1 4 1 5 
priority_queue: 5 4 3 1 1
min-heap:      1 1 3 4 5 

The stack returns the last value pushed, the queue the first, and the priority queue the largest. Passing std::greater<int> reverses the ordering and turns the priority queue into a min-heap, which is what Dijkstra’s algorithm uses to pick the closest unvisited vertex. Adaptors have no iterators, so the standard algorithms cannot be applied to them directly.

How Much the Container Choice Costs: Counting Comparisons

Complexity tables describe growth, not counts. This program measures the counts directly: it stores the integers 0 to 999,999, searches for 765,432, and counts every comparison through comparison objects that increment a counter. Counting comparisons, rather than timing, gives the same result on every run and on every machine with the same standard library.

// lookup_cost.cpp - how many element comparisons it takes to find one value
// among 1,000,000, depending on the container and the algorithm.
#include <algorithm>
#include <cstddef>
#include <functional>
#include <iostream>
#include <set>
#include <unordered_set>
#include <vector>

static long g_compares = 0;   // incremented by every comparison below

struct CountingLess {
    bool operator()(int a, int b) const { ++g_compares; return a < b; }
};
struct CountingEqual {
    bool operator()(int a, int b) const { ++g_compares; return a == b; }
};

// Every key in one bucket: what hashing degrades to when the hash is poor.
struct ConstantHash {
    std::size_t operator()(int) const { return 42; }
};

template <typename F>
long count(F&& lookup)
{
    g_compares = 0;
    lookup();
    return g_compares;
}

int main()
{
    constexpr int n = 1'000'000;
    const int target = 765'432;

    std::vector<int> values(n);
    for (int i = 0; i < n; ++i)
        values[i] = i;                      // already sorted

    std::set<int, CountingLess> tree(values.begin(), values.end());
    std::unordered_set<int, std::hash<int>, CountingEqual> table(values.begin(), values.end());

    long linear = count([&] {
        (void)std::find_if(values.begin(), values.end(),
                           [&](int x) { return CountingEqual{}(x, target); });
    });
    long binary = count([&] {
        (void)std::binary_search(values.begin(), values.end(), target, CountingLess{});
    });
    long set_find = count([&] { (void)tree.find(target); });
    long hash_find = count([&] { (void)table.find(target); });

    // Built with only 10,000 values: with one bucket, construction is quadratic.
    std::unordered_set<int, ConstantHash, CountingEqual> bad_table(values.begin(),
                                                                   values.begin() + 10'000);
    long bad_hash_find = count([&] { (void)bad_table.find(7'654); });

    std::cout << "searching " << n << " ints for " << target << "\n"
              << "std::find on vector:           " << linear << " comparisons\n"
              << "std::binary_search on vector:  " << binary << " comparisons\n"
              << "std::set::find:                " << set_find << " comparisons\n"
              << "std::unordered_set::find:      " << hash_find << " comparisons\n"
              << "same, constant hash, 10000 ints: " << bad_hash_find << " comparisons\n";
}

Output (identical with libstdc++ 13 and libc++ 18):

searching 1000000 ints for 765432
std::find on vector:           765433 comparisons
std::binary_search on vector:  21 comparisons
std::set::find:                22 comparisons
std::unordered_set::find:      1 comparisons
same, constant hash, 10000 ints: 2346 comparisons

Two things stand out. A sorted std::vector with std::binary_search matched std::set with one comparison fewer, while storing the integers contiguously instead of in a million separately allocated tree nodes. And hashing’s single comparison depends entirely on the hash function: with every key in one bucket, the search became linear. That bucket held 10,000 keys, and 7,654 was the 2,346th from the front in both standard libraries, consistent with each library adding new keys at the front of the bucket. The “O(1) on average” in the table above is an average over keys that a reasonable hash spreads across buckets.

The binary_search figure needs one caveat. It is available on any sorted range with forward iterators, but on a std::list the number of iterator steps is linear even though comparisons stay logarithmic, because the list cannot jump to its middle.

Iterators: How Algorithms Reach Containers

An iterator is an object that points at an element and can move to another one. Every standard container except the adaptors provides begin() and end(), where end() points one past the last element, and the classic algorithms take a range as such a pair. The figure above shows the categories: an algorithm states the weakest category it can work with, and a container must provide at least that.

std::sort jumps to the middle of its range and computes distances between iterators, so it needs random-access iterators. std::list provides bidirectional iterators, and the call does not compile:

// sort_list.cpp - must NOT compile: std::sort needs random-access iterators,
// and std::list provides bidirectional ones.
#include <algorithm>
#include <list>

int main()
{
    std::list<int> numbers{3, 1, 4, 1, 5};
    std::sort(numbers.begin(), numbers.end());
}

GCC 13.3’s first error is not about sorting at all (excerpt):

tests/compile-fail/sort_list.cpp:9:14:   required from here
/usr/include/c++/13/bits/stl_algo.h:1948:50: error: no match for 'operator-' (operand types are 'std::_List_iterator<int>' and 'std::_List_iterator<int>')

The compiler found the problem inside the library, at the point where std::sort subtracts two iterators. C++20’s range algorithms state their requirements as concepts, so the same mistake is reported against the requirement instead:

// ranges_sort_list.cpp - must NOT compile: the same mistake with C++20 ranges.
#include <algorithm>
#include <list>

int main()
{
    std::list<int> numbers{3, 1, 4, 1, 5};
    std::ranges::sort(numbers);
}

GCC 13.3 (excerpt, first and last lines of the explanation):

tests/compile-fail/ranges_sort_list.cpp:8:22: error: no match for call to '(const std::ranges::__sort_fn) (std::__cxx11::list<int>&)'
/usr/include/c++/13/concepts:67:28: note:   'std::random_access_iterator_tag' is not a base of 'std::bidirectional_iterator_tag'

The error now points at line 8 of your file and ends with the reason: a bidirectional iterator is not a random-access iterator. The improvement is in what the message says, not necessarily its length:

The fix is the member function numbers.sort(). std::list provides its own sort, merge, remove and unique, because a list can reorder elements by relinking nodes, which the general algorithms cannot do.

Iterator Invalidation: The Bug That Prints Plausible Numbers

An iterator into a std::vector points into the vector’s current block of memory. When push_back needs more capacity, the vector allocates a larger block, moves the elements, and frees the old block, and every existing iterator, pointer and reference now points at freed memory. The containers reference lists this rule for each container.

// invalidated_iterator.cpp - an iterator kept across push_back. When the
// vector grows, it moves its elements and the old iterator dangles.
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> scores{70, 85, 90};
    std::cout << "capacity before: " << scores.capacity() << '\n';

    auto best = scores.begin() + 2;       // points at 90
    scores.push_back(95);                 // exceeds capacity: storage is reallocated

    std::cout << "capacity after:  " << scores.capacity() << '\n';
    std::cout << "best score: " << *best << '\n';   // reads freed memory
}

Output (three runs, no sanitizer):

--- run 1
capacity before: 3
capacity after:  6
best score: 1630214452
--- run 2
capacity before: 3
capacity after:  6
best score: 1772156858
--- run 3
capacity before: 3
capacity after:  6
best score: -735922981

The capacity went from 3 to 6, so the storage moved. The program then printed a different wrong value on each run, and never crashed. A test that only checked “the program runs” would pass. Built with -fsanitize=address, the read is reported where it happens (excerpt):

==2465==ERROR: AddressSanitizer: heap-use-after-free on address 0x502000000018 at pc 0x55eca9da983b bp 0x7ffd6f796da0 sp 0x7ffd6f796d90
READ of size 4 at 0x502000000018 thread T0
    #0 0x55eca9da983a in main tests/sanitizer-fail/invalidated_iterator.cpp:15

There are three standard ways to keep track of an element while a vector grows:

// stable_positions.cpp - three ways to keep track of an element while a
// vector grows: an index, reserve(), or a node-based container.
#include <cstddef>
#include <iostream>
#include <iterator>
#include <list>
#include <vector>

int main()
{
    // 1. An index survives reallocation; an iterator does not.
    std::vector<int> scores{70, 85, 90};
    std::size_t best = 2;
    scores.push_back(95);
    std::cout << "index:   best score = " << scores[best] << '\n';

    // 2. reserve() up front: no reallocation while size() <= capacity().
    std::vector<int> reserved{70, 85, 90};
    reserved.reserve(8);
    auto it = reserved.begin() + 2;
    const auto* data_before = reserved.data();
    reserved.push_back(95);
    std::cout << "reserve: best score = " << *it << ", storage moved: "
              << (reserved.data() != data_before ? "yes" : "no") << '\n';

    // 3. std::list never moves its elements; iterators stay valid until erased.
    std::list<int> nodes{70, 85, 90};
    auto node = std::next(nodes.begin(), 2);
    for (int i = 0; i < 1000; ++i)
        nodes.push_back(i);
    std::cout << "list:    best score = " << *node << '\n';
}

Output:

index:   best score = 90
reserve: best score = 90, storage moved: no
list:    best score = 90

An index stays meaningful after reallocation because it is relative to whatever block the vector currently uses. reserve() guarantees no reallocation until size() exceeds capacity(); the program confirms the storage did not move. And node-based containers such as std::list, std::set and std::map never move their elements, so iterators stay valid until that element is erased. That stability is one of the few good reasons to choose a std::list over a std::vector.

Stream Iterators and Insert Iterators

Iterators are not limited to containers. An std::istream_iterator reads values from a stream each time it is advanced, an std::ostream_iterator writes each value assigned through it, and std::back_inserter calls push_back on a container. Any algorithm that takes iterators can therefore read from a stream, write to one, or grow a container.

// stream_iterators.cpp - algorithms reading from and writing to streams.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <sstream>
#include <vector>

int main()
{
    std::istringstream input("10 20 3 45 15 8 30");   // stands in for a file or std::cin

    // Read every int until end of input; a default-constructed istream_iterator
    // compares equal to one that has reached end of stream.
    std::vector<int> values(std::istream_iterator<int>(input),
                            std::istream_iterator<int>{});

    // Write straight to std::cout: no output loop.
    std::cout << "all:      ";
    std::copy(values.begin(), values.end(), std::ostream_iterator<int>(std::cout, " "));

    std::cout << "\nat most 15: ";
    std::remove_copy_if(values.begin(), values.end(),
                        std::ostream_iterator<int>(std::cout, " "),
                        [](int x) { return x > 15; });

    // back_inserter calls push_back, so the algorithm grows the destination.
    std::vector<int> doubled;
    std::transform(values.begin(), values.end(), std::back_inserter(doubled),
                   [](int x) { return x * 2; });
    std::cout << "\ndoubled:  ";
    std::copy(doubled.begin(), doubled.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\nsizes: values " << values.size() << ", doubled " << doubled.size() << '\n';
}

Output:

all:      10 20 3 45 15 8 30 
at most 15: 10 3 15 8 
doubled:  20 40 6 90 30 16 60 
sizes: values 7, doubled 7

The values vector was built directly from the stream: a default-constructed istream_iterator compares equal to one that has reached end of input, so the pair marks “everything in the stream”. remove_copy_if and copy wrote to std::cout with no loop. Replacing the istringstream with an std::ifstream reads a file the same way.

std::back_inserter resolves the limitation described in the std::remove section below. doubled started empty and ended with seven elements, because each assignment through the inserter called push_back. Without it, transform would have written past the end of an empty vector.

STL Algorithms

Most algorithms live in <algorithm>, and <numeric> adds the arithmetic ones. They fall into a few groups:

Algorithms work on ranges, not containers, and that has a consequence that is easy to miss: an algorithm working through a container’s own iterators cannot add or remove elements. (An algorithm can grow a container when it writes through an insert iterator such as std::back_inserter, because that iterator calls push_back.) std::remove shows the first case.

What the Standard Guarantees About Cost

The C++ standard does not only say what each algorithm does; it also limits how much work it may do. Some limits are exact, some are upper bounds and some are asymptotic. This program counts predicate and comparison calls on 1,000 values from std::mt19937, whose output sequence the standard fixes:

// algorithm_counts.cpp - the C++ standard specifies how many operations an
// algorithm may perform. This counts predicate and comparison calls.
#include <algorithm>
#include <cmath>
#include <iostream>
#include <random>
#include <vector>

int main()
{
    std::vector<int> v(1000);
    std::mt19937 gen(7);                          // fixed sequence on every library
    for (int& x : v) x = static_cast<int>(gen() % 10000);

    long calls = 0;
    auto big = [&](int x) { ++calls; return x > 5000; };

    calls = 0;
    auto n_big = std::count_if(v.begin(), v.end(), big);
    std::cout << "count_if: " << n_big << " matches, predicate called " << calls
              << " times for " << v.size() << " elements\n";

    calls = 0;
    auto it = std::find_if(v.begin(), v.end(), big);
    std::cout << "find_if:  first match at index " << (it - v.begin())
              << ", predicate called " << calls << " times\n";

    long compares = 0;
    std::sort(v.begin(), v.end(), [&](int a, int b) { ++compares; return a < b; });
    const double n = static_cast<double>(v.size());
    const double n_log_n = n * std::log2(n);
    std::cout << "sort:     " << compares << " comparisons; N log2 N = "
              << static_cast<long>(n_log_n) << '\n';
}

Output (GCC 13.3, libstdc++):

count_if: 488 matches, predicate called 1000 times for 1000 elements
find_if:  first match at index 2, predicate called 3 times
sort:     11272 comparisons; N log2 N = 9965

count_if and find_if produced identical counts on both libraries, as the standard requires. std::sort did not, and does not have to: an O(N log N) bound allows any constant factor, and both counts are within 15% of N log₂ N = 9,965. Before C++11 the requirement was weaker, “approximately N log N comparisons on the average”, which allowed a quadratic worst case; LWG issue 713 made the bound apply to every input.

These guarantees are why a hand-written loop rarely beats the library version: the algorithm’s cost is already pinned down by the standard, and the remaining question is which algorithm and which container, as the comparison counts earlier in this article showed.

Why std::remove Does Not Remove

// erase_remove.cpp - std::remove does not remove anything from the container.
#include <algorithm>
#include <iostream>
#include <vector>

static void print(const char* label, const std::vector<int>& v)
{
    std::cout << label << " size " << v.size() << ":";
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';
}

int main()
{
    std::vector<int> v{1, 0, 2, 0, 3, 0, 4};
    print("start          ", v);

    auto new_end = std::remove(v.begin(), v.end(), 0);
    print("after remove   ", v);
    std::cout << "                kept elements end at index " << (new_end - v.begin()) << '\n';

    v.erase(new_end, v.end());                   // the erase-remove idiom
    print("after erase    ", v);

#if defined(__cpp_lib_erase_if)
    std::vector<int> w{1, 0, 2, 0, 3, 0, 4};
    auto removed = std::erase(w, 0);             // C++20: one call does both
    print("C++20 std::erase", w);
    std::cout << "                removed " << removed << " elements\n";
#endif
}

Output (C++20 build; under C++17 the last two lines are absent, because the #if excludes them):

start           size 7: 1 0 2 0 3 0 4
after remove    size 7: 1 2 3 4 3 0 4
                kept elements end at index 4
after erase     size 4: 1 2 3 4
C++20 std::erase size 4: 1 2 3 4
                removed 3 elements

After std::remove, the vector still has seven elements. remove moved the kept values 1 2 3 4 to the front and returned an iterator to the new logical end; the three elements after it are in a valid but unspecified state. Here they happen to be 3 0 4, but no program should depend on that. Only a member function of the container, such as erase, can change its size, hence the erase-remove idiom: v.erase(std::remove(...), v.end()). C++20 adds std::erase and std::erase_if, which do both steps in one call and return the number removed.

Function Objects and Lambdas

A function object is anything that can be called like a function. Algorithms and ordered containers accept one to customize their behaviour: how to compare, what to test, how to transform.

// function_objects.cpp - customizing algorithms and containers with lambdas,
// standard function objects and a comparison for a user-defined type.
#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <set>
#include <string>
#include <vector>

struct Employee {
    std::string name;
    int salary;
};

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

    std::sort(v.begin(), v.end(), std::greater<int>{});        // descending
    std::cout << "descending:";
    for (int x : v) std::cout << ' ' << x;

    int threshold = 4;
    auto above = std::count_if(v.begin(), v.end(),
                               [threshold](int x) { return x > threshold; });
    std::cout << "\nabove " << threshold << ": " << above;

    std::vector<int> squares(v.size());
    std::transform(v.begin(), v.end(), squares.begin(), [](int x) { return x * x; });
    std::cout << "\nsum of squares: "
              << std::accumulate(squares.begin(), squares.end(), 0);

    // A set orders by its comparison object; here, by salary then name.
    auto by_salary = [](const Employee& a, const Employee& b) {
        return a.salary != b.salary ? a.salary < b.salary : a.name < b.name;
    };
    std::set<Employee, decltype(by_salary)> staff(by_salary);
    staff.insert({"dana", 5200});
    staff.insert({"erin", 4100});
    staff.insert({"finn", 5200});

    std::cout << "\nby salary:";
    for (const auto& e : staff) std::cout << ' ' << e.name << '(' << e.salary << ')';
    std::cout << '\n';
}

Output:

descending: 9 8 5 3 2 1
above 4: 3
sum of squares: 184
by salary: erin(4100) dana(5200) finn(5200)

std::greater<int> is one of the standard function objects in <functional>; a lambda is the more common choice for anything else. The lambda for count_if captures threshold by value, so it carries its own copy of the data it needs. The std::set example shows the comparison doing a second job: a set treats two elements as equal when neither compares less than the other. Comparing by salary alone made dana and finn equal in a separate test, and the set kept only dana: two elements, not three. Adding the name as a tie-breaker keeps both.

Replacing the C++98 Function Adapters

Tutorials written before C++11 build function objects with adapters such as ptr_fun, bind2nd and mem_fun_ref. Most of these were deprecated in C++11 and removed in C++17; not1 and not2 followed in C++20.

Removal from the standard did not mean removal from every compiler. This classic example compiles with GCC 13.3 and Clang 18.1.3 with libstdc++ under -std=c++17 and -std=c++20, with -Wdeprecated-declarations warnings. Built against libc++ 18 with -std=c++17, it does not compile:

transform(d, d + DSZ, back_inserter(vb), not1(ptr_fun(isEven)));

ptrfun_not1.cpp:18:6: error: use of undeclared identifier 'ptr_fun'

So code using these adapters can build on Linux and fail on macOS, whose standard library is libc++. Here are the classic examples rewritten with their replacements:

// modern_adapters.cpp - C++98 function adapters and their replacements.
// Each block reproduces a classic example with C++17 tools.
#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <iterator>
#include <memory>
#include <vector>

static bool is_even(int x) { return x % 2 == 0; }

class Angle {
public:
    explicit Angle(int deg) : degrees_(deg) {}
    int mul(int times) { return degrees_ *= times; }
private:
    int degrees_;
};

struct Shape {
    virtual ~Shape() = default;
    virtual void draw() const = 0;
};
struct Circle : Shape { void draw() const override { std::cout << "Circle::draw "; } };
struct Square : Shape { void draw() const override { std::cout << "Square::draw "; } };

int main()
{
    const std::vector<int> d{123, 94, 10, 314, 315};

    // not1(ptr_fun(is_even))  ->  std::not_fn(is_even)
    std::cout << "not_fn:  ";
    std::transform(d.begin(), d.end(), std::ostream_iterator<bool>(std::cout, " "),
                   std::not_fn(is_even));

    // bind2nd(ptr_fun<double, double, double>(pow), 2.0)  ->  a lambda
    const std::vector<double> x{1.23, 91.370, 56.661, 23.230, 19.959, 1.0, 3.14159};
    std::cout << "\nsquares: ";
    std::transform(x.begin(), x.end(), std::ostream_iterator<double>(std::cout, " "),
                   [](double v) { return std::pow(v, 2.0); });

    // mem_fun_ref(&Angle::mul) with two ranges  ->  std::mem_fn
    std::vector<Angle> angles;
    for (int deg = 0; deg < 50; deg += 10) angles.emplace_back(deg);
    const std::vector<int> times{1, 2, 3, 4, 5};
    std::cout << "\nmem_fn:  ";
    std::transform(angles.begin(), angles.end(), times.begin(),
                   std::ostream_iterator<int>(std::cout, " "), std::mem_fn(&Angle::mul));

    // mem_fun(&Shape::draw) over raw pointers, then a manual purge()
    //   ->  std::mem_fn over unique_ptr; no cleanup code
    std::vector<std::unique_ptr<Shape>> shapes;
    shapes.push_back(std::make_unique<Circle>());
    shapes.push_back(std::make_unique<Square>());
    std::cout << "\nshapes:  ";
    std::for_each(shapes.begin(), shapes.end(), std::mem_fn(&Shape::draw));

    // bind1st(equal_to<int>(), 20) and not1(...)  ->  std::bind, or a lambda
    auto equals_20 = std::bind(std::equal_to<int>{}, 20, std::placeholders::_1);
    const std::vector<int> e{10, 20, 30, 20};
    std::cout << "\nbind:    " << std::count_if(e.begin(), e.end(), equals_20)
              << " equal to 20, "
              << std::count_if(e.begin(), e.end(), [](int v) { return v != 20; })
              << " not equal\n";
}

Output (identical on all three toolchains):

not_fn:  1 0 0 0 1 
squares: 1.5129 8348.48 3210.47 539.633 398.362 1 9.86959 
mem_fn:  0 20 60 120 200 
shapes:  Circle::draw Square::draw 
bind:    2 equal to 20, 2 not equal

The output matches what the original adapter versions printed (1 0 0 0 1 and 0 20 60 120 200). Two of the replacements do more than restore the old behaviour. The shapes example used to hold Shape* in a vector and needed a purge() helper to delete them. With std::unique_ptr elements, std::mem_fn calls draw() through the smart pointer, and nothing needs deleting by hand. The pow example needed an explicit ptr_fun<double, double, double> to choose among the overloads of std::pow; inside a lambda, ordinary overload resolution picks the right one.

A map Pitfall: operator[] Inserts

std::map::operator[] returns a reference to the value for a key, and to return a reference it needs an element to refer to. If the key is missing, it inserts one with a value-initialized value.

// map_lookup.cpp - operator[] inserts a key that is not there; find() does not.
#include <iostream>
#include <map>
#include <stdexcept>
#include <string>

int main()
{
    std::map<std::string, int> stock{{"apples", 4}, {"pears", 0}};

    // Looks like a read. It is an insert when the key is missing.
    if (stock["plums"] > 0)
        std::cout << "plums in stock\n";
    std::cout << "after operator[]: " << stock.size() << " keys, including \"plums\"\n";

    // find() reports absence without changing the map.
    if (auto it = stock.find("cherries"); it == stock.end())
        std::cout << "find(\"cherries\"): not found, still " << stock.size() << " keys\n";

    // at() throws for a missing key instead of inserting.
    try {
        std::cout << stock.at("figs") << '\n';
    } catch (const std::out_of_range&) {
        std::cout << "at(\"figs\"): threw std::out_of_range\n";
    }
}

Output:

after operator[]: 3 keys, including "plums"
find("cherries"): not found, still 3 keys
at("figs"): threw std::out_of_range

The if looked like a read, and it added "plums" with a count of zero. In a function that only meant to check stock, that is a quiet change to shared data, and on a const std::map it does not compile at all, since operator[] has no const overload. Use find() (or C++20’s contains()) to test for a key, at() when a missing key is an error, and operator[] only when inserting a default is what you want, as in counting word frequencies.

C++20 Ranges: The Next Layer of the STL

C++20 added the ranges library, which keeps the STL’s containers, iterators and algorithms and adds two things: algorithms that accept a whole container, and views that describe a transformation without performing it until values are requested.

// ranges_pipeline.cpp - C++20 ranges: algorithms that take a whole container,
// and lazy views composed with |.
#include <algorithm>
#include <iostream>
#include <ranges>
#include <vector>

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

    std::ranges::sort(v);                         // no begin()/end() pair
    std::cout << "sorted:";
    for (int x : v) std::cout << ' ' << x;

    // Nothing is computed until the loop pulls values through the view.
    auto odd_squares = v | std::views::filter([](int x) { return x % 2 != 0; })
                         | std::views::transform([](int x) { return x * x; });
    std::cout << "\nodd squares:";
    for (int x : odd_squares) std::cout << ' ' << x;

    auto it = std::ranges::find(v, 8);
    std::cout << "\nfound 8 at index " << (it - v.begin()) << '\n';
}

Output:

sorted: 1 2 3 5 7 8 9
odd squares: 1 9 25 49 81
found 8 at index 5

std::ranges::sort(v) replaces std::sort(v.begin(), v.end()), and constraint errors become readable, as the iterator section showed. The odd_squares view stores no results; the loop pulls each value through filter and then transform. Views compose with |, which reads left to right in the order the operations happen. All three toolchains used here compiled this example as C++20.

Which STL Container Should You Use?

The STL containers guide goes further on choosing between them, with a complexity table, iterator-invalidation rules and measured vector-versus-list timings, and the std::vector guide covers the default container in depth, including capacity growth and reserve().

Key Takeaways

• The STL separates storage from processing. Containers hold data, algorithms process ranges, and iterators connect them, so one std::sort serves every random-access container.
• The container sets the cost. Finding one value among a million took 765,433 comparisons with std::find, 21 with binary_search on a sorted vector, 22 in a std::set and one in an std::unordered_set.
• Iterator categories decide which algorithms compile. std::sort rejects a std::list; use list.sort(). C++20 ranges report that mismatch by name.
• Growth invalidates vector iterators. The stale iterator printed a different wrong number on each of three runs without crashing. Hold an index, reserve(), or use a node-based container.
• An algorithm cannot shrink the container it was given iterators into. Follow std::remove with erase, or use C++20 std::erase and std::erase_if.
• map::operator[] inserts missing keys. Use find, contains or at to read.
• Hashing is only as good as the hash. A constant hash turned one comparison into 2,346.
• Replace the C++98 adapters. ptr_fun, bind2nd and mem_fun_ref are gone from C++17. Code using them still built with libstdc++ and failed with libc++, the library macOS uses. Lambdas, std::not_fn and std::mem_fn replace them.

Frequently Asked Questions

Conclusion

The STL has lasted since 1994 because its central decision still holds: describe algorithms in terms of what they need from an iterator, and let every container that meets the need use them. Containers, algorithms, function objects and C++20 ranges are all extensions of that one idea.

The practical skill it asks for is choosing a container by what your program does most often, then checking the iterator rules for the operations you perform on it. More C++ guides are collected in the C++ programming section.

Source Code and Tests

All programs on this page are in the stl/overview directory of the MYCPLUS C++ examples repository:

Build and test:

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build
bash tests/run_tests.sh "$PWD/build"
bash tests/sanitizers.sh g++

What the build checks. On Linux with GCC and with Clang, it compiles every example with warnings treated as errors, runs it and compares the output with the output on this page, including the comparison counts. A libc++ job, a macOS job and a Windows (MSVC) job do the same for the outputs every conforming library must produce; for lookup_cost that is the linear-search count, since the tree and hash counts depend on the implementation, and for algorithm_counts it is the exact count_if and find_if counts, since the sort comparison count does too. A sanitizer job confirms that every example runs without an AddressSanitizer or UndefinedBehaviorSanitizer report, that the invalidated iterator is reported as heap-use-after-free, and that both std::sort(list) programs fail to compile, the ranges version with an error naming random_access. The compiler error lengths in the table are not checked by any job; they depend on the compiler version.