Module 7: The Standard Template Library (STL)

The Standard Template Library (STL) provides ready-to-use data structures called containers, so you rarely need to build your own linked list, dynamic array, or hash table from scratch.

C++ STL containers are organized into three primary families:

• Sequence containers (vector, list, deque, array): Keep elements in a linear, sequential order.
• Associative containers (map, set, multimap, multiset): Keep elements strictly sorted by key (implemented as Red-Black Trees) for fast O(log n) search and retrieval.
• Unordered containers (unordered_map, unordered_set): Trade that strict sorting for even faster average O(1) constant-time lookup speed using hash tables.

std::vector is a dynamic array — behaving like a built-in array with contiguous memory layout, but able to grow and shrink automatically as elements are added or removed.

It is the default "go-to" container for most programming tasks because it combines array-like constant O(1) random-access speed with flexible dynamic sizing.

#include <iostream>
#include <vector>
using namespace std;

vector<int> v = {1, 2, 3};
v.push_back(4);    // {1, 2, 3, 4}
cout << v[0];      // 1 (O(1) access)
cout << v.size();  // 4

An iterator is an object that behaves like a pointer and lets you walk through a container's elements one by one, without needing to know how that container is implemented internally (whether a contiguous vector, a linked list node, or a tree node).

Every STL container provides:

• A begin() iterator pointing directly to the first element.
• An end() iterator pointing one position past the last element (the half-open range [begin, end)).

vector<int> v = {10, 20, 30};

for (auto it = v.begin(); it != v.end(); ++it) {
    cout << *it << " "; // Dereferencing iterator gives element: 10 20 30
}

std::map stores key-value pairs sorted by key (using self-balancing Red-Black Trees), giving fast O(log n) lookup by key much like a dictionary.

std::set stores only unique values in sorted order, and is ideal whenever you simply need to check membership or eliminate duplicates.

#include <map>
#include <set>
using namespace std;

// std::map
map<string, int> ages;
ages["Sam"] = 21;
cout << ages["Sam"]; // 21

// std::set (duplicates discarded, sorted)
set<int> s = {3, 1, 2, 1}; // stored as {1, 2, 3}

The <algorithm> header provides ready-made, highly optimized functions — sort, find, count, reverse, binary_search, and many more — that work across any container through iterators.

This means you almost never need to hand-write a sorting or searching algorithm yourself in production C++.

#include <algorithm>
#include <vector>
using namespace std;

vector<int> v = {5, 2, 8, 1};

// Sorts in O(n log n) Introsort:
sort(v.begin(), v.end()); // {1, 2, 5, 8}

// Finds element through iterators:
auto it = find(v.begin(), v.end(), 8);
if (it != v.end()) {
    cout << "Found at index: " << distance(v.begin(), it);
}