C++ templates are a compile-time code generation mechanism — the compiler generates a separate concrete implementation for each type a template is instantiated with (reification). The Standard Template Library (STL) provides generic containers (vector, map, set), iterators, and algorithms that work with any type satisfying the required interface, with no virtual dispatch overhead.
In C, writing a sort function that works for both int and double requires either a void* (type-unsafe) or two copies of the code. C++ templates let you write the sort once, parameterised over the type. The compiler generates a type-safe sort<int> and sort<double> at compile time — no runtime type checking, no boxing, no overhead.
Function templates
#include <iostream>
#include <string>
// Function template: T is the type parameter
template<typename T>
T maximum(T a, T b) {
return (a > b) ? a : b;
}
// Class template
template<typename T>
class Stack {
std::vector<T> data;
public:
void push(const T& val) { data.push_back(val); }
void pop() { if (!data.empty()) data.pop_back(); }
T& top() { return data.back(); }
bool empty() const { return data.empty(); }
size_t size() const { return data.size(); }
};
int main() {
// Compiler deduces T = int from arguments
std::cout << maximum(3, 7) << "\n"; // 7
std::cout << maximum(3.14, 2.71) << "\n"; // 3.14
std::cout << maximum(std::string("apple"), std::string("banana")) << "\n"; // banana
// Stack<int> is a complete concrete class generated at compile time
Stack<int> s;
s.push(10);
s.push(20);
std::cout << s.top() << "\n"; // 20
}STL containers
The STL provides three categories of containers: sequence containers (vector, list, deque, array), associative containers (map, set, multimap — tree-based, sorted), and unordered containers (unordered_map, unordered_set — hash-based). Choose based on access pattern: random access → vector; key lookup → unordered_map; sorted iteration → map.
#include <vector>
#include <map>
#include <unordered_map>
#include <string>
#include <iostream>
int main() {
// vector: dynamic array — O(1) random access, O(1) amortised push_back
std::vector<int> v = {3, 1, 4, 1, 5, 9};
v.push_back(2);
v.reserve(20); // pre-allocate to avoid reallocation
for (int x : v) std::cout << x << " ";
std::cout << "\n";
// map: balanced BST — O(log n) all operations, sorted by key
std::map<std::string, int> scores;
scores["Alice"] = 95;
scores["Bob"] = 87;
scores["Charlie"] = 92;
for (const auto& [name, score] : scores) { // structured bindings (C++17)
std::cout << name << ": " << score << "\n"; // printed in alphabetical order
}
// unordered_map: hash table — O(1) average lookup
std::unordered_map<std::string, int> freq;
std::string words[] = {"go", "go", "rust", "cpp", "go"};
for (const auto& w : words) freq[w]++;
std::cout << "go: " << freq["go"] << "\n"; // 3
}STL algorithms
The <algorithm> header provides over 100 generic algorithms that work on any container via iterators: sort, find, count_if, transform, accumulate, remove_if. C++20 ranges provide a cleaner, composable interface to the same algorithms.
#include <algorithm>
#include <numeric>
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {5, 2, 8, 1, 9, 3};
std::sort(v.begin(), v.end()); // {1, 2, 3, 5, 8, 9}
// find_if: returns iterator to first match
auto it = std::find_if(v.begin(), v.end(), [](int x){ return x > 4; });
if (it != v.end()) std::cout << "First > 4: " << *it << "\n"; // 5
// accumulate: sum (or any fold)
int sum = std::accumulate(v.begin(), v.end(), 0);
std::cout << "Sum: " << sum << "\n"; // 28
// transform: apply function to each element, store result
std::vector<int> doubled(v.size());
std::transform(v.begin(), v.end(), doubled.begin(), [](int x){ return x * 2; });
// C++20 ranges — more readable, composable, lazy
// std::ranges::sort(v);
// auto evens = v | std::views::filter([](int x){ return x % 2 == 0; });
}Template specialisation and SFINAE
Explicit specialisation provides a custom implementation for a specific type. Partial specialisation (class templates only) specialises for a category of types (e.g. all pointer types). SFINAE (Substitution Failure Is Not An Error) is a rule: if substituting template arguments into a function template fails, the template is silently removed from the overload set rather than causing a compile error. This enables compile-time conditional template selection via std::enable_if. C++20 concepts replaced most SFINAE with readable constraint syntax.
#include <concepts>
#include <iostream>
// C++20 concepts: constrain template parameters with readable names
// Numeric concept: T must support arithmetic operators
template<typename T>
concept Numeric = std::integral<T> || std::floating_point<T>;
// Constrained template: only accepts Numeric types
template<Numeric T>
T square(T x) { return x * x; }
// requires clause: inline constraint
template<typename T>
requires std::totally_ordered<T>
T clamp(T value, T lo, T hi) {
return (value < lo) ? lo : (value > hi) ? hi : value;
}
int main() {
std::cout << square(5) << "\n"; // 25
std::cout << square(3.14) << "\n"; // 9.8596
// square("hello"); // COMPILE ERROR: constraint not satisfied
// Error message: "the associated constraints are not satisfied"
// (much clearer than SFINAE errors)
std::cout << clamp(15, 0, 10) << "\n"; // 10
}Iterator categories and complexity guarantees
STL iterators have five categories with defined capability sets: InputIterator (single-pass read), ForwardIterator (multi-pass read), BidirectionalIterator (++ and --), RandomAccessIterator (+ n, - n, []). Algorithms declare which iterator category they require — std::sort requires RandomAccess, std::find requires only Input. Each STL container documents its iterator category: vector provides RandomAccess; list provides Bidirectional; forward_list provides Forward. C++20 adds contiguous iterators for containers with elements in contiguous memory (vector, array, string).
std::vector<int> and std::vector<double>, the compiler generates two separate classes. In Java, ArrayList<Integer> and ArrayList<Double> are the same class at runtime — type information is erased. C++ templates are faster (no boxing, no type checks) but generate more code (template bloat). Java generics cannot hold primitives directly; C++ templates can hold any type including primitives.std::map is a balanced BST — O(log n) for all operations, sorted order, stable iteration. std::unordered_map is a hash table — O(1) average for lookup/insert/erase, but O(n) worst case (hash collisions), no ordering, iteration order undefined. For most key-lookup uses, unordered_map is faster; use map when you need sorted keys or stable ordering.Template instantiation and the two-phase lookup
C++ templates are compiled in two phases. In phase one, the template definition is parsed and names that do not depend on template parameters are resolved. In phase two, when the template is instantiated with concrete types, dependent names are resolved in the context of both the template definition and the instantiation point. This two-phase lookup is why you must write typename before dependent type names (typename T::value_type) and template before dependent template member accesses. It is also why the One Definition Rule (ODR) requires template definitions to be in headers — the compiler needs the definition at each instantiation point, unlike regular functions which can be in separate translation units.
std::ranges and the range pipeline model (C++20)
The C++20 std::ranges library rethinks STL algorithms with three improvements. First, algorithms accept range objects instead of iterator pairs — std::ranges::sort(v) instead of std::sort(v.begin(), v.end()). Second, views (std::views::filter, std::views::transform) are lazy — they don't compute until iterated, and compose with the pipe operator: v | views::filter(isEven) | views::transform(double). Third, concepts constrain algorithms: passing a list (bidirectional) to ranges::sort (requires random-access) gives a clear compile error. The ranges library is the modern replacement for <algorithm> paired with begin/end.
ISO/IEC 14882:2020 (C++20). iso.org/standard/79358.html. Sections 13 (templates), 20–22 (STL). Josuttis, N. M. (2012). The C++ Standard Library (2nd ed.). Addison-Wesley. Meyers, S. (2001). Effective STL. Addison-Wesley. cppreference.com — Templates, Containers, Algorithms.