C++ Templates & STL

1. C++ Templates

What are Templates?

Templates are a powerful feature in C++ that allows writing generic code. They enable functions and classes to operate with generic types, allowing code reusability without sacrificing performance.

Types of Templates:

a) Function Templates

cpp

// Generic function to find maximum of two values
template <typename T>
T max(T a, T b) {
    return (a > b) ? a : b;
}

// Usage
int main() {
    cout << max(10, 20) << endl;        // int
    cout << max(3.14, 2.71) << endl;    // double
    cout << max('a', 'z') << endl;      // char
}

b) Class Templates

cpp

// Generic Stack class
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 out_of_range("Stack is empty");
        }
        T element = elements.back();
        elements.pop_back();
        return element;
    }
};

// Usage
Stack<int> intStack;
Stack<string> stringStack;

c) Template Specialization

cpp

// General template
template <typename T>
class Container {
    T element;
public:
    Container(T elem) : element(elem) {}
    T get() { return element; }
};

// Specialization for bool
template <>
class Container<bool> {
    bool element;
public:
    Container(bool elem) : element(elem) {}
    string get() { 
        return element ? "true" : "false"; 
    }
};

2. Standard Template Library (STL)

STL is a powerful set of C++ template classes that provides general-purpose classes and functions with templates that implement many popular and commonly used algorithms and data structures.

Core Components of STL:

a) Containers

Objects that store collections of other objects.

Sequence Containers:

cpp

#include <vector>
#include <list>
#include <deque>
#include <array>
#include <forward_list>

vector<int> vec = {1, 2, 3, 4, 5};
list<string> names = {"Alice", "Bob", "Charlie"};
deque<double> dq = {1.1, 2.2, 3.3};
array<int, 5> arr = {1, 2, 3, 4, 5};

Associative Containers (sorted):

cpp

#include <set>
#include <map>

set<int> s = {3, 1, 4, 1, 5};  // {1, 3, 4, 5}
map<string, int> age = {
    {"Alice", 25},
    {"Bob", 30}
};

Unordered Containers (hash-based):

cpp

#include <unordered_set>
#include <unordered_map>

unordered_set<int> us = {3, 1, 4, 1, 5};
unordered_map<string, int> um = {
    {"Alice", 25},
    {"Bob", 30}
};

Container Adapters:

cpp

#include <stack>
#include <queue>
#include <priority_queue>

stack<int> stk;
queue<int> q;
priority_queue<int> pq;  // max-heap by default

b) Iterators

Objects that enable traversal through containers.

cpp

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

// Different iterator types
vector<int>::iterator it = vec.begin();
vector<int>::const_iterator cit = vec.cbegin();
vector<int>::reverse_iterator rit = vec.rbegin();

// Range-based for loop (C++11)
for (const auto& element : vec) {
    cout << element << " ";
}

// Using iterators
for (auto it = vec.begin(); it != vec.end(); ++it) {
    cout << *it << " ";
}

c) Algorithms

Over 100 algorithms for searching, sorting, counting, and manipulating data.

cpp

#include <algorithm>
#include <vector>

vector<int> nums = {5, 2, 8, 1, 9, 3};

// Sorting
sort(nums.begin(), nums.end());

// Finding
auto it = find(nums.begin(), nums.end(), 8);

// Counting
int count_eights = count(nums.begin(), nums.end(), 8);

// Transforming
vector<int> squared;
transform(nums.begin(), nums.end(), back_inserter(squared),
          [](int x) { return x * x; });

// Lambda expressions with algorithms
sort(nums.begin(), nums.end(), 
     [](int a, int b) { return a > b; });  // descending

Common Algorithms:

• sort(), stable_sort()

• find(), find_if()

• binary_search(), lower_bound(), upper_bound()

• copy(), move()

• remove(), remove_if()

• replace(), replace_if()

• reverse(), rotate()

• unique()

• accumulate(), inner_product()

• min_element(), max_element()

d) Functors (Function Objects)

Classes that overload the operator().

cpp

// Functor example
class MultiplyBy {
    int factor;
public:
    MultiplyBy(int x) : factor(x) {}
    int operator()(int y) const {
        return factor * y;
    }
};

// Usage
vector<int> nums = {1, 2, 3, 4, 5};
transform(nums.begin(), nums.end(), nums.begin(), MultiplyBy(3));

e) Utilities

Important utility classes.

cpp

#include <utility>  // pair
#include <tuple>    // tuple
#include <functional> // function, bind

// Pair
pair<string, int> person("Alice", 25);

// Tuple
tuple<string, int, double> student("Bob", 20, 3.8);

// Function wrapper
function<int(int, int)> add = [](int a, int b) { return a + b; };

// Bind
auto add_five = bind(add, placeholders::_1, 5);
cout << add_five(10);  // 15

3. Modern C++ Features with STL

C++11 and Beyond Features:

Lambda Expressions

cpp

vector<int> nums = {1, 2, 3, 4, 5};

// Lambda syntax: [capture](parameters) -> return_type { body }
int threshold = 3;
auto count = count_if(nums.begin(), nums.end(),
                     [threshold](int x) { return x > threshold; });

// Generic lambda (C++14)
auto print = [](const auto& x) { cout << x << " "; };
for_each(nums.begin(), nums.end(), print);

Auto and Decltype

cpp

auto x = 42;  // int
auto y = 3.14;  // double

vector<int> vec = {1, 2, 3};
for (auto it = vec.begin(); it != vec.end(); ++it) {
    cout << *it << " ";
}

Range-based Operations (C++20)

cpp

#include <ranges>

vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

// Filter and transform using ranges
auto result = nums | views::filter([](int x) { return x % 2 == 0; })
                  | views::transform([](int x) { return x * x; });

for (int x : result) {
    cout << x << " ";  // 4 16 36 64 100
}

4. Best Practices and Examples

Example 1: Comprehensive STL Program

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <string>

using namespace std;

int main() {
    // Vector operations
    vector<int> numbers = {4, 2, 5, 3, 1, 4, 5};
    
    sort(numbers.begin(), numbers.end());
    numbers.erase(unique(numbers.begin(), numbers.end()), numbers.end());
    
    // Map operations
    map<string, vector<int>> studentGrades;
    studentGrades["Alice"] = {85, 90, 78};
    studentGrades["Bob"] = {92, 88, 95};
    
    // Set operations
    set<int> uniqueNumbers(numbers.begin(), numbers.end());
    
    // Algorithm with lambda
    auto isEven = [](int x) { return x % 2 == 0; };
    int evenCount = count_if(numbers.begin(), numbers.end(), isEven);
    
    return 0;
}

Example 2: Custom Template with STL

cpp

template <typename T>
class Statistics {
private:
    vector<T> data;
public:
    void add(const T& value) {
        data.push_back(value);
    }
    
    T mean() const {
        if (data.empty()) return T();
        T sum = accumulate(data.begin(), data.end(), T());
        return sum / data.size();
    }
    
    T median() {
        if (data.empty()) return T();
        vector<T> sorted = data;
        sort(sorted.begin(), sorted.end());
        size_t n = sorted.size();
        if (n % 2 == 0) {
            return (sorted[n/2 - 1] + sorted[n/2]) / 2;
        } else {
            return sorted[n/2];
        }
    }
    
    vector<T> mode() {
        map<T, int> frequency;
        for (const auto& val : data) {
            frequency[val]++;
        }
        
        int maxFreq = 0;
        for (const auto& [value, count] : frequency) {
            maxFreq = max(maxFreq, count);
        }
        
        vector<T> modes;
        for (const auto& [value, count] : frequency) {
            if (count == maxFreq) {
                modes.push_back(value);
            }
        }
        return modes;
    }
};

5. Key Advantages

1. Code Reusability: Write once, use with multiple data types

2. Type Safety: Compile-time type checking

3. Performance: Templates are instantiated at compile time

4. Abstraction: Hide implementation details

5. Standardization: STL provides battle-tested implementations

6. Interoperability: All STL components work together seamlessly

6. Common Pitfalls

1. Complex Error Messages: Template errors can be verbose

2. Code Bloat: Each template instantiation creates new code

3. Compilation Time: Templates increase compilation time

4. Binary Size: Multiple instantiations increase binary size

7. When to Use

Use Templates When:

• Writing container classes

• Implementing algorithms that work with multiple types

• Creating utility functions

• Building generic libraries

Use STL When:

• You need standard data structures

• Implementing common algorithms

• Avoiding reinventing the wheel

• Writing maintainable, standard-compliant code

Summary

C++ Templates and STL form the backbone of modern C++ programming. They provide a powerful combination of generic programming capabilities and pre-built, optimized data structures and algorithms. Mastering these concepts is essential for writing efficient, reusable, and maintainable C++ code in professional environments.