Chapter 6a - Templates & the STL

Why Templates?

Without templates, you'd need a separate max function for every type:

int    maxInt(int a,    int b)    { return a > b ? a : b; }
double maxDouble(double a, double b) { return a > b ? a : b; }
string maxString(string a, string b) { return a > b ? a : b; }

Templates let you write the logic once and let the compiler generate the right version for any type.

---

Function Templates

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

int main() {
    cout << maxOf(3, 7)           << endl;  // 7
    cout << maxOf(3.14, 2.71)     << endl;  // 3.14
    cout << maxOf('z', 'a')       << endl;  // z
}

The compiler generates a separate maxOf<int>, maxOf<double>, etc. at compile time — zero runtime overhead.

Multiple Type Parameters

template <typename T, typename U>
void printPair(T first, U second) {
    cout << "(" << first << ", " << second << ")" << endl;
}

🧪 Function templates

---

Challenge: max of two

Finish maxOf so it returns the larger of two ints.

a	b	Return
3	7	7
10	2	10

---

Class Templates

You can template entire classes. This is how std::vector<T>, std::stack<T>, and std::pair<T,U> work internally.

template <typename T>
class Box {
private:
    T value;
public:
    Box(T v) : value(v) {}
    T get() const { return value; }
    void set(T v) { value = v; }
};

Template Stack (Generic)

template <typename T>
class Stack {
    vector<T> data;
public:
    void push(T val)    { data.push_back(val); }
    void pop()          { data.pop_back(); }
    T    top()  const   { return data.back(); }
    bool empty() const  { return data.empty(); }
};

🧪 Template Pair

---

Template Specialization

You can provide a custom implementation for a specific type while keeping the generic version for everything else.

template <typename T>
void describe(T val) {
    cout << "Value: " << val << endl;
}

template <>
void describe<bool>(bool val) {
    cout << "Boolean: " << (val ? "true" : "false") << endl;
}

🧪 Specialization

---

Mini quiz — class templates and specialization

Quiz

Class templates

1 / 3

What does this mean?

template <typename T> class Box

Pick an answer to see if you are right.

---

The Standard Template Library (STL)

The STL provides ready-made containers, algorithms, and iterators. Everything works generically through templates.

STL Containers Overview

Container	Header	Ordered?	Unique keys?	Access
vector<T>	<vector>	Insertion order	—	O(1) index
list<T>	<list>	Insertion order	—	O(1) insert
deque<T>	<deque>	Insertion order	—	O(1) front+back
stack<T>	<stack>	LIFO	—	O(1) top
queue<T>	<queue>	FIFO	—	O(1) front
priority_queue<T>	<queue>	Max-heap	—	O(log n)
set<T>	<set>	Sorted	Yes	O(log n)
unordered_set<T>	<unordered_set>	No	Yes	O(1) avg
map<K,V>	<map>	Sorted by key	Yes	O(log n)
unordered_map<K,V>	<unordered_map>	No	Yes	O(1) avg

---

Iterators

An iterator is a generalization of a pointer — it points to an element in a container and can be advanced.

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

for (auto it = v.begin(); it != v.end(); ++it) {
    cout << *it << " ";
}

---

Mini quiz — STL and iterators

Quiz

STL and iterators

1 / 3

The STL is…

Pick an answer to see if you are right.

---

STL Algorithms (<algorithm>)

STL algorithms work on any container through iterators.

sort(v.begin(), v.end());
reverse(v.begin(), v.end());
int s = accumulate(v.begin(), v.end(), 0);

Lambda Functions with Algorithms

A lambda is an anonymous function written inline.

int evens = count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });

Lambda syntax: [capture](parameters) { body }

Capture	Meaning
[]	No captures
[x]	Capture x by value
[&x]	Capture x by reference
[=]	Capture all locals by value
[&]	Capture all locals by reference

🧪 Full algorithm example

---

priority_queue — Heap

A priority_queue always gives you the largest (or smallest) element in O(log n).

priority_queue<int> maxHeap;
maxHeap.push(3);
maxHeap.push(9);
cout << maxHeap.top();  // 9

Application: Top K Elements

🧪 Top K

---

Mini quiz — algorithms and heaps

Quiz

Algorithms and priority_queue

1 / 3

What does this mean?

sort(v.begin(), v.end())

Pick an answer to see if you are right.

---

Exercises

Activity: Generic min and clamp

Write a template function myMin(a, b) and clamp(val, lo, hi) that works for any comparable type. Test with int, double, and char.

📒 Solution