Templates & Generic Programming: Functions, Classes, STL

TAKEAWAYS:

• Generic code lets you write one function/class that works for int, float, or custom types without rewriting.
• Function templates use <T> to create functions that adapt to any data type (e.g., swap<T>(a, b)).
• Class templates define reusable containers like vector<T> or map<K,V> that store any type.
• STL algorithms (e.g., sort, find) work generically on any container (array, list, vector).
• Type deduction lets the compiler infer template parameters from arguments (e.g., auto x = 5; → int).
• Specializations override default template behavior for specific types (e.g., vector<bool> uses bits).

1. Why Generic Programming?

Problem with Procedure-Oriented Code

In C-style functions, you must write separate versions for each data type:

void swapInt(int &a, int &b) { int t = a; a = b; b = t; }
void swapFloat(float &a, float &b) { float t = a; a = b; b = t; }

Disadvantages:

• Code duplication: Same logic repeated for every type.
• Maintenance: Fixing a bug requires editing all versions.
• Limited flexibility: Cannot handle custom types (e.g., swap for Student objects).

Solution: Templates

Templates let you write one function/class that works for any type. The compiler generates specialized versions as needed.

2. Function Templates

Syntax

template <typename T>  // or 'class T' (same meaning)
return_type function_name(parameters) {
    // body using T
}

Example: Generic swap function

template <typename T>
void swap(T &a, T &b) {
    T temp = a;
    a = b;
    b = temp;
}

How it works:

1. The compiler replaces T with the actual type (e.g., int, float) when called.
2. No runtime overhead—just like a regular function.

Example: Generic max Function

template <typename T>
T max(T a, T b) {
    return (a > b) ? a : b;
}

Trace:

Real-World Use: STL Algorithms

The Standard Template Library (STL) uses templates for algorithms like:

• sort(): Works on vector<int>, list<string>, etc.
• find(): Searches in any container.
• accumulate(): Sums elements of any iterable type.

Example: Sorting a vector of Student objects (custom type).

#include <algorithm>
#include <vector>
using namespace std;

struct Student {
    string name;
    int roll;
    bool operator<(const Student &s) const {
        return roll < s.roll;
    }
};

int main() {
    vector<Student> students = {{"Alice", 101}, {"Bob", 102}};
    sort(students.begin(), students.end());  // Uses template <typename Iter>
    return 0;
}

3. Class Templates

Syntax

template <typename T>
class ClassName {
    // members using T
};

Example: Generic Stack class

template <typename T>
class Stack {
private:
    vector<T> data;
public:
    void push(T item) { data.push_back(item); }
    T pop() { T top = data.back(); data.pop_back(); return top; }
};

Usage:

Stack<int> intStack;    // Stack of integers
Stack<string> strStack; // Stack of strings

State After Operations

Stack Operations Visualized

4. Template Specialization

When to Use

Override default template behavior for specific types (e.g., optimize vector<bool> to use bits).

Example: Specializing max for string

template <>  // Specialization for string
string max<string>(string a, string b) {
    return (a.length() > b.length()) ? a : b;
}

Trace:

5. Non-Type Template Parameters

Templates can also use non-type parameters (e.g., size_t for array sizes):

template <size_t N>
class FixedArray {
    int data[N];
public:
    void set(int index, int value) { data[index] = value; }
};

Use Case: Fixed-size arrays with compile-time bounds (e.g., FixedArray<100>).

6. Standard Template Library (STL) Containers

STL provides generic containers using templates:

Example: vector Internals

flowchart TD
    A["vector<int> v(5);"] --> B["Allocated: [_, _, _, _, _] (capacity=5, size=0)"]
    B --> C["v.push_back(10)"]
    C --> D["State: [10, _, _, _, _] (size=1)"]
    D --> E["v.push_back(20)"]
    E --> F["State: [10, 20, _, _, _] (size=2)"]
    F --> G["v.resize(10)"]
    G --> H["State: [10, 20, _, _, _, _, _, _, _, _] (size=10, capacity=10)"]

7. Type Deduction with auto and decltype

auto

Lets the compiler deduce the type:

auto x = 5;          // int
auto y = 3.14;       // double
auto z = vector<int>(); // vector<int>

decltype

Returns the type of an expression (used in templates):

template <typename T>
auto add(T a, T b) -> decltype(a + b) {
    return a + b;
}

8. Advantages of Templates

9. Disadvantages/Limitations

In the Real World

1. eSewa (Nepal)

   • Use: map<string, User> stores user accounts (key: email, value: User object).
   • Why: Generic map handles any key-value pair without rewriting.

2. Khalti’s Transaction System

   • Use: vector<Transaction> stores all transactions (custom Transaction struct).
   • Why: STL’s sort() and find() work on any iterable, including vector<Transaction>.

3. Pathao’s Ride Queue

   • Use: queue<RideRequest> manages pending ride requests (FIFO).
   • Why: Generic queue<T> ensures type safety for any request type.

4. Ncell’s Customer Database

   • Use: set<Customer> ensures unique customer IDs (sorted).
   • Why: STL’s set automatically handles uniqueness and ordering.

5. Daraz’s Order Processing

   • Use: map<OrderID, Order> tracks orders by ID.
   • Why: Generic map adapts to any OrderID type (e.g., string or int).

Worked Example: Bank Loan Calculator

Problem: A bank wants a generic function to calculate loan interest for any numeric type (float, double, or custom Currency). Solution: Use a template function with operator+ overloaded.

#include <iostream>
using namespace std;

template <typename T>
T calculateInterest(T principal, float rate, int years) {
    return principal + (principal * rate * years / 100);
}

struct NepaliRupee {
    float amount;
    NepaliRupee operator+(NepaliRupee other) {
        return {amount + other.amount};
    }
};

int main() {
    // Works for float
    float loan1 = calculateInterest(100000.0f, 8.5f, 5);
    cout << "Float loan: " << loan1 << endl;

    // Works for custom type (if + is overloaded)
    NepaliRupee loan2 = calculateInterest(NepaliRupee{100000}, 8.5f, 5);
    cout << "Nepali Rupee loan: " << loan2.amount << endl;

    return 0;
}

Output:

Float loan: 142500
Nepali Rupee loan: 142500

Exam Tip

1. Understand Template Syntax:

   • Know when to use typename vs. class (they are equivalent).
   • Remember <> for template arguments (e.g., vector<int>).

2. STL is Key:

   • Memorize common containers (vector, list, map) and algorithms (sort, find).
   • Explain how sort() works generically on any iterable.

3. Trace Template Instantiation:

   • For questions like "What does max(3.5, 7.2) generate?", answer: double max(double, double) (compiler deduces T = double).

4. Specialization vs. Overloading:

   • Overloading: Same name, different parameters (compile-time).

     void print(int x);       // Overload 1
     void print(double x);    // Overload 2
     

   • Specialization: Same template, different type (compile-time).

     template <> void print<string>(string s); // Specialization
     

5. Common Pitfalls:

   • Missing #include <vector>: Causes "vector not found" errors.
   • Forgetting typename: Use vector<T>::iterator (not vector<T>::iterator without typename).
   • Non-copyable types: Templates assume types are copyable (e.g., unique_ptr needs special handling).

6. Practical Questions:

   • Expect programs like:
     • Generic add() for two numbers.
     • Stack<T> with push()/pop().
     • Using sort() on a vector of custom objects.
   • Always trace the template instantiation (e.g., what type T becomes).

Past Exam Question Analysis

Question: "Why is generic programming beneficial? Explain template functions with a simple program." Model Answer: Generic programming reduces code duplication and improves maintainability. Template functions allow writing a single function that works for multiple types, as shown below:

template <typename T>
T multiply(T a, T b) {
    return a * b;
}

int main() {
    cout << multiply(3, 4) << endl;          // int
    cout << multiply(3.5, 2.0) << endl;      // double
    return 0;
}

Trace:

Quick Revision Table

In the real world

• Pathao/Daraz: Uses std::sort (STL algorithm) to sort delivery orders by distance or time, ensuring efficient route planning for drivers. The generic sort works on vector<Order> where each Order is a custom struct with distance, time, and location fields.
• Nepali Banks (e.g., NMB, Global IME): Employs std::map (STL container) to store customer account details (key: account number, value: Account struct) for O(log n) lookup during transactions. Template specialization optimizes map<bool> for flag checks (e.g., is_active).
• eSewa/Khalti: Leverages std::queue (STL container) to manage pending transactions in FIFO order, ensuring fairness and preventing deadlocks during peak hours. The queue’s generic nature handles transactions of any type (Payment, Refund, etc.).