Chapter 34 of 48

Introduction to the STL

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 found

Compare 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:

ComponentWhat it isExamples
ContainersObjects that store a collection of elements and manage their memoryvector, list, map, unordered_set
IteratorsPointer-like objects that refer to an element and can move to the next onev.begin(), v.end()
AlgorithmsFunction templates that operate on a range of elements given by iteratorssort, find, count, accumulate
Function objectsObjects that can be called like functions, used to customize algorithmsstd::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"              elements

Why 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
true

For 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.

FamilyContainersTypical underlying structureOrder of elements
Sequencevector, deque, list, forward_list (C++11), array (C++11)dynamic array, blocks of arrays, doubly/singly linked list, fixed arrayPosition you choose
Ordered associativeset, multiset, map, multimapbalanced binary search tree (red-black tree in common implementations)Sorted by key
Unordered associative (C++11)unordered_set, unordered_multiset, unordered_map, unordered_multimaphash tableNo meaningful order
Container adaptorsstack, queue, priority_queue; flat_set, flat_map and their multi versions (C++23)built on top of another containerDepends 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

Operationvectorlistset / mapunordered_set / unordered_map
Access by indexO(1)not availablenot availablenot available
Search by value / keyO(n) (O(log n) with binary search if sorted)O(n)O(log n)O(1) average, O(n) worst
Insert / erase at endO(1) amortizedO(1)——
Insert / erase in middleO(n)O(1) given an iteratorO(log n)O(1) average
Elements kept sorted?nonoyesno

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: 11

Not 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:

CategoryCan doProvided by
Input / Outputsingle pass: read (input) or write (output), then ++stream iterators
Forwardmulti-pass, ++forward_list, unordered containers
Bidirectionalforward plus --list, set, map
Random accessbidirectional plus it + n, it[n], it2 - it1, <deque
Contiguous (C++20)random access, and elements are adjacent in memoryvector, 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::remove only shifts the kept elements forward; a container member function such as erase must actually delete the leftovers. We meet this in the vector chapter.

  • Searching algorithms return last when nothing is found, so always compare with end() before dereferencing.

  • Complexity is specified by the standard: find and count are linear, sort is O(n log n), binary_search is 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: 8

Notice 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
true

The 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() = 42

stack 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

HeaderProvides
<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 when x is absent. Always compare the result with end() first.

  • Calling std::sort on a list. It needs random access iterators, so it does not compile (GCC complains about a missing operator- for list iterators). Use myList.sort().

  • Mixing iterators from different containers, such as std::find(a.begin(), b.end(), x). It compiles but is undefined behavior. The std::ranges versions avoid this.

  • Expecting algorithms to shrink a container. std::remove does not change size(); you also need erase (or the C++20 std::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 a vector in 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.