Up to now, whenever we needed a growing list of numbers, a lookup table or a sorted collection, we had to build it ourselves with arrays, pointers and new/delete, as in the Dynamic Memory Allocation chapter. That is slow to write and easy to get wrong. Real C++ programmers almost never do it, because the language ships with a ready-made, heavily tested toolbox: the Standard Template Library (STL).
In the previous chapter, Templates, we saw how one piece of code can work for many types. The STL is the biggest example of that idea: one vector template works for int, double, std::string or your own Student class, and one sort algorithm works on many different containers. This chapter gives you the big picture: what the STL is made of, how its parts fit together, and why it was designed that way. The following chapters then study each container in detail, starting with vector.
What Is the STL?
The STL is the part of the C++ Standard Library that provides generic containers (data structures), iterators (a uniform way to walk through them) and algorithms (operations such as searching and sorting), all written as templates so that they work with any suitable type.
A little history helps to understand the design. The STL was created by Alexander Stepanov and Meng Lee at Hewlett-Packard and accepted into C++ during the first standardization, so it has been part of standard C++ since C++98. Strictly speaking, the C++ standard never uses the name "STL"; it just talks about the containers library, the iterators library and the algorithms library. In everyday speech (and in interviews) "STL" means exactly these parts of the standard library, and that is how we use it here.
Everything lives in namespace std, and you get it simply by including the right header. Nothing extra needs to be installed.
A First Taste
Here is a small program that stores marks, sorts them, and computes total, minimum, maximum and a count, without a single hand-written loop for the hard parts:
#include <iostream>
#include <vector>
#include <algorithm> // sort, find, count, min_element, max_element
#include <numeric> // accumulate
int main() {
std::vector<int> marks = {72, 95, 58, 88, 95, 64};
std::sort(marks.begin(), marks.end()); // ascending order
std::cout << "Sorted: ";
for (int m : marks)
std::cout << m << ' ';
std::cout << '\n';
int total = std::accumulate(marks.begin(), marks.end(), 0);
std::cout << "Total: " << total << '\n';
std::cout << "Lowest: " << *std::min_element(marks.begin(), marks.end()) << '\n';
std::cout << "Highest: " << *std::max_element(marks.begin(), marks.end()) << '\n';
std::cout << "Count of 95: " << std::count(marks.begin(), marks.end(), 95) << '\n';
auto it = std::find(marks.begin(), marks.end(), 88);
if (it != marks.end())
std::cout << "Found 88 at index " << (it - marks.begin()) << '\n';
it = std::find(marks.begin(), marks.end(), 100);
if (it == marks.end())
std::cout << "100 not found\n";
}Output:
Sorted: 58 64 72 88 95 95
Total: 472
Lowest: 58
Highest: 95
Count of 95: 2
Found 88 at index 3
100 not foundCompare this with writing your own bubble sort, your own min/max loop and your own linear search. The library versions are shorter, already debugged, and usually faster (std::sort is guaranteed O(n log n) since C++11).
The Four Building Blocks
The STL is built from four kinds of components that work together:
| Component | What it is | Examples |
|---|---|---|
| Containers | Objects that store a collection of elements and manage their memory | vector, list, map, unordered_set |
| Iterators | Pointer-like objects that refer to an element and can move to the next one | v.begin(), v.end() |
| Algorithms | Function templates that operate on a range of elements given by iterators | sort, find, count, accumulate |
| Function objects | Objects that can be called like functions, used to customize algorithms | std::greater<int>, your own functor, lambdas |
Two supporting pieces are also worth knowing by name: container adaptors (stack, queue, priority_queue), which give a restricted interface on top of another container, and allocators, which decide how containers obtain memory. You can ignore allocators for nearly all everyday code; the default std::allocator uses new and delete underneath.
The key idea: iterators connect algorithms to containers
Algorithms never touch containers directly. They only receive a pair of iterators. Containers only need to provide iterators. That one decision is the heart of the whole design:
CONTAINERS ITERATORS ALGORITHMS
┌─────────────┐ ┌──────────────┐
│ vector │──┐ ┌──│ find │
│ list │──┤ begin() end() ├──│ count │
│ deque │──┼───▶ [first ...... last) ◀──┼──│ sort │
│ set / map │──┤ a "range" of elements ├──│ accumulate │
│ your class │──┘ └──│ your algo │
└─────────────┘ └──────────────┘
know how to store the common know how to process
elements "language" elementsWhy is this smart? Suppose there are M containers and N algorithms. If every algorithm were written separately for every container, we would need M × N implementations. With iterators in the middle, each container provides iterators once and each algorithm is written once, so only M + N pieces of code are needed. Add a new container with iterators and every existing algorithm works with it immediately. This is generic programming at its best.
You can see it in action: the very same std::find works on a vector, a linked list, a fixed array, a raw C array and a string:
#include <iostream>
#include <vector>
#include <list>
#include <array>
#include <string>
#include <algorithm>
int main() {
std::vector<int> v = {4, 8, 15, 16, 23, 42};
std::list<int> l = {4, 8, 15, 16, 23, 42};
std::array<int, 6> a = {4, 8, 15, 16, 23, 42};
int raw[] = {4, 8, 15, 16, 23, 42};
std::string s = "algorithm";
// The SAME algorithm works on five different kinds of sequence
std::cout << std::boolalpha;
std::cout << (std::find(v.begin(), v.end(), 23) != v.end()) << '\n';
std::cout << (std::find(l.begin(), l.end(), 23) != l.end()) << '\n';
std::cout << (std::find(a.begin(), a.end(), 99) != a.end()) << '\n';
std::cout << (std::find(std::begin(raw), std::end(raw), 42) != std::end(raw)) << '\n';
std::cout << (std::find(s.begin(), s.end(), 'r') != s.end()) << '\n';
}Output:
true
true
false
true
trueFor raw arrays, std::begin(raw) and std::end(raw) (C++11) return plain pointers. A pointer is an iterator: you can dereference it with * and advance it with ++. Iterators were deliberately designed to look like pointers.
Containers at a Glance
The standard containers fall into four families. The table also tells you which chapter covers each one.
| Family | Containers | Typical underlying structure | Order of elements |
|---|---|---|---|
| Sequence | vector, deque, list, forward_list (C++11), array (C++11) | dynamic array, blocks of arrays, doubly/singly linked list, fixed array | Position you choose |
| Ordered associative | set, multiset, map, multimap | balanced binary search tree (red-black tree in common implementations) | Sorted by key |
| Unordered associative (C++11) | unordered_set, unordered_multiset, unordered_map, unordered_multimap | hash table | No meaningful order |
| Container adaptors | stack, queue, priority_queue; flat_set, flat_map and their multi versions (C++23) | built on top of another container | Depends on the adaptor |
Chapter guide: vector is next; then list, deque & array; stack, queue & priority_queue; set & map; and unordered_set & unordered_map. The C++23 flat containers keep their elements in sorted vectors; they are newer and less common in exams, so we only mention them here.
The standard specifies the complexity of operations, not the exact data structure. For example it requires map lookup to be O(log n), which in practice means a balanced tree. This is why the "typical structure" column says typical.
Quick complexity guide
| Operation | vector | list | set / map | unordered_set / unordered_map |
|---|---|---|---|---|
| Access by index | O(1) | not available | not available | not available |
| Search by value / key | O(n) (O(log n) with binary search if sorted) | O(n) | O(log n) | O(1) average, O(n) worst |
| Insert / erase at end | O(1) amortized | O(1) | — | — |
| Insert / erase in middle | O(n) | O(1) given an iterator | O(log n) | O(1) average |
| Elements kept sorted? | no | no | yes | no |
A practical rule used by experienced programmers: start with vector. Choose something else only when you have a clear reason, such as needing fast lookup by key (map/unordered_map), uniqueness (set), or fast insertion at the front (deque).
Iterators in One Page
An iterator is an object that refers to an element of a container and supports moving to another element. At minimum you can dereference it (
*it) and advance it (++it).
Every container has begin(), which refers to the first element, and end(), which refers to the position one past the last element. The pair describes a half-open range [begin, end): the first is included, the last is not.
v = {10, 20, 30, 40}
index: 0 1 2 3
┌──────┬──────┬──────┬──────┐
│ 10 │ 20 │ 30 │ 40 │
└──────┴──────┴──────┴──────┘
▲ ▲
v.begin() v.end() (one past the last: never dereference it!)Why one past the last? Because it makes everything simple: an empty range is just begin == end, the number of elements is end - begin, and a loop is always while (it != end). It also gives algorithms a natural "not found" answer: return end.
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {10, 20, 30, 40};
// begin() points to the first element, end() points ONE PAST the last
for (auto it = v.begin(); it != v.end(); ++it)
std::cout << *it << ' '; // *it gives the element
std::cout << '\n';
auto it = v.begin();
*it = 11; // write through the iterator
it += 2; // jump ahead (vector iterators allow this)
std::cout << "third element: " << *it << '\n';
std::cout << "distance from begin: " << (it - v.begin()) << '\n';
std::cout << "elements in [begin, end): " << (v.end() - v.begin()) << '\n';
std::cout << "first is now: " << v.front() << '\n';
}Output:
10 20 30 40
third element: 30
distance from begin: 2
elements in [begin, end): 4
first is now: 11Not all iterators are equally powerful. A vector iterator can jump (it += 2) and subtract (it - v.begin()), but a list iterator can only step one node at a time. The standard groups iterators into categories:
| Category | Can do | Provided by |
|---|---|---|
| Input / Output | single pass: read (input) or write (output), then ++ | stream iterators |
| Forward | multi-pass, ++ | forward_list, unordered containers |
| Bidirectional | forward plus -- | list, set, map |
| Random access | bidirectional plus it + n, it[n], it2 - it1, < | deque |
| Contiguous (C++20) | random access, and elements are adjacent in memory | vector, array, string, raw pointers |
Algorithms state the category they need. std::sort needs random access iterators, so it works on vector and deque but not on list (that is why list has its own member sort()). We will study iterators thoroughly in the Iterators chapter; for now, begin(), end(), * and ++ are enough.
Algorithms
The algorithms live mostly in <algorithm>, with numeric ones such as accumulate in <numeric>. There are over a hundred of them. They all follow the same pattern: take a range [first, last), do one job, return something useful (often an iterator).
Important properties to remember:
Algorithms work on ranges, not containers, so they cannot change the size of a container. For example,
std::removeonly shifts the kept elements forward; a container member function such aserasemust actually delete the leftovers. We meet this in the vector chapter.Searching algorithms return
lastwhen nothing is found, so always compare withend()before dereferencing.Complexity is specified by the standard:
findandcountare linear,sortis O(n log n),binary_searchis O(log n) comparisons on a sorted range.
The full tour of algorithms comes in the STL Algorithms chapter.
Associative Containers: a Quick Example
Sequence containers keep your order; associative containers organize elements by key. Here is a classic task, counting word frequencies, done with a map and a set:
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
int main() {
std::string text = "to be or not to be that is the question";
std::map<std::string, int> freq; // word -> count, kept sorted by word
std::set<std::string> unique; // each word once, sorted
std::istringstream in(text);
std::string word;
while (in >> word) {
++freq[word]; // missing key starts at 0
unique.insert(word); // duplicates are ignored
}
for (const auto& [w, c] : freq) // C++17 structured binding
std::cout << w << ": " << c << '\n';
std::cout << "Unique words: " << unique.size() << '\n';
}Output:
be: 2
is: 1
not: 1
or: 1
question: 1
that: 1
the: 1
to: 2
Unique words: 8Notice that the words come out in alphabetical order without any sorting by us, because map keeps its keys sorted. The set silently ignored duplicates. Also note that freq[word] creates the entry with value 0 the first time a word is seen; that is very handy here but can surprise you elsewhere (covered in set & map). The const auto& [w, c] syntax is a C++17 structured binding, which unpacks each key/value pair.
Function Objects: Customizing Algorithms
A function object (functor) is any object that can be called with function-call syntax, typically an object of a class that overloads
operator().
In Operator Overloading we saw that classes can define operators. Overloading operator() makes an object callable. Algorithms such as sort accept such an object to decide "which element comes first":
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional> // std::greater
struct Student {
std::string name;
int marks;
};
// A function object (functor): a class with operator()
struct ByMarksDesc {
bool operator()(const Student& a, const Student& b) const {
return a.marks > b.marks;
}
};
void print(const std::vector<int>& v) {
for (int x : v) std::cout << x << ' ';
std::cout << '\n';
}
int main() {
std::vector<int> v = {5, 2, 9, 1, 7};
std::sort(v.begin(), v.end()); // default: operator<
print(v);
std::sort(v.begin(), v.end(), std::greater<int>()); // library functor
print(v);
std::vector<Student> cls = { {"Ravi", 78}, {"Meena", 91}, {"Arjun", 85} };
std::sort(cls.begin(), cls.end(), ByMarksDesc()); // our own functor
for (const Student& s : cls)
std::cout << s.name << ' ' << s.marks << '\n';
ByMarksDesc cmp;
std::cout << std::boolalpha << cmp(cls[0], cls[1]) << '\n'; // call it like a function
}Output:
1 2 5 7 9
9 7 5 2 1
Meena 91
Arjun 85
Ravi 78
trueThe library provides ready-made functors in <functional>: std::less, std::greater, std::plus, std::equal_to and more. Why use an object instead of a plain function pointer? A functor's type tells the compiler exactly which code to call, so the call is easily inlined, and a functor can also carry state (data members). Today you will most often write comparisons as lambda expressions, which are a short way of creating a function object; they get their own chapter, Lambda Expressions.
Container Adaptors
Sometimes you want less functionality on purpose. A stack should only allow push, pop and top. Container adaptors wrap an existing container and expose only that restricted interface:
#include <iostream>
#include <stack>
#include <vector>
int main() {
std::stack<int> st; // an adaptor: uses std::deque<int> inside by default
st.push(1);
st.push(2);
st.push(3);
std::cout << "top = " << st.top() << ", size = " << st.size() << '\n';
st.pop();
std::cout << "after pop, top = " << st.top() << '\n';
std::stack<int, std::vector<int>> st2; // same interface, vector underneath
st2.push(42);
std::cout << "st2.top() = " << st2.top() << '\n';
}Output:
top = 3, size = 3
after pop, top = 2
st2.top() = 42stack and queue use deque by default; priority_queue uses vector and keeps it arranged as a heap. These three adaptors have no iterators, so you cannot run algorithms on them directly (the C++23 flat containers are different: they do provide iterators). Details are in stack, queue & priority_queue.
Modern Addition: Ranges (C++20)
Passing v.begin(), v.end() every time is repetitive and allows silly bugs such as mixing iterators of two different containers. C++20 added the ranges library: constrained versions of the algorithms in namespace std::ranges that accept the whole container, plus lazy views that transform a range without copying it.
#include <iostream>
#include <vector>
#include <algorithm>
#include <ranges>
int main() {
std::vector<int> v = {30, 10, 50, 20, 40};
std::ranges::sort(v); // C++20: pass the container itself
for (int x : v) std::cout << x << ' ';
std::cout << '\n';
std::cout << std::ranges::count(v, 20) << '\n';
for (int x : v | std::views::reverse | std::views::take(3)) // lazy view, no copy
std::cout << x << ' ';
std::cout << '\n';
}Output:
10 20 30 40 50
1
50 40 30 The | pipes the vector through views: reverse walks it backwards and take(3) stops after three elements. No new vector is created; the elements are produced on demand. The classic iterator-pair algorithms are still everywhere (and still on exams), so learn both styles. More in Modern C++ Features (C++11 to C++23).
Headers You Will Use
| Header | Provides |
|---|---|
<vector>, <list>, <deque>, <array>, <forward_list> | sequence containers |
<set>, <map> | ordered associative containers (and their multi versions) |
<unordered_set>, <unordered_map> | hash-based containers |
<stack>, <queue> | stack; queue and priority_queue |
<algorithm> | most algorithms, including std::ranges versions |
<numeric> | accumulate, iota, gcd, lcm and others |
<functional> | less, greater, function and other function objects |
<iterator> | iterator utilities: advance, distance, next, back_inserter |
<ranges> | views such as views::filter, views::reverse (C++20) |
You may see #include <bits/stdc++.h> in competitive programming code. It is a GCC-specific internal header that includes everything; it is not standard C++, does not work on every compiler and slows compilation. Use it only in contests, never in real projects.
Common Mistakes
Dereferencing
end().*std::find(v.begin(), v.end(), x)is undefined behavior whenxis absent. Always compare the result withend()first.Calling
std::sorton alist. It needs random access iterators, so it does not compile (GCC complains about a missingoperator-for list iterators). UsemyList.sort().Mixing iterators from different containers, such as
std::find(a.begin(), b.end(), x). It compiles but is undefined behavior. Thestd::rangesversions avoid this.Expecting algorithms to shrink a container.
std::removedoes not changesize(); you also neederase(or the C++20std::erase).Using an iterator after the container changed. Adding or removing elements can make existing iterators invalid. Each container has its own rules; the vector chapter covers them in detail.
Choosing an exotic container too early. A
list"because insertion is O(1)" is often slower than avectorin practice, because the vector's contiguous memory is far more cache-friendly.
Interview / GATE-Style Questions
Q1. What are the main components of the STL?
Containers, iterators, algorithms and function objects. Container adaptors and allocators are supporting components.
Q2. Why does the STL separate algorithms from containers using iterators?
So that each algorithm is written once and works with every container that supplies suitable iterators. With M containers and N algorithms this needs M + N implementations instead of M × N, and new containers automatically work with all existing algorithms.
Q3. What does end() refer to, and why?
The position one past the last element. Ranges are half-open [begin, end), so an empty range is begin == end, the size is end - begin for random access iterators, and algorithms can return end to mean "not found". Dereferencing end() is undefined behavior.
Q4. Can you use std::sort on std::list? Why or why not?
No. std::sort requires random access iterators, while list provides only bidirectional iterators. Use the member function list::sort(), which is O(n log n) and relinks nodes instead of moving values.
Q5. Which container would you choose for: (a) fast lookup of a roll number's name, kept sorted; (b) fast lookup when order does not matter; (c) a list of marks you mostly append to and read by index?
(a) std::map (O(log n), sorted by key). (b) std::unordered_map (O(1) average). (c) std::vector (amortized O(1) push_back, O(1) indexing).
Q6. What is a functor and why might it be faster than a function pointer passed to sort?
A functor is an object of a class with operator(). Each functor class is a distinct type, so sort is instantiated for it and the compiler knows exactly which function is called and can inline it. With a function pointer the target is a run-time value, which is harder to inline.
Summary
The STL is the template-based part of the standard library: containers, iterators, algorithms and function objects, part of C++ since C++98.
Iterators connect algorithms to containers, so M containers and N algorithms need only M + N implementations.
Ranges are half-open
[begin, end);end()is one past the last element and must never be dereferenced.Container families: sequence, ordered associative, unordered associative (C++11) and adaptors (plus C++23 flat containers).
Iterator categories (input/output, forward, bidirectional, random access, contiguous) decide which algorithms a container supports.
Algorithms work on ranges and cannot change a container's size; they have standard-guaranteed complexities.
Function objects (and later lambdas) customize algorithms; C++20 ranges let you pass whole containers and build lazy views.
Default choice:
vector. That is exactly where the next chapter begins.