Generic Programming Concepts

How can we create a universal swap function that works with different data types?

void Exchange(int& first, int& second)
{
    int temporary = first;
    first = second;
    second = temporary;
}

void Exchange(double& first, double& second)
{
    double temporary = first;
    first = second;
    second = temporary;
}

void Exchange(char& first, char& second)
{
    char temporary = first;
    first = second;
    second = temporary;
}

While function overloading provides a solution, it presents several limtiations:

• Overloaded functions differ only in type, resulting in low code reuse efficiency. Each new type requires creating a corresponding function.
• Maintainability issues arise since an error in one function might affect all overloaded versions.

The solution lies in providing the compiler with a blueprint to generate type-specific code automatically. C++ templates serve this purpose by allowing code generation based on type parameters.

Generic programming involves writing type-independent code as a method for code reuse, with templates forming the foundation of this approach.

Template Categories

C++ templates are primarily divided into function templates and class templates.

Function Templates

Function Template Definition

Function templates represent families of functions that operate independently of types. They become parameterized during usage, generating specific type versions based on argument types.

Template Syntax

template<typename Type1, typename Type2, ..., typename TypeN>

return_type function_name(parameter_list){}

#include <iostream>

template<typename ElementType>
void Exchange(ElementType& x, ElementType& y)
{
    ElementType temp = x;
    x = y;
    y = temp;
}

int main()
{
    int num1 = 15;
    int num2 = 25;
    std::cout << "Before exchange: " << num1 << " " << num2 << std::endl;
    Exchange(num1, num2);
    std::cout << "After exchange: " << num1 << " " << num2 << std::endl;
    return 0;
}

Note: The typename keyword defines template parameters and can be replaced with class (struct cannot substitute for class).

Template Mechanism

Function templates serve as blueprints rather than actual functions. The compiler generates specific type functions based on usage patterns, automating repetitive coding tasks.

During compilation, the compiler deduces template parameters from argument types and creates corresponding specialized functions. For example, when using double types with a template, the compiler identifies T as double and generates double-specific code.

Template Instantiation

Using template functions with different parameter types constitutes template instantiation, which occurs through implicit or explicit instantiation.

Implicit Instantiation

template<typename DataType>
void Exchange(const DataType& elem1, const DataType& elem2)
{
    DataType temp = elem1;
    elem1 = elem2;
    elem2 = temp;
}

int main()
{
    int value1 = 15;
    double value2 = 3.14;
    
    Exchange(value1, (int)value2);  // Type casting for compatibility
    Exchange((double)value1, value2);
    return 0;
}

The compiler deduces types from template function arguments. Mismatched parameter types require explicit conversion.

Explicit Instantiation

template<typename GenericType>
void Exchange(const GenericType& item1, const GenericType& item2)
{
    GenericType temporary = item1;
    item1 = item2;
    item2 = temporary;
}

int main()
{
    int integer_val = 15;
    double double_val = 3.14;
    
    Exchange<int>(integer_val, double_val);
    Exchange<double>(integer_val, double_val);
    return 0;
}

When types don't match, the compiler attempts implicit conversion, reporting errors if conversion fails.

Template Parameter Matching Rules

A non-template function can coexist with a同名 function template, and the template can instantiate the non-template function.

// Specialized integer addition
int Sum(int x, int y)
{
    return x + y;
}

// Generic addition template
template<class TemplateType>
TemplateType Sum(TemplateType x, TemplateType y)
{
    return x + y;
}

void Demo()
{
    Sum(5, 10);           // Matches non-template function
    Sum<int>(5, 10);      // Calls template instantiation
}

When both non-template and template functions are available with identical conditions, the non-template function takes precedence. The template generates better matches when appropriate.

// Specialized integer addition
int Sum(int x, int y)
{
    return x + y;
}

// Generic addition with different types
template<class Type1, class Type2>
Type1 Sum(Type1 x, Type2 y)
{
    return x + y;
}

void Demo()
{
    Sum(5, 10);           // Exact match with non-template
    Sum(5, 10.5);         // Template generates better match
}

Template functions prohibit automatic type conversion, while regular functions permit it.

Class Templates

Class Template Definition

template<class T1, class T2, ..., class Tn>
class ClassTemplateName
{
    // Class member definitions
};

// Dynamic array template
template<class ContentType>
class DynamicArray
{
public:
    DynamicArray(size_t initial_capacity = 10)
        : data(new ContentType[initial_capacity])
        , current_size(0)
        , total_capacity(initial_capacity)
    {}
    
    ~DynamicArray();
    
    void Append(const ContentType& element);
    void RemoveLast();
    
    size_t GetSize() { return current_size; }
    
    ContentType& operator[](size_t position)
    {
        assert(position < current_size);
        return data[position];
    }
    
private:
    ContentType* data;
    size_t current_size;
    size_t total_capacity;
};

// External definition requires template parameters
template <class ContentType>
DynamicArray<ContentType>::~DynamicArray()
{
    if(data)
        delete[] data;
    current_size = total_capacity = 0;
}

Class Template Instantiation

Class template instantiation differs from function templates by requiring the template name followed by <> containing the specific type. The template name itself isn't a real class—the instantiated result constitutes the actual class.

// DynamicArray is template name, DynamicArray<int> is actual type
DynamicArray<int> integer_array;
DynamicArray<double> double_array;

typename vs class in Templates

Generally, typename and class are interchangeable in template declarations. However, typename becomes necessary when referring to dependent types within templates to inform the compiler about type identifiers.

Non-Type Template Parameters

Template Parameter Classification

Template parameters divide into type parameters and non-type parameters.

Type parameters appear in template parameter lists following class or typename.

Non-type parameters use constants as template parameters, treated as constants within templates.

namespace container
{
    template<class ArrayType, size_t ArraySize = 10>
    class FixedArray
    {
    public:
        ArrayType& operator[](size_t index) { return elements[index]; }
        const ArrayType& operator[](size_t index) const { return elements[index]; }
        
        size_t size() const { return current_size; }
        bool empty() const { return 0 == current_size; }
        
    private:
        ArrayType elements[ArraySize];
        size_t current_size;
    };
}

Important notes:

• Floating-point numbers, class objects, and strings cannot serve as non-type template parameters—only integral types are permitted.
• Non-type template parameters must be resolvable at compile time.

Template Specialization

Specialization Purpose

While templates typically create type-independent code, special types might produce incorrect results requiring specialized handling.

// Generic comparison template
template<class Comparable>
bool IsLess(Comparable a, Comparable b)
{
    return a < b;
}

int main()
{
    std::cout << IsLess(5, 10) << std::endl;  // Correct comparison
    
    Date date1(2023, 8, 15);
    Date date2(2023, 8, 16);
    std::cout << IsLess(date1, date2) << std::endl;  // Correct comparison
    
    Date* ptr1 = &date1;
    Date* ptr2 = &date2;
    std::cout << IsLess(ptr1, ptr2) << std::endl;  // Incorrect: compares addresses
    return 0;
}

Template specialization provides special implementations for specific types, available as function template specialization and class template specialization.

Full Specialization

template<class Param1, class Param2>
class DataContainer
{
public:
    DataContainer() { std::cout << "DataContainer<Param1, Param2>" << std::endl; }
private:
    Param1 member1;
    Param2 member2;
};

template<>
class DataContainer<int, char>
{
public:
    DataContainer() { std::cout << "DataContainer<int, char>" << std::endl; }
private:
    int member1;
    char member2;
};

void TestFunction()
{
    DataContainer<int, int> container1;
    DataContainer<int, char> container2;
}

Partial Specialization

Partial specialization imposes additional constraints on template parameters.

template<class T1, class T2>
class DataContainer
{
public:
    DataContainer() { std::cout << "DataContainer<T1, T2>" << std::endl; }
private:
    T1 member1;
    T2 member2;
};

Partial Parameter Specialization

Specializing only some template parameters:

// Specialize second parameter as int
template <class Type1>
class DataContainer<Type1, int>
{
public:
    DataContainer() { std::cout << "DataContainer<Type1, int>" << std::endl; }
private:
    Type1 member1;
    int member2;
};

Parameter Restriction Specialization

Imposing additional constraints on template parameters:

// Pointer specialization
template <typename P1, typename P2>
class DataContainer <P1*, P2*>
{ 
public:
    DataContainer() { std::cout << "DataContainer<P1*, P2*>" << std::endl; }
private:
    P1 member1;
    P2 member2;
};

// Reference specialization
template <typename R1, typename R2>
class DataContainer <R1&, R2&>
{
public:
    DataContainer(const R1& d1, const R2& d2)
        : member1(d1)
        , member2(d2)
    {
        std::cout << "DataContainer<R1&, R2&>" << std::endl;
    }
private:
    const R1 & member1;
    const R2 & member2;
};

void TestSpecialization()
{
    DataContainer<double, int> cont1;      // Calls int specialization
    DataContainer<int, double> cont2;      // Calls base template
    DataContainer<int*, int*> cont3;       // Calls pointer specialization
    DataContainer<int&, int&> cont4(5, 10); // Calls reference specialization
}

Specialization Requirements

Function template specialization requires:

• Existing base function template
• Empty angle brackets following template keyword
• Function name followed by angle brackets specifying specialized types
• Parameter list identical to base template function

Template Separate Compilation

Separate Compilation Concept

Separate compilation involves multiple source files compiling individually into object files, then linking into a single executable.

Template Separate Compilation Issues

When template declarations and definitions separate across files:

// header.h
template<class T>
T Add(const T& x, const T& y);

// implementation.cpp
template<class T>
T Add(const T& x, const T& y)
{
    return x + y;
}

// main.cpp
#include "header.h"
int main()
{
    Add(5, 10);
    Add(5.5, 10.5);
    return 0;
}

This approach fails because templates don't instantiate without type information, preventing symbol table generation.

Solutions:

• Place declarations and definitions in the same file (.hpp or .h recommended)
• Explicit instantiation at definition location (not recommended)

Template Summary

Advantages:

• Code reuse and resource conservation through template libraries like STL
• Enhanced code flexibility

Disadvantages:

• Code bloat and increased compilation time
• Complex and confusing error messages