Template programming allows us to create parameterized classes (templates) that are specialized to actual code when we need to use them. The advantage is that we can use the template code to generate many concrete classes without having to duplicate code.
Note: templates are a large and complex topic.
Example: if we want to implement a class List for int data and another for float data, we could copy and paste the code and just change the type of the private fields within the Nodes
The class List:
class List {
struct Node;
Node *theList;
...
};
struct List::Node {
int data;
Node *next;
};class IntList {
struct Node {
int data;
Node *next;
...
};
Node *theList;
public:
...
};
class FloatList {
struct Node {
float data;
Node *next;
...
};
Node *theList;
public:
...
};Copying and Pasting is never a good idea. What if we want to store something other than int? Do we need to rewrite a whole new class?
To avoid this code duplication, we can create a List template with a parameter that corresponds to the type of data stored in the list.
A template class is a class that's parameterized by a type.
template<typename T> class List {
struct Node {
T data;
Node *next;
... // big 5
}; // List<T>::Node
Node *theList;
public:
class Iterator {
Node *p;
explicit Iterator(Node *p) : p{p} {}
public:
T &operator*() { return p->data; }
Iterator &operator++(){...}
...
friend class List<T>;
}; // List<T>::Iterator
void addToFront(const T &n) {...}
};Now, out List class can store any type of data. To create a new List object, we need to specify the value of the parameter T, i.e., the type of data we want to store.
When the program is executed, each instance of T in the code of the List will be replaced with the actual type.
List<int< li; // int is the value of the template parameter T,
// so each T in the List's code will be replaced with int
li.addToFront(1);
List<string> ls; // string is the value of the template parameter T,
// so each T in the List's code will be replaced with string
ls.addToFront("hello");Client code:
List<int> l1;
List<List<int>> l2;
l1.addToFront(3);
l2.addToFront(l1);
for (List<int)::Iterator it = l1.begin(); it != l1.end(); ++it) {
std::cout << *it << std::endl;
}
// or
for (auto n : l1) {
std::cout << n << std::endl;
}Template for stack:
template<typename T> class Stack {
int size;
int cap;
T *contents;
public:
stack() {...}
void push(T x) {...}
T top() const { return contents[size-1]; }
void pop() {...}
};How do templates work? Compiler specializes the templates into actual code as a source-level transformation (at the source code level before compilation) and then compiles the resulting code as usual.
Node that because of the way that templates work, the implementation of the template needs to go in the .h file instead of the .cc file as usual.
What types can T be? Use duck-typing to determine.
Duck-typing: if it looks like a duck, walks like a duck, and quacks like a duck, then it is a duck.
So the valid types of T are any types that support the ways in which you use T.
Consider:
template<typename T> class Foo {
T x;
public:
Foo operator+(const Foo &other) { return Foo{x + other.x}}
}Additionally, note that in the declaration of the template parameters, typename is the required keyword, but T is only a common name for type by convention. You can use something other than T if you prefer. When the template has more than one parameter, it is common to use an upper-case character related to the meaning of the type.
For example, you could use K as the name of the type for a key, V for a value, I for an index, etc. These are just conventions.
template<typename K, V> class Dictionary {
K key;
V value;
...
}
Dictionary<string, Student> d; // Each K in Dictionary will be replaced with string and each V will be replaced with StudentThe Standard Template Library (STL) is a large collection of useful templates that already exist in C++.
It contains collection classes such as lists, vectors, maps, deques, etc, iterators to traverse the elements in those collections and generic functions to operate on them, such as initialization, sorting, searching, and transformation of the elements.
The template classes in the STL are explicitly structures not to allow inheritance. You can't derive from them to extend their behaviour because their methods are not virtual (but you could extend their behaviour using Decorators).
The class std::vector is a generic (template) implementation of dynamic-length arrays.
Example: use vector to create a dynamic-length array of integers
#include<vector>
using namespace std;
...
vector<int> v; // because it is a template, we need to specify the type of data to store, which is int in this example
v.emplace_back(6); // {6}
v.emplace_back(7); // {6, 7}
vector<int> u{4, 5}; // {4, 5}The methods emplace_back() or push_back() can be used to add elements to the vector. The difference is emplace_back() creates a new object by using the class constructor before adding it to the array, whereas push_back() copies or moves the content from an existing object into the array.
Note: you don't pass the actual object to emplace_back, you pass the arguments to be used to construct the object, and emplace_back calls the constructor for you. This is extremely useful when you want to create an actual object "in place" in the container rather than first creating the object and then moving (or copying) it into the container.
Example: create a vector of Vec objects using emplace_back:
#include <iostream>
#include <vector>
struct Vec {
int x, y;
Vec(int x, int y) : x{x}, y{y} {}
};
int main() {
std::vector<Vec> v;
for (int i = 0; i < 5; i++) {
v.emplace_back(i, i+1); // invokes Vec ctor
}
for (const auto & i : v) {
std::cout << "(" << i.x << ", " << i,y << ")" << std::endl;
}
}You can use a for loop to visit a vector's contents by indexing:
for (std::size_t i = 0; i < v.size(); ++i) {
cout << v[i] << endl;
}
for (int i = 0; i < v.size(); ++i) {
cout << v[i] << endl;
}Vectors also support the iterator abstraction:
// iterator here is in lower case
for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
cout << *it << endl;
}
// or use auto
for (auto n : v) {
cout << n << endl;
}To iterate in reverse:
for (vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it) {
cout << *it << endl;
}
for (auto it = v.rbegin(); it != v.rend(); ++it) {
cout << *it << endl;
}To remove the last element:
v.pop_back(); // removes last element of vector
*(--v.end()); // last element
*(v.end() - 2); // second last elementOther vector operations are based on iterators.
The erase method which removes element from a vector, work with iterators:
auto it = v.erase(v.begin()); // erase item 0, returns iterator to first item after the erase
it = v.erase(v.begin() + 3); // erase item 3 (4th item)
it = v.erase(it); // erases item pointed to by it
it = v.erase(v.end() - 1); // erase last item
Use Vectors instead of dynamic-length arrays
Vectors are guaranteed to be implemented internally as arrays. Use them whenever you need a dynamic-length array (i.e. avoid using the array versions of new and delete, as using these operators usually indicates an opportunity to use a vector instead).
If you want a non-dynamic (static) length array, std::array exists, but you could just use a vector and not change its size.
Consider:
vector<int> v{0, 1, 2};
auto it = v.begin();
for (int i = 0; i < 1000; ++i) {
v.emplace_back(i);
}
cout << *it << endl; // undefined behaviour, iterator invalidation!Accessing elements:
v[i]; // returns ith element of v (completely unchecked), just like an array index
// v[i] -- if you go out of bounds, the behaviour is undefined
v.at(i); // same as v[i] but checked. It makes sure you don't go out of bound, but what does it do if it is out of bound?
v.at(i) throws an out_of_range exception
Because of the additional checking, v[i] is more efficient than v.at(i). Thus, it may be a good idea to use v.at(i) at the initial stages of development and replace it with v[i] for production code after testing the program thoroughly.
Problem: What should happen when using v.at(i) when i is out of bound?
C Solution:
- some functions that might fail return a status code
- or set the global variable error
- leads to awkward programming
- encourages programmers to ignore error checks
C++ Solution:
- when an error conditions arises, the function raises an exception
- What happens? by default, execution stops
The class std::map can be used to implement dictionaries, in which unique keys are mapped to values. It is a generic (template) class, so we can define any type for the keys and values. (Well, the key must be of a type that supports operator<, which compare and sort the keys)
Example: map of string keys to int values (note that map is in the <map> library and the std namespace)
#include <map>
using namespace std;
...
map<string, int> m; // string is the key type, and int is the value type
// Setting the values for the keys "abc" and "def"
m["abc"] = 1;
m["def"] = 4;
// Reading the values associated with each key
cout << m["abc"] << endl; // 1
cout << m["ghi"] << endl; // 0
// key "ghi" didn't exist in our map, but the index operator creates keys if they don't exist... but we never set the value, so what is it?
// the value gets default initialized, integer get 0Here, "ghi" is not a key defined in m, so it is not found. It a key is not found when trying to read it, it is inserted and the value if default-constructed (for an int, the default value is zero).
The erase method can be used to delete a key and its associated value:
m.erase("abc");The count method returns one if a key is found in the map, or zero otherwise:
if (m.count("def")) ... // 0 = not found, 1 = foundIterating over a map:
Iterating over a map happens in sorted key order:
for (auto &p : m) {
cout << p.first << ' ' << p.second << endl;
// Note: first and second are fields, not methods
}p's type here is std::pair<string, int>& (pairs are defined in <utility>).