SolutionGigsSolutionGigs
Free Handbook · Every example compiled & verified

Templates & the STL

Class templates, deduction and CTAD, the STL containers, iterators and algorithms, lambdas as comparators, C++20 ranges and views, and concepts.

0 / 145 lessons🔥 0 day streak
ShareXLinkedIn

Module 09 · what you'll be able to do

  • Write a class template with type and non-type parameters, and let the compiler deduce template arguments
  • Choose between vector, map, unordered_map and set, and walk any container with iterators
  • Replace hand-written loops with std::sort, find_if, count_if, transform, accumulate and lower_bound
  • Compose lazy pipelines with C++20 ranges and views
  • Constrain templates with concepts so a wrong type fails with a readable error
01

Class templates

Module 03 showed function templates. A class template is the same idea for a type: write the class once with a placeholder T, and the compiler generates a separate, fully typed class for every T you use (Stack<int>, Stack<std::string>). Nothing is boxed or type-erased, so the generated code is as fast as if you had written each version by hand. Template parameters can also be values, such as a size: std::array<int, 4> works this way.

C++main.cpp
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

template <typename T>
class Stack {
public:
    void push(const T& value) { items_.push_back(value); }
    T pop() {
        if (items_.empty()) throw std::out_of_range("pop on empty stack");
        T top = items_.back();
        items_.pop_back();
        return top;
    }
    bool empty() const { return items_.empty(); }
    std::size_t size() const { return items_.size(); }
private:
    std::vector<T> items_;
};

template <typename T, std::size_t N>
class RingBuffer {  // keeps only the last N values
public:
    void add(const T& v) { data_[next_ % N] = v; ++next_; }
    std::size_t capacity() const { return N; }
    T latest() const { return data_[(next_ - 1) % N]; }
private:
    T data_[N]{};
    std::size_t next_ = 0;
};

int main() {
    Stack<std::string> words;
    words.push("templates");
    words.push("are");
    words.push("fun");
    while (!words.empty()) std::cout << words.pop() << ' ';
    std::cout << '\n';

    RingBuffer<int, 3> recent;
    for (int i = 1; i <= 5; ++i) recent.add(i * 10);
    std::cout << "capacity " << recent.capacity() << ", latest " << recent.latest() << '\n';
}
Outputcompiled & run with real C++
fun are templates 
capacity 3, latest 50

N is a compile-time constant, so T data_[N] is a fixed array inside the object: no heap allocation at all.

Your turn

Add const T& peek() const to Stack that throws the same exception when empty, then use it before popping.

Templates live in headers
The compiler needs the full template definition wherever it generates a version, so class templates are written entirely in header files, not split into .h and .cpp like ordinary classes. That is also why template-heavy code compiles slowly.
02

Template argument deduction and CTAD

For function templates, the compiler deduces T from the arguments, so you rarely write max<int>(a, b). Since C++17, class template argument deduction (CTAD) does the same for constructors: std::vector v{1, 2, 3} is a std::vector<int> and std::pair p{1, 2.5} is a std::pair<int, double>. When the arguments disagree, deduction fails, and you either convert an argument or name the type explicitly.

C++main.cpp
#include <iostream>
#include <string>
#include <utility>
#include <vector>

template <typename T>
T biggest(T a, T b) { return a > b ? a : b; }

int main() {
    std::cout << biggest(3, 9) << '\n';                  // T = int
    std::cout << biggest(2.5, 1.5) << '\n';              // T = double
    std::cout << biggest<double>(3, 9.5) << '\n';        // explicit: int 3 converts to double
    std::cout << biggest(std::string("pear"), std::string("apple")) << '\n';

    std::vector v{1, 2, 3};                              // CTAD: std::vector<int>
    std::pair p{7, std::string("seven")};                // std::pair<int, std::string>
    std::cout << v.size() << ' ' << p.first << ' ' << p.second << '\n';
}
Outputcompiled & run with real C++
9
2.5
9.5
pear
3 7 seven

biggest(3, 9.5) without <double> would not compile: the first argument says T = int, the second T = double. Strings compare alphabetically, so "pear" is bigger than "apple".

03

The STL containers you use every day

The Standard Template Library's containers are class templates you instantiate with your element type. Four cover most code: std::vector (the default sequence), std::map (sorted key-value pairs, a balanced tree), std::unordered_map (hash table, fastest lookups, no order) and std::set / std::unordered_set (unique values). The full cost table is in Module 13.

C++main.cpp
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>

int main() {
    std::vector<std::string> words{"pear", "fig", "apple", "fig", "kiwi", "pear", "fig"};

    std::map<std::string, int> counts;               // sorted by key
    for (const auto& w : words) ++counts[w];         // operator[] inserts 0 first time
    for (const auto& [word, n] : counts) std::cout << word << '=' << n << ' ';
    std::cout << '\n';

    std::set<std::string> unique(words.begin(), words.end());
    std::cout << unique.size() << " unique, first " << *unique.begin() << '\n';

    std::unordered_map<std::string, double> price{{"fig", 0.5}, {"kiwi", 0.3}};
    if (auto it = price.find("fig"); it != price.end()) std::cout << "fig costs " << it->second << '\n';
    std::cout << std::boolalpha << price.contains("mango") << '\n';  // C++20
}
Outputcompiled & run with real C++
apple=1 fig=3 kiwi=1 pear=2 
4 unique, first apple
fig costs 0.5
false

std::map iterates in key order, which is why the counts print alphabetically. Never print an unordered_map and expect a stable order.

Error you will hit

No viable overloaded operator[] on a const map

C++
#include <map>
#include <string>

int main() {
    const std::map<std::string, int> stock{{"apples", 3}};
    int n = stock["apples"];
    return n;
}
main.cpp:6:18: error: no viable overloaded operator[] for type 'const std::map<std::string, int>' (aka 'const map<basic_string<char>, int>')
    6 |     int n = stock["apples"];
      |             ~~~~~^~~~~~~~~
.../c++/v1/map:1095:38: note: candidate function not viable: 'this' argument has type 'const std::map<std::string, int>' (aka 'const map<basic_string<char>, int>'), but method is not marked const
 1095 |   _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k);
      |                                      ^
1 error generated.
Why the compiler said that

operator[] inserts a default value when the key is missing, so it has to modify the map. On a const map (or a map passed as const&) that is impossible, and the compiler rejects the call.

The fix

Use at(), which throws std::out_of_range for a missing key, or find(), which lets you handle the missing case yourself.

C++
#include <map>
#include <string>

int main() {
    const std::map<std::string, int> stock{{"apples", 3}};
    auto it = stock.find("apples");
    int n = (it != stock.end()) ? it->second : 0;
    return n;
}
04

Iterators and erasing safely

An iterator is a generalised pointer into a container: *it reads the element, ++it moves on, and begin()/end() mark the range, with end() one past the last element. Every STL algorithm works on an iterator range, which is what lets one std::find search a vector, a list or a set. Containers offer different categories: a vector has random-access iterators (it + 5 is O(1)), a list only bidirectional ones.

Erasing while iterating is the classic trap: erase invalidates the iterator you erased (and, for a vector, every iterator after it). Use the iterator erase returns, or better, C++20's std::erase_if, which does the whole job in one call.

C++main.cpp
#include <iostream>
#include <map>
#include <vector>

int main() {
    std::vector<int> v{3, 8, 1, 6, 5, 2};
    for (auto it = v.begin(); it != v.end(); ) {
        if (*it % 2 == 0) it = v.erase(it);   // erase returns the next valid iterator
        else ++it;
    }
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';

    std::vector<int> w{3, 8, 1, 6, 5, 2};
    auto removed = std::erase_if(w, [](int x) { return x % 2 == 0; });  // C++20
    std::cout << removed << " removed, " << w.size() << " left\n";

    std::map<std::string, int> stock{{"apple", 0}, {"fig", 4}, {"kiwi", 0}};
    std::erase_if(stock, [](const auto& kv) { return kv.second == 0; });
    for (const auto& [name, qty] : stock) std::cout << name << ':' << qty << '\n';
}
Outputcompiled & run with real C++
3 1 5 
3 removed, 3 left
fig:4
Your turn

Rewrite the first loop with the older erase-remove idiom: v.erase(std::remove_if(v.begin(), v.end(), pred), v.end()). Why does remove_if alone not shrink the vector?

VisualizeErasing even numbers with the returned iteratorStep 1 / 6
for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0) it = v.erase(it);
    else ++it;
}
Line 1

Start at the first element.

Variables now
v{3, 8, 1, 6, 5, 2}
*it3
All 6 steps as a table
StepLineWhat happenedVariables now
11Start at the first element.v = {3, 8, 1, 6, 5, 2} *it = 3
233 is odd: step forward.*it = 8
328 is even: erase it. Everything after it shifts left, and erase returns an iterator to the element that took its place.v = {3, 1, 6, 5, 2} *it = 1
431 is odd: step forward.*it = 6
52Erase 6; the returned iterator points at 5. Writing ++it here instead would have skipped 5.v = {3, 1, 5, 2} *it = 5
625 is odd, step; then erase 2, which returns end().v = {3, 1, 5}
05

Algorithms: stop writing loops by hand

<algorithm> and <numeric> contain over a hundred tested, optimised algorithms. A named algorithm says what the loop does (count_if, any_of, min_element) so the reader does not have to work it out, and it cannot have an off-by-one error. The workhorses:

C++main.cpp
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<int> scores{72, 95, 58, 88, 64, 95, 41};

    std::cout << "sum " << std::accumulate(scores.begin(), scores.end(), 0) << '\n';
    std::cout << "passed " << std::count_if(scores.begin(), scores.end(), [](int s) { return s >= 60; }) << '\n';
    std::cout << "best " << *std::max_element(scores.begin(), scores.end()) << '\n';
    std::cout << std::boolalpha << "any fail? "
              << std::any_of(scores.begin(), scores.end(), [](int s) { return s < 50; }) << '\n';

    auto firstHigh = std::find_if(scores.begin(), scores.end(), [](int s) { return s > 90; });
    std::cout << "first > 90 at index " << (firstHigh - scores.begin()) << '\n';

    std::vector<int> curved(scores.size());
    std::transform(scores.begin(), scores.end(), curved.begin(), [](int s) { return std::min(100, s + 5); });

    std::sort(curved.begin(), curved.end());
    for (int s : curved) std::cout << s << ' ';
    std::cout << '\n';

    auto at = std::lower_bound(curved.begin(), curved.end(), 70);   // binary search, sorted input
    std::cout << "first >= 70: " << *at << '\n';
}
Outputcompiled & run with real C++
sum 513
passed 5
best 95
any fail? true
first > 90 at index 1
46 63 69 77 93 100 100 
first >= 70: 77

accumulate's starting value sets the result type: 0 sums as int, 0.0 as double, and 0LL avoids overflow on big totals.

Your turn

Use std::partition to move all passing scores (>= 60) to the front, then print how many passed using the iterator it returns.

06

Lambdas as comparators and sorting by several keys

std::sort takes an optional comparator: a function that returns true when its first argument should come before the second. A lambda is the natural way to write one. For several keys, compare tuples with std::tie, which compares element by element. std::sort is not stable; when equal elements must keep their original order, use std::stable_sort.

C++main.cpp
#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>

struct Person {
    std::string name;
    std::string dept;
    int salary;
};

int main() {
    std::vector<Person> people{
        {"Ravi", "data", 90}, {"Ana", "web", 75}, {"Chen", "data", 120}, {"Bola", "web", 75},
    };

    // dept ascending, then salary descending
    std::stable_sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return std::tie(a.dept, b.salary) < std::tie(b.dept, a.salary);
    });
    for (const auto& p : people) std::cout << p.name << ' ' << p.dept << ' ' << p.salary << '\n';
}
Outputcompiled & run with real C++
Chen data 120
Ravi data 90
Ana web 75
Bola web 75

Swapping a.salary and b.salary inside the tie reverses that key. Ana and Bola tie on both keys, so stable_sort keeps them in their original order.

A comparator must be a strict weak ordering
Use <, never <=. A comparator that returns true for equal elements breaks the algorithm's assumptions: results can be wrong, and some implementations read past the end of the range.
07

C++20 ranges and views

The ranges library takes whole containers instead of iterator pairs (std::ranges::sort(v)) and adds views: lazy, composable adaptors joined with |. v | std::views::filter(pred) | std::views::transform(f) builds no intermediate vectors; each element flows through the pipeline only when the loop asks for it. A view does not own its data, so the underlying container must outlive it.

C++main.cpp
#include <algorithm>
#include <iostream>
#include <ranges>
#include <vector>

int main() {
    std::vector<int> nums{5, 12, 7, 20, 3, 18, 9, 30};

    std::ranges::sort(nums);
    for (int n : nums) std::cout << n << ' ';
    std::cout << '\n';

    auto evensSquared = nums
        | std::views::filter([](int n) { return n % 2 == 0; })
        | std::views::transform([](int n) { return n * n; });
    for (int n : evensSquared) std::cout << n << ' ';
    std::cout << '\n';

    for (int n : std::views::iota(1) | std::views::take(5)) std::cout << n * 10 << ' ';  // infinite, then take 5
    std::cout << '\n';

    for (int n : nums | std::views::reverse | std::views::take(3)) std::cout << n << ' ';
    std::cout << '\n';
}
Outputcompiled & run with real C++
3 5 7 9 12 18 20 30 
144 324 400 900 
10 20 30 40 50 
30 20 18

std::views::iota(1) is an infinite sequence; it is safe because take(5) stops asking after five elements. That only works because views are lazy.

Your turn

Print the first three numbers above 10 in nums, doubled, using filter, transform and take in one pipeline.

08

Concepts: constraining templates

An unconstrained template accepts any type and fails deep inside its body when the type does not fit, producing pages of errors. A concept (C++20) states the requirement up front: template <std::integral T> accepts only integer types. The standard library ships many (std::integral, std::floating_point, std::totally_ordered, std::ranges::range), and you can write your own with requires expressions.

C++main.cpp
#include <concepts>
#include <iostream>
#include <string>
#include <vector>

template <std::integral T>
T half(T value) { return value / 2; }

template <typename T>
concept HasArea = requires(const T& shape) {
    { shape.area() } -> std::convertible_to<double>;
};

struct Square { double side; double area() const { return side * side; } };
struct Circle { double r; double area() const { return 3.14159 * r * r; } };

template <HasArea... Shapes>
double totalArea(const Shapes&... shapes) {
    return (shapes.area() + ...);   // fold expression over the pack
}

int main() {
    std::cout << half(11) << ' ' << half(40L) << '\n';
    std::cout << totalArea(Square{2}, Circle{1}, Square{3}) << '\n';
}
Outputcompiled & run with real C++
5 20
16.1416

HasArea requires an area() member that returns something convertible to double. Any type that has one qualifies, with no base class or inheritance needed.

Error you will hit

Constraints not satisfied

C++
#include <concepts>
#include <iostream>
#include <string>

template <std::integral T>
T half(T value) {
    return value / 2;
}

int main() {
    std::cout << half(10) << '\n';
    std::cout << half(std::string("ten")) << '\n';
}
main.cpp:12:18: error: no matching function for call to 'half'
   12 |     std::cout << half(std::string("ten")) << '\n';
      |                  ^~~~
main.cpp:6:3: note: candidate template ignored: constraints not satisfied [with T = std::string]
    6 | T half(T value) {
      |   ^
main.cpp:5:11: note: because 'std::string' does not satisfy 'integral'
    5 | template <std::integral T>
      |           ^
.../c++/v1/__concepts/arithmetic.h:28:20: note: because 'is_integral_v<std::string>' evaluated to false
   28 | concept integral = is_integral_v<_Tp>;
      |                    ^
1 error generated.
Why the compiler said that

The template only accepts integral types, and std::string is not one. Because of the concept, the compiler says exactly that, at the call site, instead of failing inside the function body on value / 2.

The fix

Pass a type that satisfies the concept (convert the text to a number first), or widen the constraint if the function really should accept more types.

C++
#include <concepts>
#include <iostream>
#include <string>

template <std::integral T>
T half(T value) {
    return value / 2;
}

int main() {
    std::cout << half(10) << '\n';
    std::cout << half(std::stoi("10")) << '\n';
}
Error you will hit

std::sort on a std::list: invalid operands to binary expression

C++
#include <algorithm>
#include <list>

int main() {
    std::list<int> scores{42, 7, 19};
    std::sort(scores.begin(), scores.end());
}
In file included from main.cpp:1:
.../c++/v1/__algorithm/make_heap.h:37:31: error: invalid operands to binary expression ('std::__list_iterator<int, void *>' and 'std::__list_iterator<int, void *>')
   37 |   const __diff_t __n = __last - __first;
      |                        ~~~~~~ ^ ~~~~~~~
...
main.cpp:6:10: note: in instantiation of function template specialization 'std::sort<std::__list_iterator<int, void *>>' requested here
    6 |     std::sort(scores.begin(), scores.end());
      |          ^
Why the compiler said that

std::sort needs random-access iterators (it computes last - first and jumps around the range). A linked list only has bidirectional iterators. The error is reported deep inside the library; the useful line is the "in instantiation … requested here" note that points back at your code.

The fix

Call the list's own sort() member, which relinks nodes instead of indexing. Or use a std::vector, which is usually the better container anyway. std::ranges::sort(scores) would fail too, but with a shorter "constraints not satisfied" message.

C++
#include <list>

int main() {
    std::list<int> scores{42, 7, 19};
    scores.sort();
}
Class template
A blueprint for a family of classes, instantiated once per set of template arguments (Stack, Stack).
CTAD
Class template argument deduction (C++17): the compiler deduces a class template's arguments from its constructor arguments.
Iterator
A generalised pointer into a container; algorithms operate on [begin, end) iterator ranges.
Iterator invalidation
An operation such as erase or push_back making existing iterators, pointers or references unusable.
Comparator
A function returning true when the first argument should come before the second; must be a strict weak ordering.
View
A lazy, non-owning range adaptor (filter, transform, take) composed with |.
Concept
A named compile-time requirement on template arguments, such as std::integral.
Quick check

Why does std::map<std::string, int> m; if (m["x"] == 0) {} change the map?

← Module 08Inheritance & PolymorphismModule 10 →Modern C++

Frequently asked questions

What is the STL in C++?
The Standard Template Library is the part of the C++ standard library made of class and function templates: containers (vector, map, unordered_map, set, deque, list), iterators that walk them, and algorithms (sort, find, count, transform, accumulate) that work on any iterator range.
What are C++20 concepts for?
Concepts state what a template needs from its type arguments, such as std::integral or a custom requirement like "has an area() method". Calls with a wrong type fail at the call site with a short error saying which requirement was not met, instead of pages of errors from inside the template body.
Should I use std::map or std::unordered_map?
Use std::unordered_map by default for fast lookups by key (hash table, O(1) on average). Use std::map when you need the keys in sorted order, range queries such as lower_bound, or predictable iteration order (balanced tree, O(log n)).

Finish the C++ handbook, then get hired

Sit the exam for your certificate, run your resume through the ATS checker, and see the jobs that ask for exactly this.

Check my resume
Found this course useful? Share it.
ShareXLinkedIn

Comments

0

Join the conversation. Sign in to leave a comment — we'd love to hear your thoughts.