4 Generic Programming in C++

Templates, auto, Generic Functions and Concepts in C++
Author

Daniel Schwarzenbach

The Idea of Generic Programming

One of the main rules of good programing is:

“Don’t repeat yourself.”

Repeating code has several downsides:

  • When you have a bug in the repeated code, you have to fix it in multiple places.
  • It is unnecessary and inefficient to write the same code sample multiple times.
  • It makes your code harder to maintain and understand.

Generic programming helps to avoid code repetition by allowing you to write code once that can work in different contexts with different types.

Macros

Macros in C++ are a way to define code that can be reused with different values or types. They are processed by the preprocessor before the actual compilation begins.

A macro is essentially a piece of code that is copy and pasted by the preprocessor wherever it is used, before the actual compilation takes place.

#include simply tells the preprocessor to include the contents of another file at that point in the code. This is very primitive compared to other programming languages. C++ is soon itroducing modules, which provide a more modern and safer way to manage code dependencies.

For example, you can define a macro to create a simple function that adds two numbers:

// never do this in modern C++ !!!
#define ADD(x, y) ((x) + (y))

You can then use this macro with different types of values:

int a = ADD(3, 4);        // a = 7
double b = ADD(2.5, 1.5); // b = 4.0

You can even use different keywords or to create more complex code patterns.

#define check(x) if (!(x)) { return std::nullopt; }

auto √(double x) -> std::optional<double> {
    // the preprocessor will replace this line
    // check(x >= 0) -> if (!(x >= 0)) { return std::nullopt; }
    check(x >= 0);
    return std::sqrt(x);
}

Macros are really powerful, but maybe a bit too powerful for their own good. They can introduce subtle bugs and make code harder to understand and maintain.

The Problem with Macros

Macros have several limitations and pitfalls:

  • Lack of type safety: The compiler does not check the types of macro arguments, which can lead to unexpected behavior.
  • Multiple evaluations: Arguments in macros can be evaluated multiple times, potentially causing side effects.
  • Debugging difficulty: Errors in macros can be harder to trace and debug compared to regular functions.
  • No scope: Macros do not respect C++ scopes, which can lead to name collisions and unexpected behavior.

Macros are the main reason why the order of includes in C++ files can be important, as they are processed by the preprocessor before compilation. Macro bugs can be particularly tricky to diagnose because they do not follow the usual rules of C++ scoping and type checking.

If you want to use a Marco you should be following the following guidelines:

  • Use macros in implementation files (e.g., .cpp files) rather than header files to minimize potential conflicts and scope issues.
  • If you must use macros in a Header file (e.g., .h or .hpp files), use #ifndef and #define guards to prevent multiple inclusions and potential conflicts. You can also use compiler flags to control macro definitions and avoid conflicts.
  • #include and #pragma once are the only preprocessor directives that are generally safe to use in header files without causing conflicts.

The Keyword auto

The auto keyword in C++ allows the compiler to automatically deduce the type of a variable from its initializer. This can make code more concise and easier to read, especially when dealing with complex types.

For example:

auto x = 42;        // int
auto y = 3.14;      // double
auto z = std::vector<int>{1, 2, 3}; // std::vector<int>

Generic Programming with auto

Using auto in generic programming allows you to write functions that can work with any type without explicitly specifying the type. This can make your code more flexible and easier to maintain.

For example, you can write a generic function to add two values:

auto add(auto a, auto b) {
    return a + b;
}

This function can now be used with different types:

int x = add(3, 4);          // int
double y = add(2.5, 1.5);   // double

Pairs and Tuples

C++ also provides std::pair and std::tuple to group multiple values together. These can be particularly useful in generic programming when you want to return multiple values from a function or store heterogeneous data.

For example, a pair:

std::pair<int, std::string> p = {1, "one"};
auto [num, str] = p; // structured binding, num = 1, str = "one"

And a tuple:

std::tuple<int, double, std::string> t = {1, 3.14, "pi"};
auto [i, d, s] = t; // structured binding, i = 1, d = 3.14, s = "pi"

Templates

Let’s say you want to your own Dictionary class in C++. You start with a naive approach where you set the key and value types explicitly:

  • key: std::string
  • value: int
struct DictionaryString_to_Int {
    ...
    auto operator[](const std::string& key) -> int&;
    ...
};

But now you suddenly need a dictionary with different key and value types, for example:

  • key: int
  • value: std::vector<int>

Well you could just write an entirely new dictionary class for each combination of key and value types, but that quickly becomes unmanageable. Instead, C++ offers a solution called templates, which allow you to write generic code that works with any type.

Here’s how you could define a generic dictionary using templates:

template<typename Key, typename Value>
struct Dictionary {
    ...
    auto operator[](const Key& key) -> Value&;
    ...
};

This dictionary can now be used with any combination of key and value types, making it much more flexible and reusable than writing separate classes for each type combination.

auto main() -> int {
    Dictionary<std::string, int> dict1;
    dict1["age"] = 30;

    Dictionary<int, std::vector<int>> dict2;
    dict2[1] = {1, 2, 3};

    return 0;
}

Implementations of Templates

In the Object-Oriented Programming paradigm, implementations and declarations where usually separated into header and source files. However, with templates, the compiler needs to see the full implementation whenever it instantiates the template. This often means that both the declaration and the implementation of a template must be included in the header file.

Use cases for Templates

Templates can not just be used for classes, they can also be used for functions or redefinitions.

Here is an example of a generic function that takes an input of type IN and returns an output of type OUT:

template<typename IN, typename OUT>
auto my_function(IN x) -> OUT {
    OUT y = x*x;
    return y;
}

auto main() -> int {
    // result will be 25.0
    auto result = my_function<int, double>(5);
    return 0;
}

Here is an example of a redefinition using templates in the case of a directed graph modeled with adjacency lists:

// a directed graph with vertices of type VERTEX
// each vertex maps to a list of adjacent vertices
template<typename VERTEX>
using DirectedGraph = std::map<VERTEX, std::vector<VERTEX>>;

Template Specialization

Template specialization allows you to define a specific implementation of a template for a particular type. This can be useful when the generic implementation is not suitable for certain types.

For example:

template<typename T>
struct Printer {
    void print(const T& value) {
        std::cout << value << std::endl;
    }
};

// Specialization for bool
template<>
struct Printer<bool> {
    void print(const bool& value) {
        std::cout << (value ? "true" : "false") << std::endl;
    }
};

Function Templates

Let’s say you want to take the derivative of a Function. You can take the function as an argument, by resolving it’s type using a template and compute its derivative numerically.

template<typename Function1x1>
auto derivative(Function1x1 f, double x, double h = 1e-5) -> double {
    return (f(x + h) - f(x - h)) / (2 * h);
}

Infinite Arguments

You can also use variadic templates to handle functions with an arbitrary number of arguments.

Let’s say you want to write a minimum function that can take an arbitrary number of arguments of different types. You can achieve this using variadic templates:

#include <iostream>
#include <type_traits> // For std::common_type_t

template<typename T, typename... Ts>
auto min(T first, Ts... args) -> std::common_type_t<T, Ts...> {
    // The common type of all arguments is used to ensure type safety and 
    // correct comparisons.
    using CT = std::common_type_t<T, Ts...>;
    CT result = first;
    for (CT arg : {static_cast<CT>(args)...}) {
        result = (arg < result ? arg : result);
    }
    return result;
}

auto main() -> int {
    auto result = min(3, 0.1, 4, 1, 5, 9);
    std::cout << result << std::endl; // Output: 0.1
    return 0;
}

Metaprogramming

Template metaprogramming allows you to perform computations at compile time using templates. This can be useful for optimizing code and generating code based on types.

For example, you can compute factorials at compile time using template metaprogramming:

template<int N>
struct Factorial {
    static constexpr int value = N * Factorial<N - 1>::value;
};

template<>
struct Factorial<0> {
    static constexpr int value = 1;
};

auto main() -> int {
    // evaluated at compile time
    constexpr int result = Factorial<5>::value;
    std::cout << result << std::endl; // Output: 120
    return 0;
}

Turing Completeness

Template metaprogramming in C++ is Turing complete, which means you can, in theory, perform any computation at compile time that you could perform at runtime. This allows for highly flexible and powerful compile-time computations, but it also requires careful design to avoid overly complex and hard-to-maintain code.

Concepts and Type Traits

Concepts and type traits are tools in C++ that allow you to impose constraints on template parameters and query properties of types at compile time.

Concepts

Concepts are a way to specify requirements for template parameters. They allow you to enforce that a type meets certain criteria, making templates easier to use and understand.

For example:

#include <concepts>
#include <iostream>

template<std::integral T>
T add(T a, T b) {
    return a + b;
}

auto main() -> int {
    std::cout << add(3, 4) << std::endl; // Works
    // Error: double is not an integral type
    std::cout << add(3.5, 4.5) << std::endl;
    return 0;
}

Type Traits

Type traits are templates that provide information about types at compile time. They can be used to check properties of types, such as whether a type is integral, floating-point, or a pointer.

For example:

#include <type_traits>
#include <iostream>

auto main() -> int {
    std::cout << std::boolalpha;
    std::cout << std::is_integral<int>::value << std::endl; // true
    std::cout << std::is_integral<double>::value << std::endl; // false
    return 0;
}