The Standard Template Library — vectors, maps, strings, algorithms — is C++'s killer app. Master it and you can replace 80% of hand-written loops with <algorithm> calls, get tested-by-millions code for free, and gain measurable performance from compiler-optimised templates. This post covers function templates, class templates, and the most-used STL containers + algorithms.

Series map: 00 Setup → 01 Syntax & Types → 02 Pointers & Memory → 03 Classes & OOP → 04 Templates & STL (this post) → 05 Modern C++ → (future).

Learning Outcome

Define and call function templates and class templates.
Use the main STL containers: vector, array, deque, list, map, unordered_map, set, string.
Use iterators to traverse and mutate containers.
Use <algorithm>: sort, find, count, transform, for_each, accumulate.
Understand iterator categories (forward / bidirectional / random-access).
Pick the right container based on access patterns.

Chapter 1 — Function templates

1
2
3
4
5
6
7
8
9 template <typename T>
T max_value(T a, T b) {
    return (a > b) ? a : b;
}
 
max_value(3, 4);            // T deduced as int
max_value(3.5, 2.1);        // T deduced as double
max_value(std::string{"abc"}, std::string{"abd"});  // T as std::string

The compiler generates a separate version of the function for each T you use. This is compile-time code generation — no runtime cost.

Multiple parameters

1
2
3
4
5
6
7 template <typename T, typename U>
auto add(T a, U b) {
    return a + b;
}
 
add(3, 4.5);                // returns double

Explicit specialisation

1
2
3
4
5
6 template <typename T>
std::string describe(T x) { return "generic"; }
 
template <>
std::string describe(int x) { return "an int"; }      // specialised

Rare in modern code — usually function overloading is clearer.

Chapter 2 — Class templates

1
2
3
4
5
6
7
8
9
10
11
12 template <typename T>
class Box {
    T value_;
public:
    Box(T v) : value_(std::move(v)) {}
    const T& get() const { return value_; }
    void set(T v) { value_ = std::move(v); }
};
 
Box<int>    bi(5);
Box<std::string> bs("hello");

Each Box<T> is a distinct type generated at compile time.

C++17 added CTAD (class template argument deduction):

1
2
3 Box b1(5);              // deduces Box<int>
Box b2(std::string{"x"});  // deduces Box<std::string>

Chapter 3 — std::vector (the workhorse)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 #include <vector>
 
std::vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
 
v[0];                   // 10 — no bounds check
v.at(0);                // 10 — throws if out of bounds
v.size();               // 3
v.empty();              // false
v.front();              // 10
v.back();               // 30
v.clear();              // empty
 
std::vector<int> w{1, 2, 3, 4, 5};
w.pop_back();           // remove last
w.insert(w.begin() + 1, 99);   // insert at position
w.erase(w.begin());     // remove first
 
for (int x : w) std::cout << x << " ";

Internally a dynamic array. Amortised O(1) push_back, O(1) random access, O(n) insert/erase in middle.

Trick: if you know the final size, v.reserve(N) ahead of time to prevent reallocations.

Chapter 4 — Other key containers

Container	Underlying	Access	Insert/erase	When to use
`vector<T>`	dynamic array	O(1) random	O(1) at end, O(n) middle	default container
`array<T, N>`	fixed array	O(1)	n/a	size known at compile time
`deque<T>`	segmented array	O(1) random	O(1) both ends	queue-like patterns
`list<T>`	doubly linked	O(n)	O(1) anywhere if iterator known	rarely useful
`map<K, V>`	balanced BST	O(log n)	O(log n)	keys ordered
`unordered_map<K, V>`	hash table	O(1) avg	O(1) avg	keys NOT ordered
`set<T>`	balanced BST	O(log n)	O(log n)	sorted unique values
`unordered_set<T>`	hash table	O(1) avg	O(1) avg	fast membership
`string`	dynamic array of chars	O(1)	O(n) middle	text

What is inside the main STL containers and what each operation costs

std::map example

1
2
3
4
5
6
7
8
9
10
11
12
13 #include <map>
std::map<std::string, int> ages;
ages["Ada"] = 30;
ages["Bob"] = 25;
 
if (auto it = ages.find("Ada"); it != ages.end()) {
    std::cout << it->second;       // 30
}
 
for (const auto& [name, age] : ages) {   // C++17 structured binding
    std::cout << name << ": " << age << "\n";
}

std::unordered_map (hash table — usually faster)

1
2
3
4
5
6 #include <unordered_map>
std::unordered_map<std::string, int> counts;
for (const auto& word : words) {
    counts[word]++;
}

Default to unordered_map unless you need keys in sorted order.

Chapter 5 — Iterators

Every STL container has begin() and end(). end() is one past the last element.

1
2
3
4
5 std::vector<int> v{10, 20, 30};
for (auto it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << " ";       // dereference like a pointer
}

Categories (most→least powerful):

Random-access: vector, array, deque. Supports it + n, it[i], it1 - it2.
Bidirectional: list, map, set. Supports ++it, --it.
Forward: forward-only.
Input / Output: single-pass only (e.g., reading from a stream).

Range-based for is iterators under the hood

1
2 for (auto& x : v) { ... }      // syntactic sugar for an iterator loop

Use range-for. The classic iterator loop is for cases where you need the iterator itself.

Const iterators

1
2
3
4 for (auto it = v.cbegin(); it != v.cend(); ++it) {
    // *it is const — can't modify through it
}

Chapter 6 — std::string

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 #include <string>
 
std::string s = "Hello";
s += ", World";
s.size();                       // 12
s.length();                     // same
s.empty();                      // false
s[0];                           // 'H'
s.substr(0, 5);                 // "Hello"
s.find("World");                // 7 (or npos if not found)
 
// integer ↔ string
std::string n = std::to_string(42);
int i = std::stoi("123");
double d = std::stod("3.14");

C++17 added std::string_view — a non-owning view into a string. Use for function parameters when you don't need to own/modify:

1
2
3
4
5 #include <string_view>
void print(std::string_view sv) {       // takes string, char*, literal, etc.
    std::cout << sv << "\n";
}

Chapter 7 — The `<algorithm>` header

The single most underused header. Replaces hand-written loops with descriptive, optimised one-liners.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43 #include <algorithm>
#include <numeric>      // accumulate
#include <vector>
 
std::vector<int> v{5, 2, 8, 1, 9, 3};
 
// sort
std::sort(v.begin(), v.end());                  // ascending
std::sort(v.begin(), v.end(), std::greater{});  // descending
 
// find
auto it = std::find(v.begin(), v.end(), 8);
if (it != v.end()) { /* found */ }
 
// count
int n_evens = std::count_if(v.begin(), v.end(), [](int x){ return x % 2 == 0; });
 
// sum
int total = std::accumulate(v.begin(), v.end(), 0);
 
// transform
std::vector<int> squares(v.size());
std::transform(v.begin(), v.end(), squares.begin(), [](int x){ return x * x; });
 
// for_each
std::for_each(v.begin(), v.end(), [](int x){ std::cout << x << " "; });
 
// any / all / none of
bool has_neg = std::any_of(v.begin(), v.end(), [](int x){ return x < 0; });
bool all_pos = std::all_of(v.begin(), v.end(), [](int x){ return x > 0; });
 
// min / max element
auto mn = std::min_element(v.begin(), v.end());
auto mx = std::max_element(v.begin(), v.end());
 
// reverse
std::reverse(v.begin(), v.end());
 
// unique (after sort)
std::sort(v.begin(), v.end());
auto last = std::unique(v.begin(), v.end());
v.erase(last, v.end());

Trick: before writing a loop on a container, search cppreference's algorithm list — there's almost always a standard one.

Lambdas (recap)

1
2
3
4
5
6
7
8
9
10
11 auto is_even = [](int x){ return x % 2 == 0; };
auto add    = [](int a, int b){ return a + b; };
 
// with capture
int threshold = 10;
auto over = [threshold](int x){ return x > threshold; };
 
// capture by reference
int count = 0;
std::for_each(v.begin(), v.end(), [&count](int){ ++count; });

[ ] is the capture list. [=] captures everything by value, [&] by reference. Be explicit when possible.

Chapter 8 — C++20 ranges (brief)

C++20 introduced ranges — algorithms that take the container directly + composable views.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 #include <ranges>
#include <vector>
#include <algorithm>
 
std::vector<int> v{1, 2, 3, 4, 5, 6};
 
// pipeline
auto result = v
    | std::views::filter([](int x){ return x % 2 == 0; })
    | std::views::transform([](int x){ return x * x; });
 
for (int x : result) std::cout << x << " ";   // 4 16 36
 
// direct algorithm
std::ranges::sort(v);     // no begin()/end() needed!

Cleaner than iterator-pair style. Worth learning if your compiler supports C++20.

Chapter 9 — Choosing a container

Decision tree:

Default = std::vector. Right answer ~80% of the time.
Need keys → values? std::unordered_map (or map if you need sorted iteration).
Need unique-set membership? std::unordered_set (or set if sorted).
Inserting at both ends? std::deque.
Fixed-size? std::array (zero overhead, size in the type).
Lots of middle insertions and you have iterators? std::list — but profile first; it's often slower than vector due to cache effects.

Rule: benchmark before choosing anything other than vector for performance reasons. The cache wins almost every fight.

Practice Exercises

Exercise 1 — Template min3

Write a function template min3(a, b, c) that returns the minimum of three values of the same type.

Solution

1
2
3
4
5 template <typename T>
T min3(T a, T b, T c) {
    return std::min({a, b, c});       // braced-list overload
}

Exercise 2 — Word count

Read words from stdin until EOF; print each unique word and its count, sorted by count descending.

Solution sketch

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 #include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <string>
 
int main() {
    std::unordered_map<std::string, int> counts;
    std::string w;
    while (std::cin >> w) counts[w]++;
 
    std::vector<std::pair<std::string, int>> sorted(counts.begin(), counts.end());
    std::sort(sorted.begin(), sorted.end(),
              [](auto& a, auto& b){ return a.second > b.second; });
 
    for (const auto& [word, n] : sorted) {
        std::cout << word << ": " << n << "\n";
    }
}

Exercise 3 — Sum of squares of even numbers

Given std::vector<int>, return the sum of squares of even values. Use STL only — no manual loop.

Solution

1
2
3
4
5 int sum_sq_even(const std::vector<int>& v) {
    return std::accumulate(v.begin(), v.end(), 0,
        [](int acc, int x){ return x % 2 == 0 ? acc + x * x : acc; });
}

Exercise 4 — Stack template

Implement template <typename T> class Stack with push, pop, top, empty, size. Internally use std::vector<T>.

Exercise 5 — Find duplicates

Given std::vector<int>, return a std::vector<int> of values that appear more than once (each duplicate listed once).

Solution sketch

1
2
3
4
5
6
7
8 std::vector<int> dups(const std::vector<int>& v) {
    std::unordered_map<int, int> count;
    for (int x : v) count[x]++;
    std::vector<int> r;
    for (const auto& [k, n] : count) if (n > 1) r.push_back(k);
    return r;
}

Cheat-sheet

What	How
Function template	`template<typename T> T f(T a, T b)`
Class template	`template<typename T> class Box { T v; };`
CTAD	`Box b(5); // deduces Box<int>`
Vector	`std::vector<int> v;`
Map (sorted)	`std::map<K, V>`
Map (hash)	`std::unordered_map<K, V>`
Set	`std::set<T>` / `std::unordered_set<T>`
String	`std::string`
Iterator	`auto it = v.begin();`
End iterator	one past last
Algorithm sort	`std::sort(v.begin(), v.end())`
Algorithm find	`std::find(b, e, value)`
Algorithm accumulate	`std::accumulate(b, e, init)`
Lambda	`[capture](args){ body }`
Structured binding	`for (auto& [k, v] : m)`
Range pipe	`v \| views::filter(p) \| views::transform(f)`

What's next

Post 05 — the final base post — covers modern C++ essentials: std::unique_ptr / std::shared_ptr, move semantics in practice, auto, range-based for, lambdas in depth, constexpr, and a glimpse of C++20 concepts.