STL Overview

What Is the C++ STL?

The Standard Template Library (STL) is the generic-programming foundation commonly used to describe the standard library's containers, iterators, algorithms and function objects. These components are designed to cooperate: a container stores values, iterators describe a range, and an algorithm operates on that range without needing to know the container's concrete type.

#include <algorithm>
#include <vector>

std::vector<int> values{5, 2, 9, 2};
std::sort(values.begin(), values.end());

STL is often used informally for the whole C++ standard library, but that is imprecise. Streams, strings, regular expressions, threads and the filesystem are standard-library facilities; the classic STL model is the generic container–iterator–algorithm system.

How the STL Architecture Fits Together

const auto passed = std::count_if(
    marks.begin(), marks.end(),
    [](int mark) { return mark >= 40; }
);

The algorithm accepts an iterator range and a predicate. It does not own the data. This separation makes the same algorithm reusable with many containers whose iterators satisfy its requirements.

Headers matter: <vector> declares vector, <algorithm> declares sorting/search algorithms, and <numeric> declares accumulate. Include what the source directly uses.

Choosing the Right Container

vector is the default sequence because compact contiguous elements exploit caches well. Do not select list merely because insertion is O(1): reaching the position is O(n), allocation is per node, and real workloads often favor vector.

See the focused lessons on vector and set and map.

Iterators, Categories and Half-Open Ranges

An iterator behaves like a generalized position. A range is normally [first, last): it includes first and excludes last. For a complete container, use begin() and end(); end() is a sentinel position and must not be dereferenced.

for (auto it = values.cbegin(); it != values.cend(); ++it) {
    std::cout << *it << ' ';
}

std::sort requires random-access iterators, so it works with vector but not list. A list supplies its own list::sort. Study C++ iterators before keeping them across mutations.

Algorithms in Practice

#include <algorithm>
#include <numeric>
#include <vector>

std::vector<int> data{7, 2, 9, 4};
std::sort(data.begin(), data.end());

auto first_even = std::find_if(data.begin(), data.end(),
                               [](int n) { return n % 2 == 0; });
int total = std::accumulate(data.begin(), data.end(), 0);
std::transform(data.begin(), data.end(), data.begin(),
               [](int n) { return n * 2; });

The initial value in accumulate also helps determine the result type. Use 0LL when summing many integers into long long. A comparator must define a valid strict weak ordering; writing a <= b for sort is wrong.

If a vector is already sorted, lower_bound performs logarithmic comparisons. Calling it on an unsorted range produces no useful search guarantee. C++20 ranges can make intent clearer:

#include <ranges>
std::ranges::sort(data);
auto odds = data | std::views::filter([](int n) { return n % 2; });

Views are often lazy and may refer to another range; manage source lifetimes carefully. Continue with STL algorithms.

Complexity, Allocation and Invalidation

Big-O is a growth contract, not a stopwatch result. O(1) can have a large constant; O(n) over contiguous memory may beat pointer-heavy traversal for practical sizes. Evaluate element size, allocation, hashing, cache locality and the actual input distribution.

• vector growth: when capacity is exhausted, reallocation moves/copies elements and invalidates all iterators, pointers and references.
• vector erase: handles at or after the erased position are invalidated.
• map/set insert: existing iterators and references normally remain valid; erasing an element invalidates handles to that element.
• unordered rehash: iterators are invalidated by rehash; references/pointers to elements remain valid under the standard rules unless the element is erased.

values.reserve(100);       // capacity changes, size does not
values.push_back(42);      // do not retain stale iterators blindly

for (auto it = values.begin(); it != values.end(); ) {
    if (*it < 0) it = values.erase(it);
    else ++it;
}

Complete STL Lab with Verified Output

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<int> marks{72, 88, 65, 88, 91};

    const int total = std::accumulate(marks.begin(), marks.end(), 0);
    const auto high = std::count_if(marks.begin(), marks.end(),
                                    [](int m) { return m >= 75; });

    std::sort(marks.begin(), marks.end());
    const auto new_end = std::unique(marks.begin(), marks.end());
    marks.erase(new_end, marks.end());

    std::cout << std::fixed << std::setprecision(1)
              << "Average: " << total / 5.0 << '\n'
              << "At least 75: " << high << "\nUnique: ";
    for (int mark : marks) std::cout << mark << ' ';
}

The erase–unique idiom has two stages: unique compacts adjacent duplicates and returns the new logical end; erase removes the leftover tail. Sorting first makes equal values adjacent.

Common Mistakes and 100-Point Checklist

1. State the data and ownership model.
2. Select a container from operations and guarantees.
3. Check algorithm iterator requirements.
4. Check preconditions such as sorting.
5. Account for invalidation after mutation.
6. Use a valid comparator/predicate.
7. Compile with -Wall -Wextra -Wpedantic.
8. Test empty, one-element, duplicate and large cases.
9. Measure before performance claims.
10. Record the required language standard.

Authoritative References

• C++ Working Draft: Containers Library
• C++ Working Draft: Iterators Library
• C++ Working Draft: Algorithms Library

The requirements, complexity terminology and invalidation guidance on this page were checked against the current C++ working draft. For a shorter entry point, open STL introduction.