Step 3 of 8
Class templates
Classes can be templates too. That's exactly how std::vector<T>, std::map<K, V> and std::unique_ptr<T> work: one class definition, and you choose the types when you use it.
#include <iostream>
#include <string>
#include <vector>
template <typename T>
class Queue {
public:
void enqueue(const T& v) { items_.push_back(v); }
T dequeue() {
T front = items_[head_];
head_++;
return front;
}
int size() const { return (int)items_.size() - head_; }
bool empty() const { return size() == 0; }
private:
std::vector<T> items_;
int head_ = 0;
};
int main() {
Queue<std::string> q;
q.enqueue("first");
q.enqueue("second");
std::cout << q.dequeue() << ", " << q.size() << " left\n";
Queue<int> nums;
for (int i = 1; i <= 3; i++) nums.enqueue(i * i);
while (!nums.empty()) std::cout << nums.dequeue() << " ";
std::cout << "\n";
}
first, 1 left
1 4 9
How it works
template <typename T>goes before the class. Inside,Tis used for members, parameters and return types.- When you use a class template, you usually write the type in angle brackets:
Queue<std::string>,Queue<int>. Each is a separate class generated by the compiler. - Member functions defined inside the class body need nothing extra. (Defined outside, they'd need
template <typename T>again andQueue<T>::before the name.) - Storing items in a
std::vector<T>gives you memory management for free. That's the rule of zero at work.
This queue is simple but wasteful: dequeued items stay in the vector. A stack has no such problem, because it adds and removes at the same end, which is exactly what push_back, back and pop_back do.
Your task
Write a class template Stack<T> with push(const T&), pop() (returns the top value and removes it; assume non-empty), bool empty() const and int size() const. Store items in a std::vector<T>.
Challenge 2
Write a class template Registry<K, V> backed by a std::map<K, V>: void set(const K& key, const V& value), V get_or(const K& key, const V& fallback) const (the stored value, or fallback if the key is missing), and int size() const.
Challenge 3
Write a class template Grid<T> with a constructor Grid(int rows, int cols, const T& fill), T& at(int r, int c), int count(const T& value) const and int rows() const / int cols() const. Store the cells in one std::vector<T> of size rows * cols, with cell (r, c) at index r * cols + c.