Lesson 08-C++ Generic Programming

Generic Algorithms

Generic Algorithms

Generic algorithms are a set of algorithms that can be applied to multiple data types, implemented through templates. Generic algorithms do not directly access the elements of containers but access and traverse the elements in containers through iterators. This makes the algorithms more general and applicable to various containers.

  • Because they implement the public interfaces of some classic algorithms, they are called “algorithms“; And “generic“, because they can be used for different types of elements and multiple container types, including built-in array types.
  • Generic algorithms themselves do not perform container operations; they rely solely on iterators and iterator operations for implementation.
  • Header files: #include <algorithm> or #include <numeric> (arithmetic-related)
  • Most algorithms achieve their functionality by traversing a segment of elements marked by two iterators.
  • Necessary programming assumption: Algorithms never change the size of the underlying container. Algorithms may change the values of elements stored in the container or move elements within the container, but cannot directly add or delete elements.

Example Suppose we have an integer vector vec, we can use the generic algorithm std::sort to sort it:

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {5, 3, 1, 4, 2};
    
    // Use the generic algorithm sort
    std::sort(vec.begin(), vec.end());

    // Output the sorted vector
    for (int elem : vec) {
        std::cout << elem << " ";
    }

    return 0;
}

Function Objects

Function objects (also known as functors) are objects that can be called like functions. They are often used in generic algorithms as standards for comparison or operations. Function objects provide more flexibility because they can maintain state.

Example Suppose we need to sort a group of strings by their length, we can use a function object:

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

struct StringLengthComparator {
    bool operator()(const std::string& s1, const std::string& s2) const {
        return s1.size() < s2.size();
    }
};

int main() {
    std::vector<std::string> strings = {"apple", "pear", "banana", "kiwi"};

    // Sort using the function object
    std::sort(strings.begin(), strings.end(), StringLengthComparator());

    // Output the sorted strings
    for (const auto& str : strings) {
        std::cout << str << " ";
    }

    return 0;
}

Iterators

Iterators provide a way to access elements in containers and serve as a bridge between containers and algorithms. Iterators can be divided into different categories, such as input iterators, output iterators, forward iterators, bidirectional iterators, and random access iterators.

Example Using iterators to traverse a vector and print its elements:

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // Traverse the vector using iterators
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }

    return 0;
}

Reverse Iterators

Reverse iterators allow you to traverse elements from the end of the container forward. Increment operations point to the previous element, while decrement operations point to the next element.

Example Using reverse iterators to print vector elements from back to front:

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // Traverse from back to front using reverse iterators
    for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
        std::cout << *rit << " ";
    }

    return 0;
}

Stream Iterators

Stream iterators allow you to use generic algorithms to read data from stream objects and write to them.

Example Using stream iterators to read a series of integers from standard input and store them in a vector:

#include <vector>
#include <iostream>
#include <iterator>

int main() {
    std::vector<int> numbers;
    std::copy(std::istream_iterator<int>(std::cin),
              std::istream_iterator<int>(),
              std::back_inserter(numbers));

    // Output the read numbers
    for (int num : numbers) {
        std::cout << num << " ";
    }

    return 0;
}

How to Write Your Own Generic Algorithms.

Determine the Function of the Algorithm

  • Clearly define the problem the algorithm needs to solve.
  • Determine the input and output of the algorithm.

Choose the Appropriate Iterator Type Choose the appropriate iterator type based on the algorithm’s requirements.

  • Input iterator: Read-only access.
  • Output iterator: Write-only access.
  • Forward iterator: Supports read-write access and increment operations.
  • Bidirectional iterator: Supports forward and backward movement.
  • Random access iterator: Supports access to any position.

Define the Algorithm’s Template

  • Use templates to define the algorithm so it can handle different types of data.
  • Ensure the algorithm can handle different types of iterators.

Implement the Algorithm Logic

  • Write the specific implementation of the algorithm.
  • Consider boundary conditions and special cases.

Test the Algorithm

  • Write test cases to verify the correctness and performance of the algorithm.
  • Test with different data types and containers.

Suppose we want to implement a simple algorithm count_if, which counts the number of elements in a container that satisfy a certain condition.

#include <algorithm>
#include <vector>
#include <iostream>

// Custom count_if algorithm
template<typename InputIterator, typename Predicate>
size_t custom_count_if(InputIterator first, InputIterator last, Predicate pred) {
    size_t count = 0;
    for (; first != last; ++first) {
        if (pred(*first)) {
            ++count;
        }
    }
    return count;
}

// Custom predicate
struct is_even {
    bool operator()(int x) const {
        return x % 2 == 0;
    }
};

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // Use the custom count_if algorithm
    size_t even_count = custom_count_if(vec.begin(), vec.end(), is_even());
    std::cout << "Number of even elements: " << even_count << std::endl;

    return 0;
}

Type Deduction

auto and decltype

auto

  • The auto keyword is used to automatically deduce the type of a variable when declaring it.
  • auto can only be used for variable declarations and cannot be used for function parameters or return types (unless using decltype).

Example:

int x = 42;
auto y = x;  // y's type is int

decltype

  • decltype is used to obtain the type of an expression.
  • decltype can be used for function parameters or return types.

Example:

int x = 42;
decltype(x) y = x;  // y's type is int

Function Return Type Example:

decltype(x) get_x() {
    return x;
}

using Keyword

Type Alias

  • The using keyword can be used to define type aliases.
  • Type aliases can make code more readable, especially when defining complex template types.

Example:

template<typename T>
using Vector = std::vector<T>;

Template Alias

  • The using keyword can also be used to define template aliases.
  • Template aliases can make the use of templates more concise.

Example:

template<typename T>
using MyVector = std::vector<T>;

MyVector<int> vec;  // Equivalent to std::vector<int> vec;

Difference Between using and typedef

  • The using keyword can be used to define type aliases and template aliases.
  • typedef can only be used to define type aliases.
  • The using keyword is more modern and recommended.

template<typename T> using and template<typename T> alias

  • Before C++17, the using keyword could only be used to define non-templated type aliases.
  • C++17 introduced the alias keyword, which can be used to define templated type aliases.

Example Using using to define templated type aliases:

template<typename T>
using MyVector = std::vector<T>;

Using alias to define templated type aliases:

template<typename T>
using MyVector = std::vector<T>;

// Or
template<typename T>
using MyVector = std::vector<T>;  // Can also use `using`

Example Code

Here is an example that comprehensively uses auto, decltype, and using:

#include <vector>
#include <iostream>

int main() {
    int x = 42;
    auto y = x;  // y's type is int

    // Use decltype to obtain the type
    decltype(x) z = x;  // z's type is also int

    // Define type alias
    using MyIntVector = std::vector<int>;

    // Use type alias
    MyIntVector vec;
    vec.push_back(1);
    vec.push_back(2);

    // Output elements in the vector
    for (auto elem : vec) {
        std::cout << elem << " ";
    }

    return 0;
}

Type Traits

std::is_same

  • std::is_same is used to check if two types are the same.
  • Returns a std::true_type or std::false_type.

Example:

#include <type_traits>

static_assert(std::is_same<int, int>::value, "Types are not the same");
static_assert(!std::is_same<int, float>::value, "Types should not be the same");

std::is_integral

  • std::is_integral is used to check if a type is an integer type.
  • Returns a std::true_type or std::false_type.

Example:

#include <type_traits>

static_assert(std::is_integral<int>::value, "int is an integral type");
static_assert(!std::is_integral<float>::value, "float is not an integral type");

std::enable_if

  • std::enable_if is used to conditionally enable or disable certain parts of templates.
  • Often used in combination with std::is_same or other type traits.

Example:

#include <type_traits>

template<typename T, typename U, typename = void>
struct Add {
    static T add(T a, U b) {
        return a + b;
    }
};

template<typename T, typename U>
struct Add<T, U, std::enable_if_t<std::is_same<T, U>::value>> {
    static T add(T a, U b) {
        return a + b;
    }
};

int main() {
    auto result1 = Add<int, int>::add(1, 2);  // Works normally
    auto result2 = Add<int, float>::add(1, 2.0f);  // Compilation error
    return 0;
}

std::conditional

  • std::conditional is used to select different types based on conditions.
  • Commonly used in template metaprogramming.

Example:

#include <type_traits>

template<typename T>
struct IsPointer {
    using type = std::false_type;
};

template<typename T>
struct IsPointer<T*> {
    using type = std::true_type;
};

template<typename T>
using PointerType = typename std::conditional<IsPointer<T>::type::value, T, T*>::type;

std::remove_reference

  • std::remove_reference is used to remove reference qualifiers from a type.
  • Returns the underlying type without reference.

Example:

#include <type_traits>

static_assert(std::is_same<int, std::remove_reference<int&>::type>::value, "Should remove reference");
static_assert(std::is_same<int, std::remove_reference<int>::type>::value, "No change for non-reference");

std::remove_cv

  • std::remove_cv is used to remove const and volatile qualifiers from a type.
  • Returns the underlying type without cv qualifiers.

Example:

#include <type_traits>

static_assert(std::is_same<int, std::remove_cv<const int>::type>::value, "Should remove const");
static_assert(std::is_same<int, std::remove_cv<volatile int>::type>::value, "Should remove volatile");

std::make_signed

  • std::make_signed is used to convert an unsigned integer type to its signed counterpart.
  • Returns the signed version of the type.

Example:

#include <type_traits>

static_assert(std::is_same<signed int, std::make_signed<unsigned int>::type>::value, "Should make signed");

std::make_unsigned

  • std::make_unsigned is used to convert a signed integer type to its unsigned counterpart.
  • Returns the unsigned version of the type.

Example:

#include <type_traits>

static_assert(std::is_same<unsigned int, std::make_unsigned<signed int>::type>::value, "Should make unsigned");

std::result_of

  • std::result_of is used to deduce the return type of a callable object or function.
  • It is deprecated in C++17 in favor of std::invoke_result.

Example:

#include <type_traits>

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

static_assert(std::is_same<int, std::result_of<decltype(&add)(int, int)>::type>::value, "Return type should be int");

std::invoke_result

  • std::invoke_result is used to deduce the return type of invoking a callable object or function with given arguments.
  • Introduced in C++17 as a replacement for std::result_of.

Example:

#include <type_traits>

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

static_assert(std::is_same<int, std::invoke_result<decltype(&add), int, int>::type>::value, "Return type should be int");

std::is_constructible

  • std::is_constructible is used to check if a type can be constructed with given arguments.
  • Returns std::true_type if constructible, otherwise std::false_type.

Example:

#include <type_traits>

struct Foo {
    Foo(int) {}
};

static_assert(std::is_constructible<Foo, int>::value, "Foo is constructible from int");
static_assert(!std::is_constructible<Foo>::value, "Foo is not default constructible");

std::is_convertible

  • std::is_convertible is used to check if one type can be converted to another.
  • Returns std::true_type if convertible, otherwise std::false_type.

Example:

#include <type_traits>

static_assert(std::is_convertible<int, double>::value, "int is convertible to double");
static_assert(!std::is_convertible<double, int>::value, "double is not convertible to int without loss");

std::is_base_of

  • std::is_base_of is used to check if one class is a base of another.
  • Returns std::true_type if the first is a base of the second, otherwise std::false_type.

Example:

#include <type_traits>

class Base {};
class Derived : public Base {};

static_assert(std::is_base_of<Base, Derived>::value, "Base is base of Derived");
static_assert(!std::is_base_of<Derived, Base>::value, "Derived is not base of Base");

std::is_pointer

  • std::is_pointer is used to check if a type is a pointer.
  • Returns std::true_type if it is a pointer, otherwise std::false_type.

Example:

#include <type_traits>

static_assert(std::is_pointer<int*>::value, "int* is a pointer");
static_assert(!std::is_pointer<int>::value, "int is not a pointer");

std::is_reference

  • std::is_reference is used to check if a type is a reference.
  • Returns std::true_type if it is a reference, otherwise std::false_type.

Example:

#include <type_traits>

static_assert(std::is_reference<int&>::value, "int& is a reference");
static_assert(!std::is_reference<int>::value, "int is not a reference");

std::is_const

  • std::is_const is used to check if a type is const-qualified.
  • Returns std::true_type if const, otherwise std::false_type.

Example:

#include <type_traits>

static_assert(std::is_const<const int>::value, "const int is const");
static_assert(!std::is_const<int>::value, "int is not const");

std::is_volatile

  • std::is_volatile is used to check if a type is volatile-qualified.
  • Returns std::true_type if volatile, otherwise std::false_type.

Example:

#include <type_traits>

static_assert(std::is_volatile<volatile int>::value, "volatile int is volatile");
static_assert(!std::is_volatile<int>::value, "int is not volatile");

std::is_trivial

  • std::is_trivial is used to check if a type is trivial (can be memcpy’ed, etc.).
  • Returns std::true_type if trivial, otherwise std::false_type.

Example:

#include <type_traits>

struct Trivial { int x; };

static_assert(std::is_trivial<Trivial>::value, "Trivial is trivial");

std::is_trivially_copyable

  • std::is_trivially_copyable checks if a type is trivially copyable.
  • Useful for optimizations like memcpy.

Example:

#include <type_traits>

struct TriviallyCopyable { int x; };

static_assert(std::is_trivially_copyable<TriviallyCopyable>::value, "Should be trivially copyable");

std::is_standard_layout

  • std::is_standard_layout checks if a type has standard layout (compatible with C structs).
  • Returns std::true_type if standard layout.

Example:

#include <type_traits>

struct StandardLayout { int x; double y; };

static_assert(std::is_standard_layout<StandardLayout>::value, "Should have standard layout");

std::is_pod (deprecated in C++20)

  • std::is_pod checks if a type is a Plain Old Data type.
  • Deprecated in C++20; use std::is_trivial and std::is_standard_layout instead.

Example:

#include <type_traits>

struct POD { int x; };

static_assert(std::is_pod<POD>::value, "Should be POD");

std::is_literal_type (deprecated in C++17)

  • std::is_literal_type checks if a type is a literal type.
  • Deprecated in C++17.

Example:

#include <type_traits>

static_assert(std::is_literal_type<int>::value, "int is literal type");

std::is_empty

  • std::is_empty checks if a type is empty (no non-static data members).
  • Returns std::true_type if empty.

Example:

#include <type_traits>

struct Empty {};

static_assert(std::is_empty<Empty>::value, "Empty is empty");

std::is_polymorphic

  • std::is_polymorphic checks if a type is polymorphic (has virtual functions).
  • Returns std::true_type if polymorphic.

Example:

#include <type_traits>

class Polymorphic { virtual void f() {}; };

static_assert(std::is_polymorphic<Polymorphic>::value, "Should be polymorphic");

std::is_abstract

  • std::is_abstract checks if a type is abstract (has pure virtual functions).
  • Returns std::true_type if abstract.

Example:

#include <type_traits>

class Abstract { virtual void f() = 0; };

static_assert(std::is_abstract<Abstract>::value, "Should be abstract");

std::is_final

  • std::is_final checks if a class is marked as final.
  • Returns std::true_type if final.

Example:

#include <type_traits>

class Final final {};

static_assert(std::is_final<Final>::value, "Should be final");

std::is_aggregate

  • std::is_aggregate checks if a type is an aggregate (can be aggregate-initialized).
  • Introduced in C++17.

Example:

#include <type_traits>

struct Aggregate { int x; };

static_assert(std::is_aggregate<Aggregate>::value, "Should be aggregate");

std::is_signed

  • std::is_signed checks if an arithmetic type is signed.
  • Returns std::true_type if signed.

Example:

#include <type_traits>

static_assert(std::is_signed<signed int>::value, "signed int is signed");
static_assert(!std::is_signed<unsigned int>::value, "unsigned int is not signed");

std::is_unsigned

  • std::is_unsigned checks if an arithmetic type is unsigned.
  • Returns std::true_type if unsigned.

Example:

#include <type_traits>

static_assert(std::is_unsigned<unsigned int>::value, "unsigned int is unsigned");
static_assert(!std::is_unsigned<signed int>::value, "signed int is not unsigned");

std::is_array

  • std::is_array checks if a type is an array.
  • Returns std::true_type if array.

Example:

#include <type_traits>

static_assert(std::is_array<int[5]>::value, "int[5] is array");
static_assert(!std::is_array<int>::value, "int is not array");

std::is_enum

  • std::is_enum checks if a type is an enumeration.
  • Returns std::true_type if enum.

Example:

#include <type_traits>

enum Enum { A };

static_assert(std::is_enum<Enum>::value, "Enum is enum");

std::is_union

  • std::is_union checks if a type is a union.
  • Returns std::true_type if union.

Example:

#include <type_traits>

union Union { int x; };

static_assert(std::is_union<Union>::value, "Union is union");

std::is_class

  • std::is_class checks if a type is a class (not union).
  • Returns std::true_type if class.

Example:

#include <type_traits>

class Class {};

static_assert(std::is_class<Class>::value, "Class is class");

std::is_function

  • std::is_function checks if a type is a function type.
  • Returns std::true_type if function.

Example:

#include <type_traits>

static_assert(std::is_function<decltype(main)>::value, "main is function");

std::is_lvalue_reference

  • std::is_lvalue_reference checks if a type is an lvalue reference.
  • Returns std::true_type if lvalue reference.

Example:

#include <type_traits>

static_assert(std::is_lvalue_reference<int&>::value, "int& is lvalue reference");

std::is_rvalue_reference

  • std::is_rvalue_reference checks if a type is an rvalue reference.
  • Returns std::true_type if rvalue reference.

Example:

#include <type_traits>

static_assert(std::is_rvalue_reference<int&&>::value, "int&& is rvalue reference");

std::is_fundamental

  • std::is_fundamental checks if a type is a fundamental type (arithmetic or void).
  • Returns std::true_type if fundamental.

Example:

#include <type_traits>

static_assert(std::is_fundamental<int>::value, "int is fundamental");

std::is_arithmetic

  • std::is_arithmetic checks if a type is arithmetic (integral or floating-point).
  • Returns std::true_type if arithmetic.

Example:

#include <type_traits>

static_assert(std::is_arithmetic<int>::value, "int is arithmetic");
static_assert(std::is_arithmetic<double>::value, "double is arithmetic");

std::is_floating_point

  • std::is_floating_point checks if a type is a floating-point type.
  • Returns std::true_type if floating-point.

Example:

#include <type_traits>

static_assert(std::is_floating_point<double>::value, "double is floating-point");
static_assert(!std::is_floating_point<int>::value, "int is not floating-point");

std::is_compound

  • std::is_compound checks if a type is compound (not fundamental).
  • Returns std::true_type if compound.

Example:

#include <type_traits>

class Compound {};

static_assert(std::is_compound<Compound>::value, "Compound is compound");
static_assert(!std::is_compound<int>::value, "int is not compound");

std::is_member_pointer

  • std::is_member_pointer checks if a type is a pointer to a member.
  • Returns std::true_type if member pointer.

Example:

#include <type_traits>

class Member { int x; };

static_assert(std::is_member_pointer<decltype(&Member::x)>::value, "Is member pointer");

std::is_object

  • std::is_object checks if a type is an object type (not function, reference, or void).
  • Returns std::true_type if object.

Example:

#include <type_traits>

static_assert(std::is_object<int>::value, "int is object");
static_assert(!std::is_object<int&>::value, "int& is not object");

std::is_scalar

  • std::is_scalar checks if a type is scalar (arithmetic, enum, pointer, member pointer, or null pointer).
  • Returns std::true_type if scalar.

Example:

#include <type_traits>

static_assert(std::is_scalar<int>::value, "int is scalar");
static_assert(std::is_scalar<int*>::value, "int* is scalar");

std::is_trivially_constructible

  • std::is_trivially_constructible checks if a type is trivially constructible with given arguments.
  • Returns std::true_type if trivially constructible.

Example:

#include <type_traits>

static_assert(std::is_trivially_constructible<int>::value, "int is trivially constructible");<br>

std::is_trivially_default_constructible

  • Checks if trivially default constructible.

Example:

#include <type_traits>

static_assert(std::is_trivially_default_constructible<int>::value, "int is trivially default constructible");

std::is_trivially_copy_constructible

  • Checks if trivially copy constructible.

Example:

#include <type_traits>

static_assert(std::is_trivially_copy_constructible<int>::value, "int is trivially copy constructible");

std::is_trivially_move_constructible

  • Checks if trivially move constructible.

Example:

#include <type_traits>

static_assert(std::is_trivially_move_constructible<int>::value, "int is trivially move constructible");

std::is_trivially_assignable

  • Checks if trivially assignable from another type.

Example:

#include <type_traits>

static_assert(std::is_trivially_assignable<int, int>::value, "int is trivially assignable from int");

std::is_trivially_copy_assignable

  • Checks if trivially copy assignable.

Example:

#include <type_traits>

static_assert(std::is_trivially_copy_assignable<int>::value, "int is trivially copy assignable");

std::is_trivially_move_assignable

  • Checks if trivially move assignable.

Example:

#include <type_traits>

static_assert(std::is_trivially_move_assignable<int>::value, "int is trivially move assignable");

std::is_trivially_destructible

  • Checks if trivially destructible.

Example:

#include <type_traits>

static_assert(std::is_trivially_destructible<int>::value, "int is trivially destructible");

std::is_nothrow_constructible

  • Checks if nothrow constructible with given arguments.

Example:

#include <type_traits>

static_assert(std::is_nothrow_constructible<int>::value, "int is nothrow constructible");

std::is_nothrow_default_constructible

  • Checks if nothrow default constructible.

Example:

#include <type_traits>

static_assert(std::is_nothrow_default_constructible<int>::value, "int is nothrow default constructible");

std::is_nothrow_copy_constructible

  • Checks if nothrow copy constructible.

Example:

#include <type_traits>

static_assert(std::is_nothrow_copy_constructible<int>::value, "int is nothrow copy constructible");

std::is_nothrow_move_constructible

  • Checks if nothrow move constructible.

Example:

#include <type_traits>

static_assert(std::is_nothrow_move_constructible<int>::value, "int is nothrow move constructible");

std::is_nothrow_assignable

  • Checks if nothrow assignable from another type.

Example:

#include <type_traits>

static_assert(std::is_nothrow_assignable<int, int>::value, "int is nothrow assignable from int");

std::is_nothrow_copy_assignable

  • Checks if nothrow copy assignable.

Example:

#include <type_traits>

static_assert(std::is_nothrow_copy_assignable<int>::value, "int is nothrow copy assignable");

std::is_nothrow_move_assignable

  • Checks if nothrow move assignable.

Example:

#include <type_traits>

static_assert(std::is_nothrow_move_assignable<int>::value, "int is nothrow move assignable");

std::is_nothrow_destructible

  • Checks if nothrow destructible.

Example:

#include <type_traits>

static_assert(std::is_nothrow_destructible<int>::value, "int is nothrow destructible");

std::has_virtual_destructor

  • Checks if a class has a virtual destructor.

Example:

#include <type_traits>

class HasVirtualDestructor { virtual ~HasVirtualDestructor(); };

static_assert(std::has_virtual_destructor<HasVirtualDestructor>::value, "Has virtual destructor");

std::alignment_of

  • Provides the alignment requirement of a type.

Example:

#include <type_traits>

static_assert(std::alignment_of<int>::value == alignof(int), "Alignment matches");

std::rank

  • Provides the rank (number of dimensions) of an array type.

Example:

#include <type_traits>

static_assert(std::rank<int[5][3]>::value == 2, "Rank is 2");

std::extent

  • Provides the extent (size) of an array dimension.

Example:

#include <type_traits>

static_assert(std::extent<int[5][3]>::value == 5, "Extent of first dimension is 5");
static_assert(std::extent<int[5][3], 1>::value == 3, "Extent of second dimension is 3");

std::is_void

  • Checks if a type is void.

Example:

#include <type_traits>

static_assert(std::is_void<void>::value, "void is void");
static_assert(!std::is_void<int>::value, "int is not void");

std::is_null_pointer

  • Checks if a type is std::nullptr_t.

Example:

#include <type_traits>

static_assert(std::is_null_pointer<std::nullptr_t>::value, "nullptr_t is null pointer");

std::is_member_object_pointer

  • Checks if a type is a pointer to a non-static member object.

Example:

#include <type_traits>

class MemberObject { int x; };

static_assert(std::is_member_object_pointer<decltype(&MemberObject::x)>::value, "Is member object pointer");

std::is_member_function_pointer

  • Checks if a type is a pointer to a non-static member function.

Example:

#include <type_traits>

class MemberFunction { void f(); };

static_assert(std::is_member_function_pointer<decltype(&MemberFunction::f)>::value, "Is member function pointer");

std::is_null_pointer (C++14)

  • Already covered above.

std::is_invocable (C++17)

  • Checks if a callable type can be invoked with given arguments.

Example:

#include <type_traits>

static_assert(std::is_invocable<decltype(add), int, int>::value, "add is invocable with int, int");

std::is_invocable_r (C++17)

  • Checks if invocable and returns a type convertible to a specified type.

Example:

#include <type_traits>

static_assert(std::is_invocable_r<int, decltype(add), int, int>::value, "Returns int");

std::is_nothrow_invocable (C++17)

  • Checks if nothrow invocable.

Example:

#include <type_traits>

static_assert(std::is_nothrow_invocable<decltype(add), int, int>::value, "Nothrow invocable");

std::is_nothrow_invocable_r (C++17)

  • Checks if nothrow invocable and returns convertible type.

Example:

#include <type_traits>

static_assert(std::is_nothrow_invocable_r<int, decltype(add), int, int>::value, "Nothrow returns int");

std::is_swappable (C++17)

  • Checks if two types are swappable.

Example:

#include <type_traits>

static_assert(std::is_swappable<int>::value, "int is swappable");

std::is_nothrow_swappable (C++17)

  • Checks if nothrow swappable.

Example:

#include <type_traits>

static_assert(std::is_nothrow_swappable<int>::value, "int is nothrow swappable");

std::is_swappable_with (C++17)

  • Checks if swappable with another type.

Example:

#include <type_traits>

static_assert(std::is_swappable_with<int&, int&>::value, "Swappable with");

std::is_nothrow_swappable_with (C++17)

  • Checks if nothrow swappable with another type.

Example:

#include <type_traits>

static_assert(std::is_nothrow_swappable_with<int&, int&>::value, "Nothrow swappable with");

std::underlying_type (for enums)

  • Provides the underlying type of an enum.

Example:

#include <type_traits>

enum EnumUnderlying : unsigned int { };

static_assert(std::is_same<unsigned int, std::underlying_type<EnumUnderlying>::type>::value, "Underlying is unsigned int");

std::remove_const

  • Removes const qualifier.

Example:

#include <type_traits>

static_assert(std::is_same<int, std::remove_const<const int>::type>::value, "Removes const");

std::remove_volatile

  • Removes volatile qualifier.

Example:

#include <type_traits>

static_assert(std::is_same<int, std::remove_volatile<volatile int>::type>::value, "Removes volatile");

std::add_const

  • Adds const qualifier.

Example:

#include <type_traits>

static_assert(std::is_same<const int, std::add_const<int>::type>::value, "Adds const");

std::add_volatile

  • Adds volatile qualifier.

Example:

#include <type_traits>

static_assert(std::is_same<volatile int, std::add_volatile<int>::type>::value, "Adds volatile");

std::add_cv

  • Adds const and volatile.

Example:

#include <type_traits>

static_assert(std::is_same<const volatile int, std::add_cv<int>::type>::value, "Adds cv");

std::remove_pointer

  • Removes pointer.

Example:

#include <type_traits>

static_assert(std::is_same<int, std::remove_pointer<int*>::type>::value, "Removes pointer");

std::add_pointer

  • Adds pointer.

Example:

#include <type_traits>

static_assert(std::is_same<int*, std::add_pointer<int>::type>::value, "Adds pointer");

std::remove_extent

  • Removes array extent.

Example:

#include <type_traits>

static_assert(std::is_same<int[3], std::remove_extent<int[5][3]>::type>::value, "Removes extent");

std::remove_all_extents

  • Removes all array extents.

Example:

#include <type_traits>

static_assert(std::is_same<int, std::remove_all_extents<int[5][3]>::type>::value, "Removes all extents");

std::add_lvalue_reference

  • Adds lvalue reference.

Example:

#include <type_traits>

static_assert(std::is_same<int&, std::add_lvalue_reference<int>::type>::value, "Adds lvalue reference");

std::add_rvalue_reference

  • Adds rvalue reference.

Example:

#include <type_traits>

static_assert(std::is_same<int&&, std::add_rvalue_reference<int>::type>::value, "Adds rvalue reference");

std::decay

  • Applies lvalue-to-rvalue, array-to-pointer, function-to-pointer conversions, and removes cv qualifiers.

Example:

#include <type_traits>

static_assert(std::is_same<int, std::decay<const int&>::type>::value, "Decays to int");

std::common_type

  • Finds the common type of multiple types.

Example:

#include <type_traits>

static_assert(std::is_same<double, std::common_type<int, double>::type>::value, "Common type is double");

std::aligned_storage

  • Provides storage with given size and alignment.

Example:

#include <type_traits>

using Storage = std::aligned_storage<sizeof(int), alignof(int)>::type;

std::aligned_union

  • Provides storage for union with alignment.

Example:

#include <type_traits>

using UnionStorage = std::aligned_union<sizeof(int), int, double>::type;

std::bool_constant

  • Alias for integral_constant with bool.

Example:

#include <type_traits>

using TrueType = std::bool_constant<true>;

std::integral_constant

  • Wraps a constant value of integral type.

Example:

#include <type_traits>

using Five = std::integral_constant<int, 5>;

std::void_t (C++17)

  • Maps types to void, useful in SFINAE.

Example:

#include <type_traits>

template<typename T, typename = void>
struct HasType { static constexpr bool value = false; };

template<typename T>
struct HasType<T, std::void_t<typename T::type>> { static constexpr bool value = true; };

std::conjunction (C++17)

  • Logical AND of type traits.

Example:

#include <type_traits>

static_assert(std::conjunction<std::true_type, std::true_type>::value, "True");
static_assert(!std::conjunction<std::true_type, std::false_type>::value, "False");

std::disjunction (C++17)

  • Logical OR of type traits.

Example:

#include <type_traits>

static_assert(std::disjunction<std::true_type, std::false_type>::value, "True");
static_assert(!std::disjunction<std::false_type, std::false_type>::value, "False");

std::negation (C++17)

  • Logical NOT of a type trait.

Example:

#include <type_traits>

static_assert(std::negation<std::false_type>::value, "True");
static_assert(!std::negation<std::true_type>::value, "False");

SFINAE

SFINAE Principle

SFINAE (Substitution Failure Is Not An Error) is a principle in C++ template metaprogramming. When the compiler substitutes template parameters, if an error occurs during substitution, the compiler does not report an error but ignores that template specialization and continues to look for other valid specializations.

Example

Suppose we have two function templates:

template<typename T>
typename T::value_type foo(T t) {
    return t.value;
}

template<typename T>
T foo(T t) {
    return t;
}

If we call foo(5), the first template substitution fails (int has no value_type), so the compiler chooses the second template.

Using SFINAE for Type Detection

SFINAE can be used to detect if a type has certain members or supports certain operations.

Example

Detect if a type has a member function size():

#include <type_traits>

template<typename T, typename = void>
struct has_size : std::false_type {};

template<typename T>
struct has_size<T, std::void_t<decltype(std::declval<T>().size())>> : std::true_type {};

SFINAE in Function Overloading

SFINAE can be used in function overloading to enable or disable certain overloads based on type traits.

Example

template<typename T>
std::enable_if_t<std::is_integral_v<T>, void> print(T t) {
    std::cout << "Integral: " << t << std::endl;
}

template<typename T>
std::enable_if_t<std::is_floating_point_v<T>, void> print(T t) {
    std::cout << "Floating point: " << t << std::endl;
}

SFINAE in Class Template Specialization

SFINAE can also be applied to class template specializations.

Example

template<typename T, typename = void>
struct Processor {
    void process() { std::cout << "General processor" << std::endl; }
};

template<typename T>
struct Processor<T, std::enable_if_t<std::is_integral_v<T>>> {
    void process() { std::cout << "Integral processor" << std::endl; }
};

Example Code

Here is an example demonstrating SFINAE for detecting if a type is iterable:

#include <type_traits>
#include <iterator>
#include <iostream>

template<typename T, typename = void>
struct is_iterable : std::false_type {};

template<typename T>
struct is_iterable<T, std::void_t<decltype(std::begin(std::declval<T>())),
                                  decltype(std::end(std::declval<T>()))>> : std::true_type {};

int main() {
    std::cout << std::boolalpha;
    std::cout << "std::vector<int>: " << is_iterable<std::vector<int>>::value << std::endl;
    std::cout << "int: " << is_iterable<int>::value << std::endl;
    return 0;
}

Concepts

Concepts in C++20

Concepts Introduction

Concepts are a new feature introduced in C++20, used to constrain template parameters. Concepts allow developers to specify requirements for template parameters, making templates more expressive and easier to use.

Example:

#include <concepts>

template<typename T>
concept Numeric = std::is_arithmetic_v<T>;

template<Numeric T>
T add(T a, T b) {
    return a + b;
}

Concept Syntax

Defining Concepts

Concepts are defined using the concept keyword, followed by the concept name and requirements.

Example:

template<typename T>
concept Integral = std::is_integral_v<T>;

Using Concepts

Concepts can be used to constrain template parameters.

Example:

template<Integral T>
void foo(T t) {
    // ...
}

Compound Requirements

Compound Requirements

Compound requirements allow combining multiple constraints.

Example:

template<typename T>
concept Addable = requires(T a, T b) {
    a + b;
};

Nested Requirements

Nested Requirements

Nested requirements allow nesting constraints within concepts.

Example:

template<typename T>
concept Container = requires(T t) {
    typename T::value_type;
    t.begin();
    t.end();
};

Requires Expressions

Requires Expressions

Requires expressions are used to specify requirements in concepts.

Example:

template<typename T>
concept Hashable = requires(T t) {
    { std::hash<T>{}(t) } -> std::convertible_to<std::size_t>;
};

Standard Library Concepts

Standard Library Concepts

The C++20 standard library provides many predefined concepts, such as std::integral, std::floating_point, etc.

Example:

#include <concepts>

template<std::integral T>
T factorial(T n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

Example Code

Here is an example using concepts to constrain a template function:

#include <concepts>
#include <iostream>

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

int main() {
    std::cout << add(5, 10) << std::endl;  // Valid
    // add(5.0, 10.0);  // Compilation error: not integral
    return 0;
}

C++20 New Features

Concepts

Concepts allow defining constraints on template parameters, making template code more readable and easier to debug.

Example:

template<typename T>
concept Integral = std::is_integral_v<T>;

template<Integral T>
void foo(T t) {
    // ...
}

Requires Clauses

Requires clauses allow specifying additional constraints on templates.

Example:

template<typename T>
    requires Integral<T>
void bar(T t) {
    // ...
}

Abbreviated Function Templates

Abbreviated function templates allow using auto as placeholder for template parameters.

Example:

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

C++23 New Features

More Improvements on Concepts

  • Extensions to Concepts: C++23 extends Concepts, including more powerful concept combinations and default values for concepts.

Example:

template<typename T>
concept Integral = std::is_integral_v<T>;

template<typename T>
concept FloatingPoint = std::is_floating_point_v<T>;

template<Integral T, FloatingPoint U>
concept Numeric = true;

template<Numeric T, Numeric U>
auto add(T a, U b) {
    return a + b;
}

Improvements to template parameter packs: C++23 introduces more improvements to template parameter packs, such as improvements to std::apply.

Example:

template<typename F, typename... Args>
auto apply(F&& f, std::tuple<Args...>&& args) {
    return std::apply(std::forward<F>(f), std::forward_as_tuple(args));
}

Example Code

Here is an example code using new features from C++20 and C++23:

#include <concepts>
#include <iostream>

// C++20 Concepts
template<typename T>
concept Numeric = requires(T t) {
    t + t;  // Requires T to support addition
};

template<Numeric T>
T add(T a, T b) {
    return a + b;
}

// C++23 Concepts
template<typename T>
concept Integral = std::is_integral_v<T>;

template<typename T>
concept FloatingPoint = std::is_floating_point_v<T>;

template<Integral T, FloatingPoint U>
concept Numeric23 = true;

template<Numeric23 T, Numeric23 U>
auto add23(T a, U b) {
    return a + b;
}

int main() {
    auto result = add(5, 10);  // Valid call
    auto result23 = add23(5, 10.0f);  // Valid call
    
    std::cout << "Result: " << result << std::endl;
    std::cout << "Result23: " << result23 << std::endl;
    
    return 0;
}

Generic Programming Style

Understanding Generic Programming with Examples

Requirement:

A vector storing integers and an integer; if this integer exists in the vector, return a pointer to that integer; otherwise, return 0.


int* find(const vector<int> &vec, int value) {
    for (int ix = 0; ix < vec.size(); ++ix)
        if (vec[ix] == value)
            return &vec[ix];
    return 0;
}

Requirement:

Hope this function can handle not only integers but any type—provided the type has an equality operator.


template <typename elemType>
elemType* find(const vector<elemType> &vec,
               const elemType &value) {
    for (int ix = 0; ix < vec.size(); ++ix)
        if (vec[ix] == value)
            return &vec[ix];
    return 0;
}

Requirement:

Hope this function can handle both vector and array.

Because both vector and array are sequential containers and store all elements in contiguous memory, pointer arithmetic (increment) is meaningful. We can pass a first pointer and a last pointer for end checking, comparing elements between the two pointers with value.


template <typename elemType>
elemType* find(const elemType *first,
               const elemType *last,
               const elemType &value) {
    if (!first || !last)
        return 0;
    for (; first != last; ++first)
        if (*first == value)
            return first
    return 0;
}

The call to the above code is a bit cumbersome and has some issues:

vector<string> svec; // Define an empty vector
find(&svec[0], &svec[svec.size()], search_value);
/*
If vector is empty, this code errors out.
A safer way is to check if svec is empty first,
then call find() if not empty.
*/

Make it more robust:

template <typename elemType>
inline elemType* begin(const vector<elemType> &vec) {
    return vec.empty() ? 0 : &vec[0];

}
// end() function similarly

Now we can call find() like this:

find(begin(svec), end(svec), search_value);

Requirement:

Hope find() can support list type.

Because pointer arithmetic assumes all elements are stored in contiguous space, then adds the element size to the current pointer to point to the next element. This is the most basic assumption in the previous find() implementation. But list breaks this assumption.

The solution is to provide a layer of abstraction over the underlying pointer behavior, replacing the original “direct pointer operation” in the program.

// find() supports pointers and a pair of iterators pointing to a container
template <typename IteratorType, typename elemType>
IteratorType find(IteratorType first,
                  IteratorType last,
                  const elemType &value) {
    for (; first != last; ++first)
        if (*first == value)
            return first;
    return last;
}

// Calling this function
list<int> ilist(iarr, iarr + size);// iarr is array, size: array size
list<int>::iterator iter;
iter = find(ilist.begin(), ilist.end(), 1024);
if (iter != ilist.end()) {
    do something;
}

It is necessary to note that for const containers, use const_iterator:

cosnt vector<string> cs_vec;
vector<string>::cosnt_iterator iter = cs_vec.begin();

decltype and std::declval

decltype is a keyword introduced in C++11, used to obtain the type of an expression or variable. Its syntax form is decltype(expression), where expression is a valid C++ expression.

std::declval is a template function defined in the <utility> header file, used to produce a temporary reference that can be used as an rvalue. Its main purpose is to perform declaration type deduction on non-copyable or non-movable types. It is usually used in combination with decltype.


#include <iostream>
#include <utility>

struct Foo {
    int x;
    double y;
};

int main() {
    decltype(Foo().x) a;  // a's type is int
    decltype(std::declval<Foo>().y) b;  // b's type is double
  
    std::cout << typeid(a).name() << std::endl;  // Print int's type name
    std::cout << typeid(b).name() << std::endl;  // Print double's type name
    return 0;
}

Understanding using ResultType = decltype(std::declval<FunctionType>()());:

This line of code is used to deduce the return type of the function type FunctionType and define it as ResultType.

Let’s explain the meaning of this line step by step:

  1. std::declval<FunctionType>(): std::declval is a template function used to generate an rvalue reference. Here, we use std::declval to generate a temporary object (rvalue) of type FunctionType.
  2. decltype(std::declval<FunctionType>()): The decltype keyword deduces and returns the type of the expression in parentheses. Here, we use decltype to deduce the type of the expression std::declval<FunctionType>(), which is the function type FunctionType.
  3. decltype(std::declval<FunctionType>()()): Since std::declval<FunctionType>() represents a function, we call the function by adding an extra pair of empty parentheses () and deduce the type of the call result.
  4. using ResultType = decltype(std::declval<FunctionType>()());: Finally, use the using keyword to define the alias ResultType and assign the type of the function call result deduced by decltype to it.

Understanding using RetType = decltype(f(args...));:

This line of code is used to deduce the return type of the function call f(args...) and define it as RetType.

Let’s explain the meaning of this line step by step:

  1. f(args...): This is a function call expression, where f is a function name, and args are the parameters of the function call.
  2. decltype(f(args...)): The decltype keyword deduces and returns the type of the expression in parentheses. Here, we use decltype to deduce the return type of the result of the function call f(args...).
  3. using RetType = decltype(f(args...));: Through the using keyword, we define the alias RetType and assign the type of the function call result deduced by decltype to it.

Using template <int type> to Achieve the Same Effect as switch case

When using template <int type> for template definition, here is a specific code example:


#include <iostream>
template <int type>

void templateFunction() {
    if (type == 0) {
        std::cout << "Type is 0." << std::endl;
    } else if (type == 1) {
        std::cout << "Type is 1." << std::endl;
    } else {
        std::cout << "Type is not recognized." << std::endl;
    }
}

int main() {
    templateFunction<0>(); // Call templateFunction with parameter 0
    templateFunction<1>(); // Call templateFunction with parameter 1
    templateFunction<2>(); // Call templateFunction with parameter 2
    return 0;
}

In the above example, templateFunction is a template function with template parameter type being an integer. Depending on the different values of the passed type parameter, the function will execute different logic.

In the main function, by using <0>, <1>, and <2>, the templateFunction template function is instantiated respectively, generating three specific function instances. Each instance will print the corresponding message based on the passed type parameter value.

When running the program, the output will be as follows:

Type is 0.
Type is 1.
Type is not recognized.

This example demonstrates that the template function generates specific code instances at compile time based on the passed parameter values and selects the corresponding logic at runtime. Through template parameters, an effect similar to a switch statement can be achieved, executing different code logic in different cases.

Share your love