The Standard Template Library, or STL, is the part of the C++ standard library that provides generic containers (like std::vector and std::map), iterators that walk those containers, algorithms that act on the iterators (like std::sort and std::find), and small function objects that customise the algorithms. It is the toolkit for storing a collection of items or running an operation across one. This chapter is the high-level map: what the STL is, how its four pieces fit together, where the headers live, and the design idea that makes it all interoperate. The remaining lessons in this section drill into each container, iterator category, and algorithm family in detail.

Before the STL, every C++ project rolled its own linked list, its own hash map, its own sort routine. They were all slightly different, all incompatible, and most were buggy. Alexander Stepanov had been thinking about generic programming since the early 1980s. The idea was simple: write algorithms once, in a way that does not depend on the specific container they operate on. Then the same sort works on an array, a linked list, or anything else, as long as the container provides a way to step through its elements.

Stepanov and Meng Lee built a prototype at HP Labs in 1993-1994. SGI later took over maintenance and the implementation that shipped with their compilers became the reference. The ISO C++ committee adopted the design and the first C++ standard (C++98) included it as part of the standard library. Today every conforming compiler ships an STL implementation: libstdc++ with GCC, libc++ with Clang, and Microsoft's STL with MSVC.

The "Template" in STL is the mechanism that makes it work. Templates let code be parameterised by type. A std::vector is not a vector of int or a vector of std::string; it is a template that generates a fresh vector class for any requested type. The same code body, instantiated for each type, with zero runtime cost compared to a hand-written equivalent.

A short example shows the result. The same loop pattern works regardless of element type, because the container and the range-based for loop are generic.

Two vectors with different element types, one loop pattern. The STL achieves this by combining templates (for genericity) with iterators (for uniform traversal). The rest of this chapter unpacks both pieces.

The STL has four moving parts. Each one exists to do a specific job, and the four are connected by a single shared idea: iterators.

The diagram reads left to right. A container holds data. It hands out iterators that point into its storage. An algorithm takes iterators (not the container) and walks them. A function object plugs into the algorithm to customise comparisons, transformations, or predicates.

Containers

Containers store collections of elements. std::vector is a growable array; std::list is a doubly-linked list; std::map is a sorted associative table; std::unordered_map is a hash table; std::stack and std::queue adapt other containers into restricted-access shapes. Each container picks a different trade-off between memory layout, access speed, and insertion cost. The chapters that follow take each one in turn.

What containers share is the API style: a constructor, size(), empty(), a way to insert (push_back, insert), a way to remove (erase, pop_back), and methods that return iterators to the beginning and end of the collection. That shared shape is what makes the rest of the STL work.

Iterators

An iterator is an object that points to an element in a container and knows how to move to the next one. Think of it as a generalised pointer. Like a raw pointer, dereferencing with * reads or writes the element, and ++ advances it. Unlike a raw pointer, it works for any container that exposes the right operations, even ones that are not laid out contiguously in memory.

The standard pair of iterators a container exposes is begin() (pointing to the first element) and end() (pointing one past the last element). A loop from begin() to end() visits every element exactly once. Iterators are the bridge: an algorithm written years before a new container can still operate on that container, as long as the container's iterators behave correctly.

Algorithms

Algorithms are free functions in the <algorithm> and <numeric> headers that operate on a range of iterators. std::sort(begin, end) sorts a range; std::find(begin, end, value) searches for a value; std::accumulate(begin, end, init) adds elements up. There are over 100 such algorithms in the standard library.

The crucial property is that algorithms do not know what container they are working on. std::sort only cares that the iterators it was handed support random access (jumping ahead by N elements in constant time). std::find only cares that the iterators support ++ and *. Algorithms are written against iterator categories, not container types, which is why the same std::find works on a vector, a deque, a C-style array, and even a custom container.

Function Objects

A function object (also called a functor) is any object that can be called like a function, meaning it overloads operator(). The STL uses them wherever the behaviour of an algorithm needs to be customised. To sort in descending order, pass std::greater<int>{} as the comparator. To find the first product over $50, pass a lambda that returns price > 50.0.

Lambdas, function pointers, classes with operator(), and std::function instances are all function objects. Chapters 22-24 of this section cover them in depth. The role to remember is "the customisation hook for algorithms".

The four pillars together provide a small, composable vocabulary. Pick a container for storage, get iterators from it, run algorithms over the iterators, and customise the algorithms with function objects. A single line like std::sort(prices.begin(), prices.end(), std::greater<double>{}); touches all four.

One std::vector template works for every element type, and one std::sort works for every container, because of C++ templates. A template is a recipe that the compiler instantiates into concrete code when used with a particular type.

A std::vector<double> prices; causes the compiler to generate a class definition for std::vector<double> from the std::vector template, substituting double for the type parameter. A separate use of std::vector<std::string> produces a separate class definition. The two classes share no code at runtime; each is its own concrete type with its own methods.

This differs from how some other languages handle generics. There is no boxing, no runtime type tag, no indirection. A std::vector<int> stores raw ints in contiguous memory; a std::vector<std::string> stores raw std::string objects (which themselves manage their own heap buffer). The compiler can inline calls, optimise tight loops, and produce code as fast as a hand-written custom vector class for that exact element type.

printFirst is one function template. The compiler instantiates it twice: once for std::vector<int> and once for std::vector<double>. Each instantiation is a full, separate function in the resulting binary. The genericity is purely a compile-time tool.

Heavy template use slows down compilation, because each instantiation is a fresh translation unit's worth of work for the compiler. It does not slow down the resulting program. Runtime cost is the same as a hand-written version.

The trade-off is real. A program that uses std::vector<int>, std::vector<double>, and std::vector<std::string> ends up with three full copies of the vector code in the binary. For most programs that is a small cost compared to the productivity gain.

The deepest design decision in the STL is that algorithms do not talk to containers; they talk to iterators. This sounds small, but it changes the algebra of the library.

Consider a naive design where every algorithm had to know about every container. That requires a sort_vector, a sort_list, a sort_deque, and a new function every time someone added a container. Adding a new algorithm would require knowing about every existing container. The number of functions grows as containers times algorithms, which is the wrong scaling.

The STL flips this. Each container is responsible for one thing: exposing iterators that walk its elements correctly. Each algorithm is responsible for one thing: doing its work in terms of iterators. The total number of pieces grows as containers plus algorithms, which is the right scaling.

The diagram shows the layering. Containers on the left expose iterators in the middle. Algorithms on the right consume iterators. The only contract between the two sides is "iterators behave in a documented way". Add a new container, expose conforming iterators, and every existing algorithm works on it. Add a new algorithm, write it against the iterator contract, and every existing container can use it.

A short demo makes this concrete. The same std::find call works on a vector and a list, with no per-container variation.

std::find is the same function in both calls. The vector hands it random-access iterators that jump in O(1); the list hands it bidirectional iterators that move one step at a time. The function works in both cases because the operations it uses (++, *, !=) are part of the contract every iterator category honours.

Not every algorithm works with every iterator. std::sort needs random-access iterators (to swap arbitrary elements efficiently), so calling std::sort(list.begin(), list.end()) does not compile; lists provide a member sort() instead. The iterator category determines which algorithms are available.

The standard containers fall into four families. The family describes the data layout, the access pattern, and the kind of iterator provided. Future chapters cover each container in detail; the table below is the map.

The sequence containers care about order. The associative containers care about lookup by key. The adapters care about access discipline (only the top, only the front, only the back).

A small example shows what each family looks like. Each method is covered in detail in its own chapter; this snapshot establishes the shapes.

Four containers, four families, four different internal layouts. The chapters that follow take each one apart so the appropriate family can be picked for a given problem.

Every STL piece lives in a header named after the container, the algorithm group, or the utility. The headers do not have a .h extension; that is a C convention. C++ standard headers use no extension.

Everything in the STL lives inside the std namespace. Access it as std::vector, std::sort, std::map, and so on. The :: is the scope resolution operator and it disambiguates "the vector in the standard library" from any vector defined elsewhere.

Two #include directives, two std:: qualifications. The <vector> header brings in std::vector; the <algorithm> header brings in std::sort. The qualified names show clearly where each piece comes from.

Tutorials sometimes show using namespace std; at the top of files. Avoid that in real code. It dumps every name from std into the global scope, which causes naming collisions (std::distance, std::count, std::move, std::less are all common words) and obscures where each symbol comes from. The cost of typing std:: is small. The cost of debugging a collision in a large codebase is not.

"STL" and "C++ standard library" are often used interchangeably. They are not the same thing, although the distinction matters less in 2026 than it did twenty years ago.

The original STL, the one Stepanov and Lee built at HP, contained four things: containers, iterators, algorithms, and function objects. That is what the term means in "the STL design". The C++ standard library is much broader. It includes everything in the STL plus std::string, the I/O streams in <iostream>, the smart pointers in <memory>, the chrono library, the threading primitives, the filesystem library, and on and on. None of those are STL in the original sense, but they all live in std:: and ship with every conforming compiler.

In casual usage, "STL" has drifted to mean "anything in the standard library". Strictly speaking that is wrong; an std::shared_ptr is part of the C++ standard library but not part of the STL. For this section of the course, "STL" means the original four pillars, and that is the focus through every chapter here.

One practical consequence: a job description that says "strong knowledge of STL" almost certainly means the original-sense STL. Knowing every container, the iterator categories, and which algorithm fits each task is the actual ask. Knowing std::string and <iostream> is assumed; those are taught in the first weeks of any C++ course.

Beyond "containers and algorithms", the STL makes a handful of design promises that shape how the library is used.

The first is value semantics. Containers own their elements by value. Copying a std::vector<int> deep-copies all its ints into a new buffer. Moving a vector (since C++11) transfers ownership of the buffer in O(1) without copying the elements. There is no implicit sharing, no reference counting, no GC. For shared ownership, place std::shared_ptr<T> into the container; the container itself stays a simple value.

Modifying b does not affect a because b got its own copy of the elements at construction. Reference semantics would make b[0] = 99 change a[0] too. Value semantics is the more predictable default and is the one C++ picks.

The second is complexity guarantees. The standard pins down the asymptotic cost of every container operation, not just for one implementation but for all conforming implementations. std::vector::push_back is amortised O(1) regardless of which standard library is linked. std::map::insert is O(log n). std::unordered_map::find is O(1) on average. The standard is precise about which operations must hit a given bound, so portable code can rely on the guarantees.

The third is exception safety. STL operations come with documented exception safety levels, usually the strong guarantee: if an operation throws, the container is left in the state it was in before the call. Some operations weaken this to the basic guarantee (no resource leak, but the container may be in a different valid state). The level matters when writing code that can throw mid-operation. The chapters that follow flag the exception-safety level of each operation that has a non-obvious one.

The fourth is iterator and reference stability rules. Every container documents which operations invalidate iterators or references. The exact rules differ per container (vector invalidates everything on reallocation; list invalidates almost nothing; map invalidates only iterators to erased nodes), and getting them wrong is a common source of bugs. The container chapters spell out the rules.

The four guarantees layer up to give a library where the costs are visible, the lifetimes are predictable, and the failure modes are explicit. None is unique to C++, but the combination is what makes the STL well-suited to systems work where performance and resource management matter.

Each STL container has a second template parameter, an allocator, that controls how the container obtains and releases memory. It is usually invisible because every container defaults to std::allocator<T>, which calls operator new and operator delete.

For 95 percent of code, the default allocator is correct and the parameter can be ignored. Allocators matter when custom memory management is required: a pool allocator for fast allocation of many same-sized objects, a stack allocator for tight loops, a shared-memory allocator for inter-process containers. For this section, treat the allocator parameter as a footnote and let it default.

A single line of typical STL code touches all four pillars at once. A complete program that builds a product catalog, sorts it by price, and finds the first product over $30:

The container is std::vector<Product>. The iterators come from catalog.begin() and catalog.end(). The algorithms are std::sort and std::find_if. The function objects are the two lambdas (one comparator, one predicate). Four pillars, one program, and the program reads like a paragraph because each piece does one job and composes cleanly with the others.

A few ideas come up often. Worth correcting before the per-container chapters.

"STL containers are slow because they are generic." They are not. Generic in C++ means template-based, and templates are a compile-time mechanism. A std::vector<int> produces the same machine code a hand-rolled int-array would, give or take what the optimiser sees. Benchmarks consistently show standard containers matching hand-written ones for the same task. The cases where the STL loses are usually about the wrong container choice (using a list when a vector would do), not about overhead in the container itself.

"`std::vector` is a C array with extra steps." It is much more than that. A vector knows its size, manages its own buffer, handles reallocation, propagates exceptions correctly during construction, and integrates with every algorithm in <algorithm>. A C array is a fixed-size, manually-managed memory range with no introspection. The two have similar memory layouts but different ergonomics.

"All STL containers support all STL algorithms." No. Algorithms are written against iterator categories, and not every container provides every iterator category. std::sort needs random-access iterators, which std::list does not have, so std::sort(list.begin(), list.end()) does not compile. The chapter on iterator categories spells out the hierarchy and which algorithm needs which category.

"Use `std::list` whenever inserting in the middle." Almost never. The cost of cache misses on a linked list traversal usually overwhelms the savings from avoiding shifts in a vector, for sizes up to thousands of elements. Measure before choosing a list. The list chapter covers the trade-offs in detail.

"The standard says `std::vector` doubles its capacity on growth." The standard says capacity grows geometrically and push_back is amortised O(1). It does not mandate a specific factor. Libstdc++ and libc++ pick 2x; MSVC picks 1.5x. Production code should not depend on the exact factor.

"`using namespace std;` makes code cleaner." It makes code shorter, not cleaner. Short names like count, distance, move, less, swap, bind collide with names from user code, and the collisions produce confusing errors. Type the four characters.

A route through the next 23 chapters:

Each chapter assumes knowledge of the previous ones. The end result is the ability to pick the right container, walk it, apply the right algorithm, and customise the algorithm's behaviour.