Sunday, April 14, 2024

Install and run Docker on Gentoo Linux

Install and run docker on gentoo linux

1 Introduction

Docker is a container virtualization environment that can establish development or runtime environments without modifying the host operating system. It is faster and lighter than full hardware virtualization.

This article will guide you through the steps required to install and run Docker on Gentoo Linux.

2 Installtion

The official sys-kernel/gentoo-kernel-bin package supports running Docker.

For the customized kernel, refer to Docker: Kernel to configure the proper kernel options.

Default USE flags can be utilized. It is recommended to read the messages for the package app-containers/docker when emerging Docker and recompile the kernel based on what is not set but should be.

To check the kernel configuration compatibility, run:

$ /usr/share/docker/contrib/check-config.sh

Install the app-containers/docker and app-containers/docker-cli packages.

$ sudo emerge --ask --verbose app-containers/docker app-containers/docker-cli

Thursday, April 11, 2024

Connect USB device to WSL

Connect USB device to WSL

Connect USB device to WSL

1 Introduction

This article will guide you through the steps required to connect a USB device to Linux running on Windows Subsystem for Linux (WSL).

2 Prerequisites

  • Install WSL and ensure it is updated to the latest version.

For installation guidance, refer to How to install Linux on Windows with WSL

  • Install a Linux distribution configured to WSL 2.

Heap and Priority Queue

Heap and Priority Queue

1 Introduction to Heap and Priority Queue

A heap is a tree-based data structure that adheres to the heap property: in a max heap, any parent node's key (value) is greater than or equal to the keys of its children. Conversely, in a min heap, the key of a parent node is less than or equal to the keys of its children.

For more details, refer to Wikipedia: Heap (data structure).

A priority queue is an abstract data type similar to a regular queue or stack, where each element has an associated priority. Elements with higher priority are served before those with lower priority.

For more details, refer to Wikipedia: Priority queue.

Although they are conceptually different, priority queues are often referred to as heaps because they are commonly implemented using heaps.

The binary heap is a data structure that efficiently supports the basic priority queue operations. It allows O(1) performance for accessing the root, O(log n) for insertions and deletions, and O(n) for initially building the heap from a set of n elements.

Note that the time complexity to build a heap is O(n log n) using a top-down approach, whereas a bottom-up approach achieves O(n).


Wednesday, February 21, 2024

Monotonic Stack

Monotonic Stack

1 Introduction to monotonic stack

A monotonic stack is a stack whose elements are monotonically increasing or decreasing.

If we pop greater elements from the stack before pushing a new element, the stack will increase from bottom to top. If we pop lesser elements, the stack will decrease.

The typical paradigm for an increasing monotonic stack is like:

for (int i = 0; i < A.size(); i++) {
    while (!stk.empty() && stk.top() > A[i]) {
        stk.pop();
    }
    stk.push(A[i]);
}

2 What can monotonically increasing stacks do?

Monotonically increasing stacks can be used to solve a variety of algorithmic problems. One common use case is for finding the nearest greater element in an array. By maintaining a stack of elements in increasing order, we can quickly determine the next greater element for each element in the array. Monotonically increasing stacks can also be used for finding the maximum area of a histogram, as well as for solving problems related to dynamic programming and graph algorithms.

2.1 To find the previous less element of each element in a vector with O(n) time.

What is the previous less element of an element in a vector? Suppose there is a vector [3, 8, 9, 6], for each element 3, 8, 9, and 6:

  • There is no previous less element for 3.
  • The previous less element of 8 is 3.
  • The previous less element of 9 is 8.
  • The previous less element of 6 is 3.

Monday, February 19, 2024

Monday, January 2, 2023

Modern C++ features

Modern C++

In this article, I am going to give a tutorial for features in modern C++, with very simple examples.

The examples will be made short for beginners to briefly understand the features.

The complete list can be found in the links - C++11, C++14, C++17, C++20.

Please browse to the references for more information.

1 C++11

1.1 nullptr

Considering the function overloading:

void fun(int);
void fun(char *);

Traditionally NULL is often defined as 0. The issue will be, which function will foo(NULL) call?

Thus, C++11 introduces a new kerword, nullptr, as a distinghished null pointer consant.

#include <iostream>

void fun(char *p) {
        std::cout << "hi pointer" << std::endl;

}

void fun(int i) {
        std::cout << "hi integer" << std::endl;

}

int main()
{
        fun(0);
        fun(nullptr);
        //fun(NULL); //this generates an error
        return 0;

}

1.2 Strongly typed enumeration

Enumerations in C++03 are effectively integers. They don't have their own scope.

It is possible to compare two enum values of different enumeration types.

#include <iostream>

int main()
{
        enum Animal {Cat, Dog, Elephant};
        enum Fish {Clam, Dolphin, Eel};

        Animal a = Dog;
        Fish f = Dolphin;

        if (a == f)
                std::cout << "Dog == Dolphin" << std::endl;
        else
                std::cout << "Dog != Dolphin" << std::endl;
        return 0;
}

C++11 introduces the new strongly-typed enumerations, with adding keyword class or struct to the classic enumerations.

They don't implicitly convert to int, and can only be accessed in the scope of the enumeration.

#include <iostream>

int main()
{
        enum class Animal {Cat, Dog, Elephant};
        enum class Fish {Clam, Dolphin, Eel};

        Animal a = Animal::Dog;
        Fish f = Fish::Dolphin;

#if 0
        //there will be a compiling error
        if (a == f)
                std::cout << "Dog == Dolphin" << std::endl;
#endif
        std::cout << "a/Dog converted to int: " << static_cast<int>(a) << std::endl;
        std::cout << "f/Dolphin converted to int: " << static_cast<int>(f) << std::endl;
        return 0;
}

1.3 Uniform initialization

C++11 allows a consistent syntax to intialize variables.

It initializes by using braces to enclose values:

type var_name{arg1, arg2, ...argn}

In the following example, it initializes different types of variables in much the same way.

#include <iostream>

class C
{
public:
        int arr[3];

        C(int x, int y, int z)
                : arr{x, y, z} {}; // initialize an array member

        void show()
        {
                std::cout << arr[0] << " " << arr[1] << " " << arr[2] << std::endl;
        }
};

C fun(C c)
{
        int i{c.arr[0]}; // initialize an integer
        int j{c.arr[1]};
        int k{c.arr[2]};
        return {i, j, k}; // initalize an object to return
}

int main()
{
        C obj = fun({7, 8, 9}); // initialize a function argument
        obj.show();
        return 0;
}

Check also initializer list, regular constructor, and aggregate intialization.

1.4 Ranged based for loop

C++11 extends the syntax of the for statement to allow for easy iteration over a range of elements.

All of the standard library containers that have begin/end pairs will work with the range-based for statement.

#include <iostream>
#include <vector>

int main()
{
        std::vector<int> v{1, 3, 5};
        for (int &i: v) {
                std::cout << i << " ";
        }
        std::cout << std::endl;
        return 0;
}

1.5 Array container

std::array is a container for constant size arrays.

It wraps around arrays, so not to lost its size when declared to a pointer.

#include <array>
#include <iostream>
#include <algorithm>

int main()
{
        std::array<int, 6> a {{2, 6, 1, 5, 4, 3}}; //double braces here
        std::cout << "size of a = " << a.size() << std::endl;
        std::sort(a.begin(), a.end());
        std::cout << "sorted a: ";
        for (auto i : a) {
                std::cout << i << " ";
        }
        std::cout << std::endl;
        return 0;
}

1.6 constexpr

In C++03, there will be a compiling error if we declare an array like this.

int fun() {
        return 3;
}

int main()
{
        int a[2 + fun()]; //compiling error
        return 0;
}

because a function cannot be a constant expression.

C++11 introduces a new keyword constexpr to allow that.

constexpr int fun() { //a function always returns a constant integer
        return 3;
}

int main()
{
        int a[2 + fun()]; //an array of 5 intgeters
        a[4] = 6;
        return 0;
}

constexpr is a declaration specifier that can be applied to:

  • the definition of a variable
  • the declaration of a function or function template
  • the declaration of a static data member

constexpr is a guarantee that the function will be computable at compile-time. This allows compiler to do certain optimizations.

1.7 Explicitly deleted and defaulted functions

C++11 allows to explicitly declare default function with appending =default specifier to its declaration. This controls whether the special member functions are automatically generated.

In the example,

class A {
public:
        A(int a) {};
        A() = default;
};

int main(void)
{
        A a; //default constructor
        A b(1); //parameterized constructor
        return 0;
}

We force the compiler to generate a default constructor. Otherwise, there will be a compiling error, because class A is defined with a parameterized constructor so that the default constructor is not automatically generated.

C++11 also allows to disable certain constructors by using =delete.

Deleted functions also give you simple language to prevent problematic type promotions from occurring in arguments to functions of all types

The following example generates two errors.

class A {
public:
        A(int a) {};
        A(double) = delete; //disable: conversion from double to int
        A& operator=(const A&) = delete; // disable: assignment operator
};

int main(void)
{
        A a(3);
        A b(2.2);
        a = b;
        return 0;
}

The first error at A b(2.2); is because the conversion from double to integer was disabled. The second error at a = b; is because the assignment operator was disabled.

1.8 Delegating constructers

Many classes have multiple constructors do similar things. It is useful for a constructor to call another constructor for delegation.

For the following example,

class A {
        int x, y, z;
public:
        A()
        {
                x = 0;
                y = 0;
                z = 0;
        }
        A(int z)
        {
                x = 0; //redundant
                y = 0; //redundant
                this->z = z;
        }
};

int main(void)
{
        A a(3);
        return 0;
}

We can remove the duplicated code with constructor delegation.

class A {
        int x, y, z;
public:
        A()
        {
                x = 0;
                y = 0;
                z = 0;
        }
        A(int z) : A()
        {
                this->z = z;
        }
};

int main(void)
{
        A a(3);
        return 0;
}

1.9 Automatic type deduction and decltype

In traditional C++, we must specify the type of an object when dclaring it. C++11 let us to declare objects without specifying their types. It takes advantage of the initializer in an object's declaration.

auto a = 1; //a is an integer
auto c = 'x'; //c is a character

Auto keyword used to mean automatic storage type, however, C++11 has changed its meaning: auto declares an object whose type is deducible from its initializer.

It is useful when the type of an object is verbose. Considering:

for (std::vector<int>::const_iterator ci = vec.begin(); ci != vec.end(); ci++)

With auto type deduction, it can be simplified as:

for (auto ci = vec.begin(); ci < vec.end(); ci++)

C++ offers a similar mechanism for capturing the type of an expression: decltype inspects the type of an declared entity.

int a = 1;
decltype(a) b = a + 3; //b : type of a - int

People tend to use auto more often to initialize variables. decltype is used when needing a type of something not a variable, such as a return type.

1.10 Lambda functions

C++11 provides the ability to create ananomous functions, called lambda functions, with the syntax:

[ capture ] (parameters) -> return-type
{
  lambda body
}

It allows a function to be defined at the point needed in another expression.

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

int main()
{
        std::vector<int> v{3, 2, 4, 5, 1};
        sort(v.begin(), v.end(),
                [](const int& i, const int& j) {return i > j;}
                );
        for_each(v.begin(), v.end(),
                [](int i) {std::cout << i << " ";}
                );
        return 0;
}

1.11 Hash tables

Hasing is a technique of mapping keys and values into the hash table using a hash function.

Classical C++ has 4 associative containers (ordered), and C++11 has 4 in addtion (unordered).

  • Classical containers: std::set, std::multiset, std::map, std::multimap
  • C++11 new containers: std::unordered_set, std::unordered_multiset, std::unordered_map, std::unordered_multimap

where if its name has

  • "map": means it has an associated value
  • "multi": means it can have more than one identical key
  • "unordered": means its keys are not sorted

as shown in the following table:

Associative Container Value Ident. keys OK Sorted
std::set      
std::unordered_set     N
std::map Y    
std::unordered_map Y   N
std::multiset   Y  
std::unordered_multiset   Y N
std::multimap Y Y  
std::unordered_multimap Y Y N

The following example demonstrates some basic usages for set and unordered set:

#include <unordered_set>
#include <set>
#include <iostream>

int main()
{
        std::set<int> os {2, 10};
        os.insert(6);
        os.erase(10);
        std::cout << "(ordered) set: ";
        for (auto &s: os) {
                std::cout << s << " ";
        }
        std::cout << std::endl;

        std::unordered_set<int> us {2, 10};
        us.insert(6);
        us.erase(10);
        std::cout << "unordered_set: ";
        for (auto &n: us) {
                std::cout << n << " ";
        }
        std::cout << std::endl;
        return 0;
}

Its output:

(ordered) set: 2 6 unordered_set: 6 2

1.12 rvalue reference and move semantics

Move semantics are created to avoid the unnecessary copying of objects.

Start with below simple example (stackoverflow) - a String class that holds a pointer to some allocated heap.

class String {
        char* data;

public:
        String(const char* p)
        {
                size_t size = strlen(p) + 1;
                data = new char[size];
                memcpy(data, p, size);
                std::cout << data << " created" << std::endl;
        }

        void Print()
        {
                std::cout << "Printing " << data << std::endl;
        }
};

Its destructor and copy constructor are implemented as following.

class String {
public:
        ~String()
        {
                delete[] data;
                std::cout << "Destroyed" << std::endl;
        }

        String(const String& s)
        {
                size_t size = strlen(s.data) + 1;
                data = new char[size];
                memcpy(data, p, size);
                std::cout << data << " copied" << std::endl;
        }
};

The copy constructor defines what it means to copy string objects.

We then implement a second class, Person, to pass String into:

class Person {
        String name;

public:
        Person(const String& s) : name(s) { }

        void PrintName()
        {
                name.Print();
        }
};

In main, we will create a temporary String object as the parameter to create a Person object, and run the program to understand how the functions are being called.

int main()
{
        Person foo {String("Foo")};
        foo.PrintName();
        return 0;
}

It produces the following output:

Foo created Foo copied Destroyed Printing Foo Destroyed

Now we can go through the prompts to understand.

Firstly, we create a String object, so the class constructor is called that prints "Foo created".

Next, in the constructor of the Person object, it copies the String object to data variable and prints "Foo copied". This is where the copy constructor gets called.

Then, the original String object that we created gets destroyed, so the descructor is called that prints "Destoryed".

Finally, we have the Person object print "printing Foo", and then exit the program, which destroys the created Person object and so prints the second "Destroyed".

Allocating memory twice is unnecessary. The unnecessary copies especially when we are dealing with a lot of dynamic data.

In the example, the created String object (Foo) is a rvalue, because underlying it has no name. It is a temporary object which is to be destroyed at the next semicolon - at the end of the full expression containing the ravlue. The client has no way to inspect the String object again later. So we could do whatever we want with the source String, and the client could not tell a difference.

C++11 introduces a new type of reference - rvalue reference, allowing to detect rvalue (temporary) arguements via function overloading. To do so, we add a constructor with an ravlue reference parameter. In that constructor we can do whatever we want with the source String:

class String {
        String(String&& s)
        {
                data = s.data;
                s.data = nullptr;
                std::cout << data << " moved" << std::endl;
        }
};

Instead of copying the heap data, we copy the pointer and set the original pointer to nullptr. In effect, we steal the data that originally belongs to the source String. Since there is no copy here, it is called a "move constructor". Its jobs is to move resources from one object to another.

It is required to set nullptr, in order later on when the destructor gets called on the source object, the memory (we stole) will not be deleted.

We have to do similarly to Person class too. Make it able to take a rvalue reference:

class Person {
public:
        Person(String&& s) : name(std::move(s)) { }
};

The main function stays the same. The program shall produce the following output:

Foo created Foo moved Destroyed Printing Foo Destroyed

Great! No more copying. Rather than the costly allocating on the heap, we simply transfer the memory. This would be the basic idea behind move semantics.

The following is the full code. The copy constructor can be removed here actually. It is kept for your reference.

#include <cstring>
#include <iostream>

class String {
        char* data;

public:
        String(const char* p)
        {
                size_t size = strlen(p) + 1;
                data = new char[size];
                memcpy(data, p, size);
                std::cout << data << " created" << std::endl;
        }

        ~String()
        {
                delete[] data;
                std::cout << "Destroyed" << std::endl;
        }

        String(const String& s)
        {
                size_t size = strlen(s.data) + 1;
                data = new char[size];
                memcpy(data, s.data, size);
                std::cout << data << " copied" << std::endl;
        }

        String(String&& s)
        {
                data = s.data;
                s.data = nullptr;
                std::cout << data << " moved" << std::endl;
        }

        void Print()
        {
                std::cout << "Printing " << data << std::endl;
        }
};

class Person {
        String name;

public:
        Person(const String& s) : name(s) { }

        Person(String&& s) : name(std::move(s)) { }

        void PrintName()
        {
                name.Print();
        }
};

int main()
{
        Person foo {String("Foo")};
        foo.PrintName();
        return 0;
}

1.13 Smart pointer

Smart pointers are used to help ensure programs are free of memory leaks.

The following example leaks by losing the pointer to the allocated memory.

int int main(void)
{
        int* a = new int(5);
        a = nullptr;
}

C++11 provides smart pointers - std::unique_ptr, std::shared_ptr and std::weak_ptr to make sure an object is deleted if it is no longer referenced.

#include <memory>

int main(void)
{
        std::unique_ptr<int> a(new int(5));
        int b = *a;
        return 0;
}

In the above example, an explicit delete is not required. It does not matter if the function scope is left through return or even through an exception. The unique_ptr destructor is always called and the object will always be deleted.

A unique_ptr does not share its pointer. It cannot be copied nor passed by value to a function - it can only be moved.

#include <memory>

int main(void)
{
        std::unique_ptr<int> a(new int(5));
        //std::unique_ptr<int> b = a; //error
        std::unique_ptr<int> c = move(a); //no more usage on a
        return 0;
}

A shared_ptr is a reference counting smart pointer, that can be used to store and pass a reference.

#include <memory>
#include <iostream>

class A {
        std::shared_ptr<int> a;
public:
        A(int a)
        {
                this->a = std::shared_ptr<int>(new int(a));
        }

        std::shared_ptr<int> getA()
        {
                return a;
        }
};

int main(void)
{
        A foo(3);
        std::shared_ptr<int> bar = foo.getA();
        std::cout << *bar << std::endl;
        return 0;
}

All the instances point to the same object, and share one control block that increments and decrements the reference count. When the reference count reaches zero, the control block deletes the memory resource and itself.

weak_ptr is used to access the underlying object of a shared_ptr without causing the reference count to be incremented. It is required typically when you have cyclic references between share_ptr instances.

The smart pointer auto_ptr is deprecated - replaced by unique_ptr.

2 C++14

2.1 Binary literals

Numeric literals can be specified in binary form, using prefixes 0b or 0B.

auto a = 0b101;

2.2 Digit separators

Single quotes can be used as digit separators in numeric literals, for both integers and floating points.

auto i = 1'000'000'000;
auto b = 0b100'0001;

2.3 Function return type deductions

It is needed for example when we have a function template with more than two parameters, and cannot decide the return type of the function.

In C++11, there are two ways: type-trails or auto combination with decltype.

#include <iostream>

template <typename A, typename B>
auto sum(A a, B b) -> decltype(a + b) {
        return a + b;
}

int main(void)
{
        std::cout << typeid(sum(2, 3)).name() << std::endl;
        std::cout << typeid(sum(2.2, 3.3)).name() << std::endl;
        std::cout << typeid(sum(true, false)).name() << std::endl;
        return 0;
}

Since C++14, we can do it simpler, without the trailing return type specifier.

#include <iostream>

template <typename A, typename B>
auto sum(A a, B b) {
        return a + b;
}

int main(void)
{
        std::cout << typeid(sum(2, 3)).name() << std::endl;
        std::cout << typeid(sum(2.2, 3.3)).name() << std::endl;
        std::cout << typeid(sum(true, false)).name() << std::endl;
        return 0;
}

2.4 Generic lambdas

In C++11, lambda function parameters need to be declared- with concrete types.

So, a lambda function summing up two integers would look like:

[](int a, int b) -> int {return a + b;}

If we need to obtain the sum of two floating point values, another lambda expression is needed:

[](double a, double b) -> double {return a + b;}

C++14 relaxes this requirement, allowing parameters of a lambda function to be declared with auto type specifier.

[](auto a, auto b) -> {return a + b;}

The following is an example of generalized lambda to sum up.

#include <iostream>
#include <string>

int main(void)
{
        auto sum = [](auto a, auto b) {
                           return a + b;
                   };
        std::cout << sum(2, 3) << std::endl;
        std::cout << sum(2.2, 3.3) << std::endl;
        std::cout << sum(std::string("22"), std::string("33")) << std::endl;
        return 0;
}

A important application is to enhances algorithms, such as the following example using sort() function.

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

int main(void)
{
        auto greater = [](auto a, auto b) -> bool {
                               return a > b;
                       };

        std::vector<int> vi = {9, 3, 5, 6};
        std::vector<double> vd = {9.9, 3.3, 5.5, 6.6};
        std::vector<std::string> vs = {"nine", "three", "five", "six"};

        sort(vi.begin(), vi.end(), greater);
        sort(vd.begin(), vd.end(), greater);
        sort(vs.begin(), vs.end(), greater);
        return 0;
}

2.5 Generalized lambda captures

In C++11, lambdas can only capture existing object in their scope.

int a = 3;
auto myld = [a](int i){ std::cout << i << "&" << a << std::endl;};

C++14 allows captured members to be initialized with arbitrary expression.

#include <iostream>

int main(void)
{
        int a = 3;
        auto myld = [b = a + 3](int i){
                            std::cout << i << " & " << b << std::endl;
                    };
        myld(9);
        return 0;
}

2.6 Variable templates

In prior versions of C++, only functions, classes or type aliases could be templated. C++14 allows the creation of variables that are templated.

#include <iostream>
#include <iomanip>

template<class T>
constexpr T pi = T(3.1415926535897932385L); //variable template

template<class T>
T circular_area(T r)
{
        return pi<T> * r * r; //pi<T> is a variable template instantiation
}

int main(void)
{
        std::cout << std::setprecision(13);
        std::cout << circular_area(3) << std::endl;
        std::cout << circular_area(3.0f) << std::endl;
        std::cout << circular_area(3.0) << std::endl;
        return 0;
}

2.7 Extended constexpr

C++11 constexpr functions can only contain a single expression that is returned.

C++14 relaxes the restrictions, allowing constexpr functions to contain:

  • local variable declarations
    • not static, thread_local
    • no uninitialized variables
  • mutating objects whose lifetime began with the constant expression evaluation
  • statements such as if, switch, for, while, do-while

    constexpr float exp(float x, int n)
    {
            return n == 0 ? 1 :
                    n % 2 == 0 ? exp(x * x, n / 2) :
                    exp(x * x, (n - 1) / 2) * x;
    }
    

3 C++17

3.1 Nested namespaces

Before C++17 we have to use verbose syntax to declare classes in nested namespaces.

namespace Company {
        namespace Module {
                namespace Part {
                        public class MyClass {
                        };
                }
        }
}

In C++17, it can be simplified.

namespace Company::Module::Part {
        public class MyClass {
        };
}

3.2 Variable declaration in if and switch

C++17 allows to declare variables inside if and switch statements:

if (init; condition)
switch (init; condition)

It is useful when we want the variable not to leak to the enclosing scope.

For something like the following,

const auto it1 = myString.find("foo");
if (it1 != std::string::npos) {
        std::cout << it1 << std::endl;
}
const auto it2 = myString.find("bar");
if (it1 != std::string::npos) {
        std::cout << it2 << std::endl;
}

It can be rewritten with each variable in separate if scope.

if (const auto it = myString.find("foo"); it != std::string::npos)
        std::cout << it1 << std::endl;
if (const auto it = myString.find("bar"); it != std::string::npos)
        std::cout << it2 << std::endl;

3.3 constexpr if statement

C++17 introduces this feature to evaluate an if statement at compile time.

It is useful for template coding.

#include <iostream>
#include <type_traits>
#include <cstring>

template<typename T>
int getLen(T &t)
{
        if constexpr (std::is_same<T, const char *>::value)
                return std::strlen(t);
        else if constexpr (std::is_array<T>::value)
                return std::size(t);
        else
                return 1;
}

int main(void)
{
        const char *s = "hello";
        int a[] = {3, 6, 9};
        int i = 3;
        std::cout << getLen(s) << std::endl;
        std::cout << getLen(a) << std::endl;
        std::cout << getLen(i) << std::endl;
        return 0;
}

In the example, for the three calls to getLen(), compile time predicate is possible which branch the program shall go, so that the compiler can optimize accordingly.

The following is another nice example, where constexpr if is used to define get<N> function, working for structured bindings.

#include <iostream>
#include <string>

struct S {
        int i;
        std::string s;
        float f;
};

template<std::size_t I>
auto& get(S& s)
{
        if constexpr (I == 0)
                return s.i;
        else if constexpr (I == 1)
                return s.s;
        else if constexpr (I == 2)
                return s.f;
}

int main(void)
{
        S obj {3, "hello", 6.9f};
        std::cout << get<0>(obj) << "," << get<2>(obj) << std::endl;
        return 0;
}

Without constexpr if, we will need to have three templates:

template <> auto& get<0>(S &s) { return s.i; }
template <> auto& get<1>(S &s) { return s.s; }
template <> auto& get<2>(S &s) { return s.f; }

3.4 Structured binding declarations

C++17 allows to bind specified names to elements of the initializer.

The following example binds a to the integer 0 and b to "hello" in the type const char *.

auto [a, b] = std::make_pair(3, "hello");

This can simplify the code, for example, when we have multiple returned values from a function. In the following program, std::set::insert returns a std::pair consisting of an iterator and a bool value.

#include <string>
#include <set>
#include <iostream>

int main(void)
{
        std::set<std::string> strs;
        auto [iter, inserted] = strs.insert("hello");

        if (inserted)
                std::cout << "inserted" << std::endl;
        return 0;
}

Without structured binding, we need to declare a std::pair :

std::pair<std::set<std::string>::iterator, bool> p = s.insert(x);
std::set<std::string>::iterator iter = p.first;
bool inserted = p.second;

Or use the magical std::tie :

std::set<std::string>::iterator it;
bool inserted;
std::tie(it, inserted) = strs.insert("hello");

Either way is more verbose.

Structured binding is not limited to tuple like types. It can be used such as binding an array or data members.

3.5 Folding expressions

C++11 provides variadic templates to work with variable number of input arguments.

#include <iostream>

auto sum()
{
        return 0;
}

//C++11 variadic template
template<typename T1, typename... T>
auto sum(T1 s, T... ts)
{
        return s + sum(ts...);
}

int main(void)
{
        std::cout << sum(1, 3, 6, 9, 19) << std::endl;
        return 0;
}

Folding expressions in C++17 are new ways to unpack vaiadic parameters.

  1. ( pack op … )
  2. ( … op pack )
  3. ( pack op … op init )
  4. ( init op … op pack )

The example can be simplified as following.

#include <iostream>

template<typename... T>
auto sum(T... ts)
{
        return (ts + ...);
}

int main(void)
{
        std::cout << sum(1, 3, 6, 9, 19) << std::endl;
        return 0;
}

4 C++20

4.1 Immediate functions

An immediate function is a consteval function. But different from C++11 constexpr functions that can be evaluated either at compile time or runtime, consteval functions must be evaluated at compile time.

#include <iostream>

consteval int sum(int const a, int const b)
{
        return a + b;
}

int main(void)
{
        constexpr int c = sum(2, 5);
        std::cout << c << std::endl;

        int x = 3, y = 6;
        const int z = sum(x, y);
        std::cout << z << std::endl;
        return 0;
}

4.2 Abbreviated function templates

C++20 abbreviated function templates mean the same to generic functions, using auto in parameters instead of verbose template syntax.

The following function template

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

in C++20 can be written as

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

It is actually an unconstrained abbreviated function template, meaning no constraints are specified on the arguments. However, constraints can be specified, such as the following example:

auto sum(std::integral auto a, std::integral auto b)
{
        return a + b;
}

is a constrained abbreviated function template - an abbreviation to the following:

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

4.3 Lambda templates

With the C++14 generic lambda

auto sum = [](auto a, auto b) {return a + b;};

The compiler generates objects like:

struct _lambda_1 {
        template<typename T, typename U>
        inline auto operator()(T t, U u) {
                return t + u;
        }
} sum;

It would be problematic in case the arguments are in the same type. So, C++20 introduces lambda templates, allowing to define generic lambdas using template:

template<template_parameter_list>
concept concept_name = constraint_expression;

4.4 Modules

A module is a self-contained unit of code that can be imported into other translation units. Modules can caontain declarations, definations, and other code.

Modules provide a new way to organize code that is more flexible than tranditional header system. They can be compiled separately, which allows faster build and better sparation of concerns.

import <iostream>;

int main(void)
{
        std::cout << "Hello modules" << std::endl;
        return 0;
}

4.5 Concepts

For the following template to print

#include <iostream>
#include <vector>

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

int main(void)
{
        print(3);
        print('c');
        print("str");

        std::vector<int> v{2, 3, 6};
        //print(v); //error!
        return 0;
}

If we try to print something that is not supported, such as a vector, there will be verbose error messages. It is because std::vector<T> does not provide and overloaded operator<<.

C++20 concepts are provided to help. They are used to perform compile time validation of template arguments, in the form:

template <template-parameter-list>
concept concept-name = constraint-expression;

The following example we define a Printable concept with proper requires clause and impose the constaint on the print method.

#include <iostream>
#include <vector>

template<typename T>
concept Printable = requires(std::ostream& os, const T& msg)
{
        {os << msg};
};

template <Printable T>
void print(const T& msg)
{
        std::cout << msg;
}

int main(void)
{
        print(3);
        print('c');
        print("str");

        std::vector<int> v{2, 3, 6};
        print(v); //error!
        return 0;
}

Now compile the program, the error messages will be clearer - there is a constraint on type T which must satisfy the Printable concept that requires T to provide an interface for std::ostream.

concept.cpp:23:2: error: no matching function for call to 'print'
print(v); //error!
^~~~~
concept.cpp:11:6: note: candidate template ignored: constraints not satisfied [with T = std::vector<int, std::allocator<int> >]
void print(const T& msg)
^
concept.cpp:10:11: note: because 'std::vector<int, std::allocator<int> >' does not satisfy 'Printable'
template <Printable T>
^
concept.cpp:7:6: note: because 'os << msg' would be invalid: invalid operands to binary expression ('std::ostream' (aka 'basic_ostream<char>') and 'const std::vector<int, std::allocator<int> >')
        {os <<EOF }
 msg};
            ^
1 error generated.

Concepts allow people to express in code what used to be in documentation about the requirements for a template argument. They also serve as a far more expressive way to use SFINAE.

4.6 Ranges

Range is concepttually the iterators begin and end. It provides a new way to write algorithms instead of using verbose syntax of STL begin and end iterators.

So the following sample:

std::sort(vec.begin(), vec.end());

can be simplied:

std::range::sort(vec);

So, for the following regular STL example,

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

int main(void)
{
        std::vector<int> v(30), even;

        std::iota(v.begin(), v.end(), 1);
        std::transform(v.begin(), v.end(), v.begin(),
                [](int i) {return i * i;} );
        std::copy_if(v.begin(), v.end(), std::back_inserter(even),
                [](int i) {return 0 == i % 2;} );
        for (int i = 0; i < 3; ++i)
                std::cout << even[i] << ' ';
        std::cout << std::endl;
        return 0;
}

It creates a list of numbers, squares the numbers, copy even numbers to another list called even, and prints the first three numbers. We may rewrite with ranges.

#include <iostream>
#include <ranges>

int main(void)
{
        for (int n : std::views::iota(1)
                   | std::views::transform( [](int i) {return i * i;} )
                   | std::views::filter( [](int i) {return 0 == i % 2;} )
                   | std::views::take(3))
        {
                std::cout << n << ' ';
        }
        std::cout << std::endl;
        return 0;
}

The second program is clearly easier to read.

4.7 Coroutines

Coroutines are beneficial to implement in synchronous programming, and require less resource than threads. Useful for the following:

  • State machines within a single subroutine
  • Actor model of concurrency
  • Generators
  • Communication sequential processes
  • Reverse communication

Unlike a function that gets called one time and returns at one point, a coroutine can be suspended and resumed before its final return.

A coroutine would have keywords

  • co_return to complete the execution and optionally final return a value
  • co_yield to suspend the execution and return a value
  • co_await to suspend the execution until resumed

The following is the most simple coroutine that returns directly.

#include <coroutine>

struct RetObj {
        struct promise_type {
                RetObj get_return_object() { return {}; }
                std::suspend_never initial_suspend() { return {}; }
                std::suspend_never final_suspend() noexcept { return {}; }
                void return_void() {}
                void unhandled_exception() {}
        };
};

RetObj myCoroutine() {
        co_return;
}

int main() {
        myCoroutine();
}

A valid coroutine return signature must be a class or struct with nested type promise_type including the member functions:

  • get_return_object to return the same as outer scope RegObj
  • initial_suspend to return an awaitable object
  • final_suspend to return an awaitable object
  • unhandled_exception to handle the exception if any

The promise is responsible for controlling co_return and co_yield behaviors with methods including return_void, return_value, and yeild_value. In the example, we use return_void for the coroutine returning directly.

Now let's create a slightly more complex example.

#include <iostream>
#include <coroutine>

struct RetObj {
        struct promise_type {
                RetObj get_return_object() { return {}; }
                std::suspend_never initial_suspend() { return {}; }
                std::suspend_never final_suspend() noexcept { return {}; }
                void unhandled_exception() {}
        };
};

struct Awaiter {
        std::coroutine_handle<> *hp;
        constexpr bool await_ready() const noexcept { return false; }
        void await_suspend(std::coroutine_handle<> h) { *hp = h; }
        constexpr void await_resume() const noexcept {}
};

RetObj myCoroutine(std::coroutine_handle<> *h)
{
        Awaiter a{h};
        for (int i = 0; ; ++i) {
                co_await a;
                std::cout << "Coroutine: " << i << std::endl;
        }
}

int main(void)
{
        std::coroutine_handle<> h;
        myCoroutine(&h);
        for (int i = 0; i < 3; ++i) {
                std::cout << "Main: " << i << std::endl;
                h();
        }
        h.destroy();
}

Instead of returning, this coroutine suspends and waits to be resumed.

When evaluating the expression co_await a, the compiler creates a coroutine handle and passes it to the method a.await_suspend. The coroutine handle is a callable object that, when called will resume the coroutine at the point following the co_awiat expression.

a can be either an awaitable (that supports co_awiat operator) or awaiter object. Here we use an awaiter object - defining how the coroutine will behave, when being suspended or resumed. Three special methods must be provided:

  • await_ready returns a boolean value indicating if to suspend or not (false means to suspend).
  • await_suspend is to be called when the coroutine is suspended, with the coroutine's handle.
  • await_resume is to be called when the coroutine is resumed, and its result is the result of the whole co_await expression.

The coroutine handle i.e. std::coroutine_handle can be used to resume the execution of the coroutine, destroy the coroutine frame, or check its a lifetime.

In the example, myCoroutine always counts and prints the incrementing integer. With the co_awiat expression, myCoroutine suspends giving the control to main. Then, the coroutine handle is invoke to resume the execution of myCoroutine. The variable i maintains its value even when myCoroutine is not in control.

Output:

Main: 0
Coroutine: 0
Main: 1
Coroutine: 1
Main: 2
Coroutine: 2

5 references

Author: TPECWL2089XD

Created: 2023-01-02 Mon 15:26

Validate