STL & Templates
Master C++ STL containers, algorithms, iterators, and template programming techniques essential for competitive programming. Learn to leverage the standard library for efficient and clean code solutions.
1. STL Containers Overview
STL provides various containers optimized for different use cases. Understanding their time complexities and appropriate usage is crucial for competitive programming.
Common STL Containers
#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <priority_queue>
using namespace std;
int main() {
// Sequential containers
vector<int> vec = {1, 2, 3, 4, 5};
deque<int> dq = {1, 2, 3, 4, 5};
list<int> lst = {1, 2, 3, 4, 5};
// Associative containers
set<int> s = {5, 2, 8, 1, 9};
map<string, int> m = {{"apple", 5}, {"banana", 3}};
// Unordered containers (hash-based)
unordered_set<int> us = {1, 2, 3, 4, 5};
unordered_map<string, int> um = {{"key1", 10}, {"key2", 20}};
// Container adapters
stack<int> st;
queue<int> q;
priority_queue<int> pq; // max heap by default
// Demonstrate basic operations
cout << "Vector size: " << vec.size() << endl;
cout << "Set contains 5: " << (s.count(5) > 0) << endl;
cout << "Map value for 'apple': " << m["apple"] << endl;
return 0;
}2. STL Algorithms
STL algorithms provide efficient implementations of common operations. They work with iterators and can be applied to various container types.
Essential STL Algorithms
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;
int main() {
vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
// Sorting
sort(vec.begin(), vec.end());
cout << "Sorted: ";
for (int x : vec) cout << x << " ";
cout << endl;
// Binary search (requires sorted container)
bool found = binary_search(vec.begin(), vec.end(), 5);
cout << "Found 5: " << found << endl;
// Lower and upper bounds
auto lb = lower_bound(vec.begin(), vec.end(), 5);
auto ub = upper_bound(vec.begin(), vec.end(), 5);
cout << "Count of 5: " << (ub - lb) << endl;
// Find operations
auto it = find(vec.begin(), vec.end(), 4);
if (it != vec.end()) {
cout << "Found 4 at position: " << (it - vec.begin()) << endl;
}
// Unique (remove consecutive duplicates)
vec.erase(unique(vec.begin(), vec.end()), vec.end());
// Accumulate (sum)
int sum = accumulate(vec.begin(), vec.end(), 0);
cout << "Sum: " << sum << endl;
// Transform
vector<int> squares(vec.size());
transform(vec.begin(), vec.end(), squares.begin(),
[](int x) { return x * x; });
// Max and min elements
auto max_it = max_element(vec.begin(), vec.end());
auto min_it = min_element(vec.begin(), vec.end());
cout << "Max: " << *max_it << ", Min: " << *min_it << endl;
return 0;
}
3. Iterators and Iterator Categories
Iterators provide a uniform interface to access container elements. Understanding iterator categories helps choose the right algorithms and containers.
Iterator Usage Examples
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <algorithm>
using namespace std;
int main() {
// Random access iterators (vector, deque)
vector<int> vec = {1, 2, 3, 4, 5};
// Forward iteration
for (auto it = vec.begin(); it != vec.end(); ++it) {
cout << *it << " ";
}
cout << endl;
// Reverse iteration
for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
cout << *it << " ";
}
cout << endl;
// Random access operations
auto it = vec.begin();
it += 2; // Jump to 3rd element
cout << "Element at position 2: " << *it << endl;
// Bidirectional iterators (list, set, map)
list<int> lst = {10, 20, 30, 40, 50};
auto lst_it = lst.begin();
advance(lst_it, 2); // Move forward 2 positions
cout << "List element at position 2: " << *lst_it << endl;
// Set iterators (always const for keys)
set<int> s = {5, 2, 8, 1, 9};
for (auto it = s.begin(); it != s.end(); ++it) {
cout << *it << " "; // Always in sorted order
}
cout << endl;
// Iterator arithmetic
cout << "Vector size using iterators: " << (vec.end() - vec.begin()) << endl;
// Range-based for loop (C++11)
cout << "Range-based loop: ";
for (const auto& element : vec) {
cout << element << " ";
}
cout << endl;
return 0;
}
4. Template Programming Basics
Templates enable generic programming, allowing you to write code that works with different data types. This is essential for creating reusable competitive programming solutions.
Function and Class Templates
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function template
template<typename T>
T maximum(T a, T b) {
return (a > b) ? a : b;
}
// Function template with multiple parameters
template<typename T, typename U>
auto add(T a, U b) -> decltype(a + b) {
return a + b;
}
// Class template
template<typename T>
class Stack {
private:
vector<T> elements;
public:
void push(const T& element) {
elements.push_back(element);
}
T pop() {
if (elements.empty()) {
throw runtime_error("Stack is empty");
}
T top = elements.back();
elements.pop_back();
return top;
}
bool empty() const {
return elements.empty();
}
size_t size() const {
return elements.size();
}
};
// Template specialization
template<>
class Stack<bool> {
private:
vector<bool> elements;
public:
void push(bool element) {
elements.push_back(element);
}
bool pop() {
if (elements.empty()) {
throw runtime_error("Stack is empty");
}
bool top = elements.back();
elements.pop_back();
return top;
}
bool empty() const {
return elements.empty();
}
};
int main() {
// Function template usage
cout << "Max of 10 and 20: " << maximum(10, 20) << endl;
cout << "Max of 3.14 and 2.71: " << maximum(3.14, 2.71) << endl;
cout << "Max of 'a' and 'z': " << maximum('a', 'z') << endl;
// Mixed type addition
cout << "Add 5 and 3.14: " << add(5, 3.14) << endl;
// Class template usage
Stack<int> intStack;
intStack.push(10);
intStack.push(20);
intStack.push(30);
cout << "Stack size: " << intStack.size() << endl;
cout << "Popped: " << intStack.pop() << endl;
cout << "Popped: " << intStack.pop() << endl;
// Template with STL
Stack<string> stringStack;
stringStack.push("Hello");
stringStack.push("World");
cout << "String stack size: " << stringStack.size() << endl;
return 0;
}
5. Advanced Template Techniques
Advanced template features like variadic templates, SFINAE, and template metaprogramming can create powerful, flexible solutions for competitive programming.
Advanced Template Features
#include <iostream>
#include <vector>
#include <type_traits>
#include <utility>
using namespace std;
// Variadic template function
template<typename... Args>
void print(Args... args) {
((cout << args << " "), ...); // C++17 fold expression
cout << endl;
}
// Template metaprogramming - compile-time factorial
template<int N>
struct Factorial {
static constexpr int value = N * Factorial<N-1>::value;
};
template<>
struct Factorial<0> {
static constexpr int value = 1;
};
// SFINAE (Substitution Failure Is Not An Error)
template<typename T>
typename enable_if<is_integral<T>::value, T>::type
safe_divide(T a, T b) {
return (b != 0) ? a / b : 0;
}
template<typename T>
typename enable_if<is_floating_point<T>::value, T>::type
safe_divide(T a, T b) {
return (b != 0.0) ? a / b : 0.0;
}
// Perfect forwarding
template<typename T>
void wrapper(T&& arg) {
process(forward<T>(arg));
}
void process(int& x) {
cout << "Processing lvalue: " << x << endl;
}
void process(int&& x) {
cout << "Processing rvalue: " << x << endl;
}
// Template alias (C++11)
template<typename T>
using Vec = vector<T>;
template<typename K, typename V>
using Map = unordered_map<K, V>;
int main() {
// Variadic template
print(1, 2.5, "hello", 'c');
// Template metaprogramming
cout << "Factorial of 5: " << Factorial<5>::value << endl;
// SFINAE
cout << "Safe divide (int): " << safe_divide(10, 3) << endl;
cout << "Safe divide (double): " << safe_divide(10.0, 3.0) << endl;
// Perfect forwarding
int x = 42;
wrapper(x); // lvalue
wrapper(100); // rvalue
// Template aliases
Vec<int> numbers = {1, 2, 3, 4, 5};
Map<string, int> counts = {{"apple", 5}, {"banana", 3}};
cout << "Numbers size: " << numbers.size() << endl;
cout << "Counts size: " << counts.size() << endl;
return 0;
}
6. Competitive Programming Applications
Practical applications of STL and templates in competitive programming scenarios, including common patterns and optimizations.
Competitive Programming Template
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cmath>
using namespace std;
// Fast I/O template
class FastIO {
public:
FastIO() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
};
// Generic pair output
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
return os << "(" << p.first << ", " << p.second << ")";
}
// Generic vector output
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
os << "[";
for (size_t i = 0; i < v.size(); ++i) {
if (i > 0) os << ", ";
os << v[i];
}
return os << "]";
}
// Generic input for vectors
template<typename T>
istream& operator>>(istream& is, vector<T>& v) {
for (auto& element : v) {
is >> element;
}
return is;
}
// Utility functions
template<typename T>
T gcd(T a, T b) {
return b ? gcd(b, a % b) : a;
}
template<typename T>
T lcm(T a, T b) {
return a / gcd(a, b) * b;
}
// Binary search template
template<typename T, typename Predicate>
T binary_search_answer(T left, T right, Predicate pred) {
while (left < right) {
T mid = left + (right - left) / 2;
if (pred(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
int main() {
FastIO fast_io;
// Example: Finding unique elements and their frequencies
int n;
cin >> n;
vector<int> arr(n);
cin >> arr;
// Count frequencies using map
map<int, int> freq;
for (int x : arr) {
freq[x]++;
}
cout << "Frequencies:" << endl;
for (const auto& p : freq) {
cout << p.first << ": " << p.second << endl;
}
// Find unique elements
sort(arr.begin(), arr.end());
arr.erase(unique(arr.begin(), arr.end()), arr.end());
cout << "Unique elements: " << arr << endl;
// Example: Priority queue for top K elements
priority_queue<int, vector<int>, greater<int>> min_heap;
int k = 3;
for (int x : arr) {
min_heap.push(x);
if (min_heap.size() > k) {
min_heap.pop();
}
}
cout << "Top " << k << " elements: ";
while (!min_heap.empty()) {
cout << min_heap.top() << " ";
min_heap.pop();
}
cout << endl;
return 0;
}
Summary
- STL Containers: Choose the right container based on required operations and time complexity
- STL Algorithms: Leverage built-in algorithms for sorting, searching, and manipulation
- Iterators: Understand iterator categories and use them effectively with algorithms
- Templates: Write generic, reusable code using function and class templates
- Advanced Features: Use variadic templates, SFINAE, and metaprogramming for complex solutions
- Competitive Programming: Apply STL and templates to solve problems efficiently