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
autokeyword is used to automatically deduce the type of a variable when declaring it. autocan 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
decltypeis used to obtain the type of an expression.decltypecan 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
usingkeyword 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
usingkeyword 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
usingkeyword can be used to define type aliases and template aliases. typedefcan only be used to define type aliases.- The
usingkeyword is more modern and recommended.
template<typename T> using and template<typename T> alias
- Before C++17, the
usingkeyword could only be used to define non-templated type aliases. - C++17 introduced the
aliaskeyword, 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_sameis used to check if two types are the same.- Returns a
std::true_typeorstd::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_integralis used to check if a type is an integer type.- Returns a
std::true_typeorstd::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_ifis used to conditionally enable or disable certain parts of templates.- Often used in combination with
std::is_sameor 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::conditionalis 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_referenceis 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_cvis 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_signedis 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_unsignedis 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_ofis 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_resultis 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_constructibleis used to check if a type can be constructed with given arguments.- Returns
std::true_typeif constructible, otherwisestd::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_convertibleis used to check if one type can be converted to another.- Returns
std::true_typeif convertible, otherwisestd::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_ofis used to check if one class is a base of another.- Returns
std::true_typeif the first is a base of the second, otherwisestd::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_pointeris used to check if a type is a pointer.- Returns
std::true_typeif it is a pointer, otherwisestd::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_referenceis used to check if a type is a reference.- Returns
std::true_typeif it is a reference, otherwisestd::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_constis used to check if a type is const-qualified.- Returns
std::true_typeif const, otherwisestd::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_volatileis used to check if a type is volatile-qualified.- Returns
std::true_typeif volatile, otherwisestd::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_trivialis used to check if a type is trivial (can be memcpy’ed, etc.).- Returns
std::true_typeif trivial, otherwisestd::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_copyablechecks 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_layoutchecks if a type has standard layout (compatible with C structs).- Returns
std::true_typeif 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_podchecks if a type is a Plain Old Data type.- Deprecated in C++20; use
std::is_trivialandstd::is_standard_layoutinstead.
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_typechecks 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_emptychecks if a type is empty (no non-static data members).- Returns
std::true_typeif empty.
Example:
#include <type_traits>
struct Empty {};
static_assert(std::is_empty<Empty>::value, "Empty is empty");
std::is_polymorphic
std::is_polymorphicchecks if a type is polymorphic (has virtual functions).- Returns
std::true_typeif 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_abstractchecks if a type is abstract (has pure virtual functions).- Returns
std::true_typeif 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_finalchecks if a class is marked as final.- Returns
std::true_typeif final.
Example:
#include <type_traits>
class Final final {};
static_assert(std::is_final<Final>::value, "Should be final");
std::is_aggregate
std::is_aggregatechecks 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_signedchecks if an arithmetic type is signed.- Returns
std::true_typeif 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_unsignedchecks if an arithmetic type is unsigned.- Returns
std::true_typeif 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_arraychecks if a type is an array.- Returns
std::true_typeif 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_enumchecks if a type is an enumeration.- Returns
std::true_typeif enum.
Example:
#include <type_traits>
enum Enum { A };
static_assert(std::is_enum<Enum>::value, "Enum is enum");
std::is_union
std::is_unionchecks if a type is a union.- Returns
std::true_typeif union.
Example:
#include <type_traits>
union Union { int x; };
static_assert(std::is_union<Union>::value, "Union is union");
std::is_class
std::is_classchecks if a type is a class (not union).- Returns
std::true_typeif class.
Example:
#include <type_traits>
class Class {};
static_assert(std::is_class<Class>::value, "Class is class");
std::is_function
std::is_functionchecks if a type is a function type.- Returns
std::true_typeif function.
Example:
#include <type_traits>
static_assert(std::is_function<decltype(main)>::value, "main is function");
std::is_lvalue_reference
std::is_lvalue_referencechecks if a type is an lvalue reference.- Returns
std::true_typeif 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_referencechecks if a type is an rvalue reference.- Returns
std::true_typeif rvalue reference.
Example:
#include <type_traits>
static_assert(std::is_rvalue_reference<int&&>::value, "int&& is rvalue reference");
std::is_fundamental
std::is_fundamentalchecks if a type is a fundamental type (arithmetic or void).- Returns
std::true_typeif fundamental.
Example:
#include <type_traits>
static_assert(std::is_fundamental<int>::value, "int is fundamental");
std::is_arithmetic
std::is_arithmeticchecks if a type is arithmetic (integral or floating-point).- Returns
std::true_typeif 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_pointchecks if a type is a floating-point type.- Returns
std::true_typeif 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_compoundchecks if a type is compound (not fundamental).- Returns
std::true_typeif 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_pointerchecks if a type is a pointer to a member.- Returns
std::true_typeif 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_objectchecks if a type is an object type (not function, reference, or void).- Returns
std::true_typeif 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_scalarchecks if a type is scalar (arithmetic, enum, pointer, member pointer, or null pointer).- Returns
std::true_typeif 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_constructiblechecks if a type is trivially constructible with given arguments.- Returns
std::true_typeif 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;
}
Other Enhancements Related to Generic Programming
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:
std::declval<FunctionType>():std::declvalis a template function used to generate an rvalue reference. Here, we usestd::declvalto generate a temporary object (rvalue) of typeFunctionType.decltype(std::declval<FunctionType>()): Thedecltypekeyword deduces and returns the type of the expression in parentheses. Here, we usedecltypeto deduce the type of the expressionstd::declval<FunctionType>(), which is the function typeFunctionType.decltype(std::declval<FunctionType>()()): Sincestd::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.using ResultType = decltype(std::declval<FunctionType>()());: Finally, use theusingkeyword to define the aliasResultTypeand assign the type of the function call result deduced bydecltypeto 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:
f(args...): This is a function call expression, wherefis a function name, andargsare the parameters of the function call.decltype(f(args...)): Thedecltypekeyword deduces and returns the type of the expression in parentheses. Here, we usedecltypeto deduce the return type of the result of the function callf(args...).using RetType = decltype(f(args...));: Through theusingkeyword, we define the aliasRetTypeand assign the type of the function call result deduced bydecltypeto 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.



