Generic Programming

Consider an example: How to implement a generic swap function?

In C++, function overloading allows us to use the same function name for different types. For example:

void Exchange(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}

void Exchange(double& a, double& b)
{
    double temp = a;
    a = b;
    b = temp;
}

void Exchange(char& a, char& b)
{
    char temp = a;
    a = b;
    b = temp;
}

In C, this would require different function names and lacks reference syntax. However, both approaches are cumbersome because each new type requires writing another function.

Disadvantages:

1. Overloaded functions differ only in type, leading to low code reuse; new types require additional functions.
2. Low maintainability; an error in one overload might affect all.

Imagine movable type printing, where changing characters in a mold produces different texts. Similarly, in C++, templates allow creating a mold that the compiler uses to generate code for different types.

Generic programming involves writing type-independent code for reuse. Templates are the foundation of generic programming.

Templates are divided into two categories: function templates and class templates.

Function Templates

Concept

A function template represents a family of functions that are type-independent. It is parameterized during use, generating specific versions based on argument types.

Format

// Add this before the function
template<typename Type1, typename Type2, ..., typename TypeN>
// Type1, Type2, etc., are placeholder names for types, commonly T, K, V.

// Then write the function
ReturnType FunctionName(ParameterList){}

Example for exchange:

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

typename is the keyword for defining template parameters; class can also be used (note: struct cannot replace class).

In the above code, exchanging int and double uses different generated functions.

How Function Templates Work

Function templates are blueprints, not actual functions. The compiler generates specific type versions based on usage. For instance, when double is used, the compiler deduces T as double and creates code for it.

Proof: In disassembly, addresses for int and double exchange functions differ.

Similarly, the C++ standard library provides a swap function implemented with templates.

Instantiation of Function Templates

Using a function template with different types is called instantiation. It can be implicit or explicit.

1. Implicit Instantiation: Compiler deduces types from arguments. Example:

   Exchange(a, b); // Compiler deduces T as int
   

   Issues arise with mixed types:

   Exchange(a, d1); // Error: cannot decide between int and double
   

   Template functions do not allow automatic type conversion, unlike regular functions.

2. Explicit Instantiation: Specify the type in angle brackets. Example:

   Exchange<int>(a, d1); // Explicitly use int
   

   This is less common in function templates but useful in scenarios like:

   template<typename T>
   T Add(T a, T b)
   {
       return a + b;
   }
   Add<int>(a, d1); // Explicit instantiation
   

When both a template and a regular functon with the same functionality exist, the regular function is prioritized, but this is not recommended.

Class Templates

Definition Format

template<class Type1, class Type2, ..., class TypeN>
class ClassName
{
    // Member definitions
};

Example of a simple class template:

template<typename T>
class DataContainer
{
public:
    DataContainer() : data(T()) {}
    void SetData(T val) { data = val; }
    T GetData() { return data; }
private:
    T data;
};

To define member functions outside the class:

template<typename T>
void DataContainer<T>::SetData(T val)
{
    data = val;
}

Note: Templates do not support separate compilation (declaration in .h, definition in .cpp).

Instantiation of Class Templates

Class templates require explicit type specification during innstantiation. Example:

DataContainer<int> container; // Specify int for T

Stack Example

Here is a complete stack implementation using templates:

template<typename T>
class Stack
{
public:
    Stack(size_t capacity = 4)
        : dataArray(nullptr), topIndex(0), currentCapacity(0)
    {
        if (capacity > 0)
        {
            dataArray = new T[capacity];
            topIndex = 0;
            currentCapacity = capacity;
        }
    }

    ~Stack()
    {
        delete[] dataArray;
        dataArray = nullptr;
        topIndex = currentCapacity = 0;
    }

    void Push(const T& element)
    {
        if (currentCapacity == topIndex)
        {
            size_t newCapacity = currentCapacity == 0 ? 4 : 2 * currentCapacity;
            T* newArray = new T[newCapacity];
            if (dataArray)
            {
                memcpy(newArray, dataArray, sizeof(T) * currentCapacity);
                delete[] dataArray;
            }
            dataArray = newArray;
            currentCapacity = newCapacity;
        }
        dataArray[topIndex] = element;
        ++topIndex;
    }

    void Pop()
    {
        assert(topIndex);
        --topIndex;
    }

    bool IsEmpty()
    {
        return topIndex == 0;
    }

    const T& Top()
    {
        return dataArray[topIndex - 1];
    }

private:
    T* dataArray;
    size_t topIndex;
    size_t currentCapacity;
};

int main()
{
    Stack<int> intStack;
    intStack.Push(1);
    intStack.Push(2);
    intStack.Push(3);
    intStack.Push(4);
    intStack.Push(5);

    while (!intStack.IsEmpty())
    {
        std::cout << intStack.Top() << " ";
        intStack.Pop();
    }
    std::cout << std::endl;

    return 0;
}

Key point: In main, Stack<int> intStack; explicitly specifies the type for the template.