DEV Community: Vishal Chovatiya

C++20 Coroutine: Under The Hood

Vishal Chovatiya — Mon, 10 May 2021 03:39:18 +0000

A coroutine is one of the major feature introduced with the C++20 standard apart from Module, Ranges & Concept. And you see how happy I am to unfold it. I already set the baseline on this topic with my previous article that Coroutine in C Language, where we saw, how suspension-resumption of execution works! With this article "C++20 Coroutine: Under The Hood", we will see how compiler creates magic & standard library helps it with basic infrastructure making C++20 coroutine more sophisticated(yet complex) & scalable/customizable.

/!\: This article has been originally published on my blog.

At any point, you feel there is some jargons/terminology that is not known to you. Please keep reading forward. I have added a special section for it.

What Is Coroutine In General?

Please refer my previous article Coroutine in C Language for more.

What Is C++20 Coroutine?

A function that
1. Contains keywords co_await, co_yield and/or co_return.
2. Use a return type specifying a promise.
From the higher abstraction, the C++20 coroutine consists of:
1. Promise
  - Defines overall coroutine behaviour.
  - Act as a communicator between caller & called coroutine.
2. Awaiter
  - Controls suspension & resumption behaviour.
3. Coroutine handle
  - Controls execution behaviour.

Why Do You Even Need Coroutine?

I have already covered this in my earlier post Coroutine in C Language.
However, if you still want to understand the need for coroutine with use case then please refer to Iterator Design Pattern With Modern C++.
Or you can directly see the section of this article Generating Integer Sequence Using Coroutine.

Understanding C++20 Coroutine With Examples

Enough theory. Let's talk code.

Suspending a Coroutine

Following is a lame & minimal example of a C++20 Coroutine. But the very good starting point for beginner with slow pace & less cluttered code.

#include <coroutine>
#include <iostream>

struct HelloWorldCoro {
    struct promise_type { // compiler looks for `promise_type`
        HelloWorldCoro get_return_object() { return this; }    
        std::suspend_always initial_suspend() { return {}; }        
        std::suspend_always final_suspend() { return {}; }
    };

    HelloWorldCoro(promise_type* p) : m_handle(std::coroutine_handle<promise_type>::from_promise(*p)) {}
    ~HelloWorldCoro() { m_handle.destroy(); }

    std::coroutine_handle<promise_type>      m_handle;
};

HelloWorldCoro print_hello_world() {
    std::cout << "Hello ";
    co_await std::suspend_always{};
    std::cout << "World!" << std::endl;
}

int main() {
    HelloWorldCoro mycoro = print_hello_world();

    mycoro.m_handle.resume();
    mycoro.m_handle(); // Equal to mycoro.m_handle.resume();
    return EXIT_SUCCESS;
}
// g++-10 -std=c++20 -fcoroutines -fno-exceptions -o myapp Main.cpp

A coroutine can be resumed by a resume member function of the std::coroutine_handle or by invoking the function call operator of the std::coroutine_handle object.
As I have mentioned earlier, the C++20 coroutine consists of:
1. Promise i.e. promise_type
  - Type containing special methods like get_return_object(), initial_suspend(), final_suspend(), etc. that compiler use in coroutine transformation. Hence, it controls overall coroutine behaviour.
2. Awaiter i.e. std::suspend_always
  1. Empty class to suspend coroutine always.
  2. You can see the GCC implementation for this type here.
3. Coroutine handle i.e. std::coroutine_handle
  - Handler for coroutine that used to resume, destroy or check on a lifetime of coroutine.
The compiler transforms the above print_hello_world coroutine as :

HelloWorldCoro print_hello_world() {
    __HelloWorldCoro_ctx* __context = new __HelloWorldCoro_ctx{};
    auto __return = __context->_promise.get_return_object();
    co_await __context->_promise.initial_suspend();

    std::cout << "Hello ";
    co_await std::suspend_always{ };
    std::cout << "World!" << std::endl;

__final_suspend_label:
    co_await __context->_promise.final_suspend();
    delete __context;
    return __return;
}

As you can see, the compiler first creates the context(i.e. coroutine state) object. Which presumably look like:

struct __HelloWorldCoro_ctx {
    HelloWorldCoro::promise_type _promise;
    // storage for argument passed to coroutine
    // storage for local variables
    // storage for representation of the current suspension point
};

// Standard doesn't define such type, rather compilers choose the type that suits its implementation.

As seen, with the help of this context object, it creates the HelloWorldCoro object named as __return with the help of promise's method get_return_object().
Finally, one more level of transformation of co_await statements, coroutine would look like:

HelloWorldCoro print_hello_world() {
    __HelloWorldCoro_ctx* __context = new __HelloWorldCoro_ctx{};
    auto __return = __context->_promise.get_return_object();
    {
        auto&& awaiter = std::suspend_always{};
        if (!awaiter.await_ready()) {
            awaiter.await_suspend(std::coroutine_handle<> p); 
            // compiler added suspend/resume hook
        }
        awaiter.await_resume();
    }

    std::cout << "Hello ";
    {
        auto&& awaiter = std::suspend_always{};
        if (!awaiter.await_ready()) {
            awaiter.await_suspend(std::coroutine_handle<> p); 
            // compiler added suspend/resume hook
        }
        awaiter.await_resume();
    }
    std::cout << "World!" << std::endl;

__final_suspend_label:
    {
        auto&& awaiter = std::suspend_always{};
        if (!awaiter.await_ready()) {
            awaiter.await_suspend(std::coroutine_handle<> p); 
            // compiler added suspend/resume hook
        }
        awaiter.await_resume();
    }
    return __return;
}

As you can see our HelloWorldCoro::promise_type::initial_suspend()\ & HelloWorldCoro::promise_type::final_suspend() returns std::suspend_always.
Whose, method std::suspend_always::await_ready() in turn returns false always.
So our coroutine will be suspended every time it encounters co_await.

Returning a Value From Coroutine

#include <coroutine>
#include <iostream>
#include <cassert>

struct HelloWorldCoro {
    struct promise_type {
        int m_value;

        HelloWorldCoro get_return_object() { return this; }
        std::suspend_always initial_suspend() { return {}; }
        std::suspend_always final_suspend() { return {}; }

        void return_value(int val) { m_value = val; }
    };

    HelloWorldCoro(promise_type* p) : m_handle(std::coroutine_handle<promise_type>::from_promise(*p)) {}
    ~HelloWorldCoro() { m_handle.destroy(); }

    std::coroutine_handle<promise_type>      m_handle;
};

HelloWorldCoro print_hello_world() {
    std::cout << "Hello ";
    co_await std::suspend_always{ };
    std::cout << "World!" << std::endl;

    co_return -1;
}


int main() {
    HelloWorldCoro mycoro = print_hello_world();

    mycoro.m_handle.resume();
    mycoro.m_handle.resume();
    assert(mycoro.m_handle.promise().m_value == -1);
    return EXIT_SUCCESS;
}

To return a value from a coroutine, you need to supply return_value() method to promise type. In other words, the compiler expects the method named return_value with appropriate argument.
And, if you don't supply it to promise type, you will be prompted with the below error:

Main.cpp:27:5: error: no member named ‘return_value’ in ‘std::__n4861::__coroutine_traits_impl<HelloWorldCoro, void>::promise_type’ {aka ‘HelloWorldCoro::promise_type’}
    27 |     co_return -1;
       |     ^~~~~~~~~

This return_value() method is then used by compiler to transform the co_return statement as below:

HelloWorldCoro print_hello_world() {
    __HelloWorldCoro_ctx* __context = new __HelloWorldCoro_ctx{};
    auto __return = __context->_promise.get_return_object();
    co_await __context->_promise.initial_suspend();

    std::cout << "Hello ";
    co_await std::suspend_always{ };
    std::cout << "World!" << std::endl;

    __context->_promise.return_value(-1);
    goto __final_suspend_label;

__final_suspend_label:
    co_await __context->_promise.final_suspend();
    delete __context;
    return __return;
}

As you might have noticed, co_return transformation is plain vanilla, where the compiler just passes the return value to the promise object & jump to the final suspend label.
I will not expand the co_await statements again. Otherwise, the code will become messy. But, by now, you can guess what could be there.

Yielding a Value From Coroutine

#include <coroutine>
#include <iostream>
#include <cassert>

struct HelloWorldCoro {
    struct promise_type {
        int m_val;

        HelloWorldCoro get_return_object() { return this; } 
        std::suspend_always initial_suspend() { return {}; } 
        std::suspend_always final_suspend() { return {}; } 

        std::suspend_always yield_value(int val) {
            m_val = val; 
            return {};
        }
    };

    HelloWorldCoro(promise_type* p) : m_handle(std::coroutine_handle<promise_type>::from_promise(*p)) {}
    ~HelloWorldCoro() { m_handle.destroy(); }

    std::coroutine_handle<promise_type>      m_handle;
};

HelloWorldCoro print_hello_world() {
    std::cout << "Hello ";
    co_yield 1;
    std::cout << "World!" << std::endl;
}

int main() {
    HelloWorldCoro mycoro = print_hello_world();

    mycoro.m_handle.resume();
    assert(mycoro.m_handle.promise().m_val == 1);
    mycoro.m_handle.resume();
    return EXIT_SUCCESS;
}

As we have done in returning a value from a coroutine, to yield anything from coroutine you need to supply the yield_value() method to promise_type that returns awaitable type.
Once again, the compiler transforms the coroutine that yields as:

HelloWorldCoro print_hello_world() {
    __HelloWorldCoro_ctx* __context = new __HelloWorldCoro_ctx{};
    auto __return = __context->_promise.get_return_object();
    co_await __context->_promise.initial_suspend();

    std::cout << "Hello ";
    co_await __context->_promise.yield_value(1);
    std::cout << "World!" << std::endl;

__final_suspend_label:
    co_await __context->_promise.final_suspend();
    delete __context;
    return __return;
}

As you can see co_yield statement transformed into co_await considering the promise's method(i.e. yield_value()) call as expression. That returns std::suspend_always so our coroutine will be suspended thereafter yielding a value.

Generating Integer Sequence Using C++20 Coroutine

So, that we understood the compiler transformations of coroutine, let's do something meaningful with coroutine.

#include <coroutine>
#include <iostream>
#include <cassert>

struct Generator {
    struct promise_type {
        int m_val;

        Generator get_return_object() { return this; }
        std::suspend_never initial_suspend() { return {}; }
        std::suspend_always final_suspend() { return {}; }

        std::suspend_always yield_value(int val) {
            m_val = val; 
            return {};
        }
    };

    /* ---------------------------- Iterator Implementation ----------------------------- */
    struct iterator {
        bool operator!=(const iterator& rhs) { return not m_h_ptr->done(); }
        iterator& operator++() { 
            m_h_ptr->resume(); 
            return *this; 
        }
        int operator*() { return m_h_ptr->promise().m_val; }

        std::coroutine_handle<promise_type> *m_h_ptr;
    };

    iterator begin() { return iterator{&m_handle}; }
    iterator end() { return iterator{nullptr}; }
    /* ---------------------------------------------------------------------------------- */

    Generator(promise_type* p) : m_handle(std::coroutine_handle<promise_type>::from_promise(*p)) {}
    ~Generator() { m_handle.destroy(); }

    std::coroutine_handle<promise_type>      m_handle;
};


Generator range(uint32_t start, uint32_t end) {
    while(start != end)
        co_yield start++;
}

int main() {
    for (auto &&no : range(0, 10)) {  // Isn't this look like Python !
        std::cout<< no <<std::endl;
    }
    return EXIT_SUCCESS;
}

A range() function of the above code will generate the integers on every iteration on a need basis. Instead of generating & returning precomputed sequence.
For the rest of the code, I suggest you spend some time with patience. And play around it.
And, If you are thinking that why do we need iterator implementation inside Generator, then please learn How Range Based for Loop Works In C++!.

C++20 Coroutine Terminology

This section should have been at beginning of the article. However, I believe that until you understand how coroutine works under the hood, you won't be able to connect the dots on C++20 coroutine jargons( or won't understand data type naming convention).
By this time you are able to write a C++ coroutine & you can ignore this section. But it is just that you will have a hard time communicating with fellow C++ developers & reading cppreference. If you do so.

Awaitable

A type that supports the co_await operator is called an Awaitable type.
C++20 introduced a new unary operator co_await that can be applied to an expression. For example:

struct dummy { // Awaitable
    std::suspend_always operator co_await(){ return {}; }
};

HelloWorldCoro print_hello_world() {
    std::cout << "Hello ";
    co_await dummy{}; 
    std::cout << "World!" << std::endl;
}

Awaiter

struct my_awaiter {
    bool await_ready() { return false; } 
    void await_suspend(std::coroutine_handle<>) {} 
    void await_resume() {}
};

HelloWorldCoro print_hello_world() {
    std::cout << "Hello ";
    co_await my_awaiter{};
    std::cout << "World!" << std::endl;
}

An Awaiter type is a type that implements the three special methods that are called as part of a co_await expression: await_ready(), await_suspend() and await_resume(). For example, standard library defined trivial awaiters i.e. std::suspend_always & std::suspend_never.
Note that a type can be both an Awaitable type and an Awaiter type.

`co_await`

co_await is a unary operator that suspends a coroutine and returns control to the caller. Its operand is an expression whose type must either define operator co_await, or Awaitable.

struct dummy { }; // Awaitable

struct HelloWorldCoro {
    struct promise_type {
        // . . .
        auto await_transform(const dummy&) {
            return std::suspend_always{};
        }
    };
    // . . .
};

HelloWorldCoro print_hello_world() {
    std::cout << "Hello ";
    co_await dummy{}; 
    std::cout << "World!" << std::endl;
}

Promise

A type strictly named as promise_type.
The promise object is used inside the coroutine. The coroutine submits its result or exception through this object.
The promise type is determined by the compiler from the return type of the coroutine using std::coroutine_traits.

Coroutine Handle

The coroutine handle used to resume the execution of the coroutine or to destroy the coroutine frame. It does also indicates the status of coroutine using std::coroutine_handle::done() method.

Coroutine State

The coroutine state(referred to as a context object) is a compiler-generated, heap-allocated (unless the allocation is optimized out) object that contains
- Promise object.
- Parameters (all copied by value).
- Local variables.
- Representation of the current suspension point, so that resume knows where to continue and destroy knows what local variables were in scope.

How Does Coroutine Gets Executed!

Ahh...! it's time for the real magic!
Now, that we saw how the compiler does the magic with coroutine keywords co_await, co_yield & co_return. Let's understand how it gets executed.
But, Before, we move forward, let me clarify some points:
- C++ Standard doesn't bother about implementation rather it only stats behaviour. Hence implementation of the coroutine is completely dependent on the compiler & library writers. To see that, you can check the library implementation of std::coroutine_handle::resume() that uses __builtin_coro_resume which is provided by the GCC compiler. Proving that the library & compiler is tightly coupled.
- With that being said, I have not written any C++ library or compiler in my career. Though I have written/ported the core C library for proprietary architecture. So, whatever you see in this section is just to build your intuition on how coroutine can be implemented. Based on my research & intuition.
There are two ways I can see this can be done:

Hypothesis 1

For example, If you have defined your coroutine as:

HelloWorldCoro print_hello_world(int a) {
    int b = 10;
    co_await std::suspend_always{};
    a = 10;
    int c = 10;
    co_await std::suspend_always{};
    co_return a + b + c;
}

Then, operations can be divided into 3 different sections separated by 2 suspension-point(i.e. co_await <expr>) as
1. int b = 10;
2. a = 10; int c = 10;
3. co_return a + b + c;
Considering these suspension points, then the compiler basically
- Rewrite your coroutine into a bit like functions.
- And create a copy of all local variables as a data member of the coroutine state object.
You can assume coroutine state object layout as:

struct print_hello_world {

    print_hello_world(int a_) : a{a}{} // Coroutine state object with coroutine arguments

    void _s1(){ // Before suspension point 1 operations
        int b = 10;

        sp = 1; // switching call back based on suspension point
    } 

    void _s2(){ // Operations b/w suspension point 1 & 2 
        a = 10;
        int c = 10;

        sp = 2;
    } 

    void _s3(){ // Operations after suspension point 2 
        promise.return_value(a + b + c);  // After execution, coro_done = true;

        coro_done = true;
    } 

    int a, b, c; // Local variables

    promise_type& promise;

    void (*s_cb)[] = {_s1, _s2, _s3}; // suspension point callbacks 
    int sp{0}; // current suspension point(sp)
    bool coro_done{false};
};

Now, when you call coroutine, you are basically creating a coroutine state object with a similar argument to that of coroutine.

auto mycoro = print_hello_world(5);

// transform into

print_hello_world    mycoro(5);

As you might have guessed, due to rewriting coroutine into tiny functions, we don't need a suspension mechanism anymore. And resumption can be implemented as:

void std::coroutine_handle::resume() { 
    if(not print_hello_world::coro_done)
        print_hello_world::s_cb[sp]();
}

So, when you call resume you are basically calling the suspension-point specific tiny function(technically its method) from a coroutine state object. That implies the creation of two stack frame i.e. std::coroutine_handle::resume() & print_hello_world::_sX(), where X stands for a suspension point number. Consequently not needing a separate stack & using the same stack as the caller. And this is why C++20 coroutines are stackless coroutine & faster.
I agree that the above example is not compilable, don't cover edge cases & doesn't consider customized(i.e. awaiter object) coroutine behaviour. But, with the intuition we just built, you can easily create a mental model of coroutine & see the compiler perspective.
And to test your intuition capability, just imagine How you can create tiny functions for the coroutine that contains co_await expression in a for loop?

Hypothesis 2

Another usual way you can implement suspension-resumption is with the help of context switching APIs. For example, in the expansion of co_wait <expr> statement, I have mentioned the comment "compiler added suspend/resume hook" as below.

{
    auto&& awaiter = std::suspend_always{};
    if (!awaiter.await_ready()) {
        awaiter.await_suspend(std::coroutine_handle<> p); 
        // compiler added suspend/resume hook
    }
    awaiter.await_resume();
}

This is the place where your compiler adds its secret sauce to your code with context switching APIs. And rest is I think easy to imagine if you have read my earlier post Coroutine in C Language thoroughly.

Summary

Subroutine vs Coroutine

	Subroutines	Coroutines
call	calling convention i.e. foo()	calling convention i.e. foo()
suspend	Can't suspend	co_await/co_yield expression
resume	Can't suspend	coroutine_handle<>::resume()
return	return statement	co_return statement

Compiler Transformation Of Coroutine Related Keywords

co_return x;

// transforms into

__promise.return_value(x);
goto __final_suspend_label;

co_await y;

// transforms into

auto&& __awaitable = y;
if (__awaitable.await_ready()) {
    __awaitable.await_suspend();
    // ...suspend/resume point...
}
__awaitable.await_resume();

co_yield z;

// transforms into

co_await __promise.yield_value(z);

Parting Words With FAQs

This is not just it, there are still many things that we haven't explored like exception handling, coroutine calling coroutine, etc.
One unusual thing I observed about C++20 Coroutine is, You have to specify the return type even if you don't return anything from the coroutine. IMO, this coroutine looks unusual & counter-intuitive.

What does it mean by stackfull & stackless coroutine?

-- stackfull coroutines need a separate stack to be executed.
-- stackless coroutine uses the same stack as of caller.

Difference between threads & coroutines?

-- Coroutines are about your programming model and threads are about your execution model.
-- co-routine can still do concurrency without scheduler overhead -- it simply manages the context-switching itself.
-- Another benefit is the much lower memory usage. With the threaded model, each thread needs to allocate its own stack, and so your memory usage grows linearly with the number of threads you have.

What does it mean by "coroutines are like lightweight threads"?

-- First of all, coroutines & threads are a different entity. Because coroutine can be stackless & doesn't need OS intervention on schedule, it is lower on memory footprint & faster on execution as compared to thread. With C++, it's, even more, faster if you use Hypothesis 1.

How come C++ coroutine are stackless?

-- This is already answered in Hypothesis 1. Still one more time.
-- The compiler "returns" a handle to this dynamically allocated coroutine frame to the caller of the coroutine.
-- When a caller calls std::coroutine_handle::resume() method, stackframe for std::coroutine_handle::resume() will be created which resumes the coroutine while processing all coroutine data on a dynamically allocated coroutine frame.
-- And this is how coroutine is stackless in C++. Because it executes in the current stack only. Instead of a separate coroutine stack.

Implementation of Coroutine in C Language

Vishal Chovatiya — Mon, 26 Apr 2021 03:03:17 +0000

It’s been quite a while that I haven’t published anything on my blog. But that’s due to the job change. I hope you understand that it has never been easy to re-settle in a new environment with new people while maintaining a steep technical learning curve. It takes time to tune yourself accordingly. Anyways, I wrote on “Coroutine in C Language” as a pre-pend to my upcoming post on C++20 Coroutine. Today we will see “How Coroutine Works Internally?”.

/!\: This article has been originally published on my blog. If you are interested in receiving my latest articles, please sign up to my newsletter.

Prerequisites

If you are an absolute beginner, then only go through below pre-requisites. And if you are not a beginner, you better know what to skip!

Coroutine Basics

What Is Coroutine?

Coroutine is a function/sub-routine(co-operative sub-routine to be precise) that can be suspended and resumed.
In other words, You can think of coroutine as the in-between solution of normal function & thread. Because, once function/sub-routine called, it executes till the end. On other hand, the thread can be blocked by synchronization primitives(like mutex, semaphores, etc) or suspended by OS scheduler. But again you can not decide on suspension & resumption on it. As it is done by the OS scheduler.
While coroutine on the other hands, can be suspended on a pre-defined point & resumed later on a need basis by the programmer. So here programmer will be having complete control of execution flow. That too with minimal overhead as compared to thread.
Coroutine is also known as native threads, fibres (in windows), lightweight threads, green threads(in java), etc.

Why Do We Need Coroutine?

As I usually do, before learning anything new, you should be asking this question to yourself. But, let me answer it:
Coroutines can provide a very high level of concurrency with very little overhead. As it doesn't need OS intervention in scheduling. While in a threaded environment, you have to bear the OS scheduling overhead.
A coroutine can suspend on pre-determined points, so you can also avoid locking on shared data structures. Because you would never tell your code to switch to another coroutine in the middle of a critical section.
With the threads, each thread needs its own stack with thread local storage & other things. So your memory usage grows linearly with the number of threads you have. While with co-routines, the number of routines you have doesn't have a direct relationship with your memory usage.
For most use cases coroutine is a more optimal choice as it is faster as compared to thread.
And if you are still not convinced then wait for my C++ Coroutine post.

To-the-point Context Switching API Theory

Before we dive into a coroutine, we need to understand the below foundation functions/APIs for context switching. Off-course, as we do, with less, to-the-point theory & with more code examples.
1. setcontext
2. getcontext
3. makecontext
4. swapcontext
If you are already familiar with setjmp/longjmp, then you might have ease in understanding these functions. You can consider these functions as an advanced version of setjmp/longjmp.
The only difference is setjmp/longjmp allows only a single non-local jump up the stack. Whereas, these APIs allows the creation of multiple cooperative threads of control, each with its own stack or entry point.

Data Strucutre To Store Execution Context

ucontext_t type structure that defined as below is used to store the execution context.
All four(setcontext, getcontext, makecontext & swapcontext) control flow functions operates on this structure.

typedef struct {
    ucontext_t *uc_link;    
    stack_t     uc_stack;
    mcontext_t  uc_mcontext;
    sigset_t    uc_sigmask;
    ...
} ucontext_t;

uc_link points to the context which will be resumed when the current context exits, if the context was created with makecontext (a secondary context).
uc_stack is the stack used by the context.
uc_mcontext stores execution state, including all registers and CPU flags, frame/base pointer(i.e. inidicates current execution frame), instruction pointer(i.e. program counter), link register(i.e. stores return address) and the stack pointer(i.e. inidicates current stack limit or end of current frame). mcontext_t is an opaque type.
uc_sigmask is used to store the set of signals blocked in the context. Which isn't the focus for today.

`int setcontext(const ucontext_t *ucp)`

This function transfers control to the context in ucp. Execution continues from the point at which the context was stored in ucp. setcontext does not return.

`int getcontext(ucontext_t *ucp)`

Saves current context into ucp. This function returns in two possible cases:
1. after the initial call,
2. or when a thread switches to the context in ucp via setcontext or swapcontext.
The getcontext function does not provide a return value to distinguish the cases (its return value is used solely to signal error), so the programmer must use an explicit flag variable, which must not be a register variable and must be declared volatile to avoid constant propagation or other compiler optimisations.

`void makecontext(ucontext_t ucp, void (func)(), int argc, ...)`

The makecontext function sets up an alternate thread of control in ucp , which has previously been initialised using getcontext.
The ucp.uc_stack member should be pointed to an appropriately sized stack; the constant SIGSTKSZ or MINSIGSTKSZ is commonly used.
When ucp is jumped to using setcontext or swapcontext, execution will begin at the entry point to the function pointed to by func, with argc arguments as specified. When func terminates, control is returned to context specified in ucp.uc_link.

`int swapcontext(ucontext_t oucp, ucontext_t ucp)`

Saves the current execution state into oucp and then transfers the execution control to ucp.

[Example 1]: Understanding Context Switching With `setcontext` & `getcontext` Functions

Now, that we have read lot of theory. Let's create meaningful out of it.
Consider the below program that implements plain infinite loop printing "Hello world" every second.

#include <stdio.h>
#include <ucontext.h>
#include <unistd.h>
#include <stdlib.h>

int main( ) {
    ucontext_t ctx = {0};

    getcontext(&ctx);   // Loop start
    puts("Hello world");
    sleep(1);
    setcontext(&ctx);   // Loop end 

    return EXIT_SUCCESS;
}

Here, getcontext is returning with both possible cases as we have mentioned earlier i.e.:
1. after the initial call,
2. when a thread switches to the context via setcontext.
Rest is I think self-explanatory.

[Example 2]: Understanding Control Flow With `makecontext` & `swapcontext` Functions

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <signal.h>
#include <ucontext.h>

void assign(uint32_t *var, uint32_t val) { 
    *var = val; 
}

int main( ) {
    uint32_t var = 0;
    ucontext_t ctx = {0}, back = {0};

    getcontext(&ctx);

    ctx.uc_stack.ss_sp = calloc(1, MINSIGSTKSZ);
    ctx.uc_stack.ss_size = MINSIGSTKSZ;
    ctx.uc_stack.ss_flags = 0;

    ctx.uc_link = &back; // Will get back to main as `swapcontext` call will populate `back` with current context
    // ctx.uc_link = 0;  // Will exit directly after `swapcontext` call

    makecontext(&ctx, (void (*)())assign, 2, &var, 100);
    swapcontext(&back, &ctx);    // Calling `assign` by switching context

    printf("var = %d\n", var);

    return EXIT_SUCCESS;
}

Here, the makecontext function sets up an alternate thread of control in ctx. And when jump made with ctx by using swapcontext, execution will begin at assign, with respective arguments as specified.
When assign terminates, control will be switch to ctx.uc_link. Which is pointing to back & will be populated by swapcontext before jump/context-switch.
If the ctx.uc_link is made to 0, then current execution context is considered as the main context, and the thread will exit when assign context gets over.
Before a call is made to makecontext, the application/developer needs to ensure that the context being modified has a pre-allocated stack. And argc matches the number of arguments of type int passed to func. Otherwise, the behavior is undefined.

Coroutine in C Language

Initially, I have created single file example. But then I realised It will be too much to stuff into the single file. Hence, I splited implementation & usage example into different file which will make the example more comprehensible & easy to understand. ## Coroutine Implementation
So, here is the simplest coroutine in c language:

`coroutine.h`

#pragma once

#include <stdint.h>
#include <stdlib.h>
#include <ucontext.h>
#include <stdbool.h>

typedef struct coro_t_ coro_t;
typedef int (*coro_function_t)(coro_t *coro);

/* 
    Coroutine handler
*/
struct coro_t_ {
    coro_function_t     function;           // Actual co-routine function
    ucontext_t          suspend_context;    // Stores context previous to coroutine jump
    ucontext_t          resume_context;     // Stores coroutine context
    int                 yield_value;        // Coroutine return/yield value
    bool                is_coro_finished;   // To indicate the current coroutine status
};

/* 
    Coroutine APIs for users
*/
coro_t *coro_new(coro_function_t function);
int coro_resume(coro_t *coro);    
void coro_yield(coro_t *coro, int value);
void coro_free(coro_t *coro);

Just ignore the coroutine APIs as of now.
The main thing to focus here is coroutine handler that has following field
- function : That holds the address of actual coroutine function supplied by user.
- suspend_context : That used to suspend the coroutine function.
- resume_context : That holds the context of actual coroutine function.
- yield_value: To store the return value between intermediate suspension point & also final return value.
- is_coro_finished : An indicator to check status on coroutine lifetime.

`coroutine.c`

#include <signal.h>
#include "coroutine.h"

static void _coro_entry_point(coro_t *coro) {
    int return_value = coro->function(coro);
    coro->is_coro_finished = true;
    coro_yield(coro, return_value);
}

coro_t *coro_new(coro_function_t function) {
    coro_t *coro = calloc(1, sizeof(*coro));

    coro->is_coro_finished = false;
    coro->function = function;
    coro->resume_context.uc_stack.ss_sp = calloc(1, MINSIGSTKSZ);
    coro->resume_context.uc_stack.ss_size = MINSIGSTKSZ;
    coro->resume_context.uc_link = 0;

    getcontext(&coro->resume_context);
    makecontext(&coro->resume_context, (void (*)())_coro_entry_point, 1, coro);
    return coro;
}

int coro_resume(coro_t *coro) {    
    if (coro->is_coro_finished) return -1;
    swapcontext(&coro->suspend_context, &coro->resume_context);
    return coro->yield_value;
}

void coro_yield(coro_t *coro, int value) {
    coro->yield_value = value;
    swapcontext(&coro->resume_context, &coro->suspend_context);
}

void coro_free(coro_t *coro) {
    free(coro->resume_context.uc_stack.ss_sp);
    free(coro);
}

The most used APIs for coroutine is coro_resume & coro_yield that drags the actual work of suspension & resumption.
If you already have consciously gone through above Context Switching API Examples, then I dont think there is much to explain for coro_resume & coro_yield. Its just coro_yield jumps to coro_resume & vice-versa. Except the first call to coro_resume which jumps to _coro_entry_point.
coro_new function allocates memory for handler as well as stack & then populates the handler members. Again getcontext & makecontext should be clear by this point. If not then please re-read above section on Context Switching API Examples.
If you genuinly understand the above coroutine API implementation, then obvious question would be why do we even need _coro_entry_point? Why can't we directly jump to actual coroutine function?.
- But then my argument will be "How do you ensure the lifetime of coroutine?".
- Which technically means, number of call to coro_resume should be similar/valid to number of call to coro_yield plus one(for actual return).
- Otherwise you can not keep track of yields. And behaviour will become undefined.
Nonetheless, _coro_entry_point function is needed otherwise there is no way by which you can deduce the corotine execution finished completely. And next/subsequent call to coro_resume is not valid anymore.

Coroutine Lifetime

By above implementation, using coroutine handler, you should only be able to execute coroutine function completely once throught out program/application life.
If you wants to call coroutine function again, then you need to create new coroutine handler. And rest of the process will remain same.

Coroutine Usage Example

`coroutine_example.c`

#include <stdio.h>
#include <assert.h>
#include "coroutine.h"

int hello_world(coro_t *coro) {    
    puts("Hello");
    coro_yield(coro, 1);    // Suspension point that returns the value `1`
    puts("World");
    return 2;
}

int main() {
    coro_t *coro = coro_new(hello_world);
    assert(coro_resume(coro) == 1);     // Verifying return value
    assert(coro_resume(coro) == 2);     // Verifying return value
    assert(coro_resume(coro) == -1);    // Invalid call
    coro_free(coro);
    return EXIT_SUCCESS;
}

Usecase is pretty straight forward:
- First, you create a coroutine handler.
- Then, you start/resume the actual coroutine function with the help of the same coroutine handler.
- And, whenever your actual coroutine function encounters a call the coro_yield, it will suspend the execution & return the value passed in 2nd argument of coro_yield.
And when actual coroutine function execution finishes completely. The call to coro_resume will return -1 to indicate that the coroutine handler object is no more valid & the lifetime is expired.
So, you see coro_resume is a wrapper to our coroutine hello_world which executes hello_world in parts(obviously by context switching).

Compiling

I have tested this example in WSL with gcc 9.3.0 & glibc 2.31.

$ gcc -I./ coroutine_example.c coroutine.c  -o myapp && ./myapp 
Hello
World

Parting Words

You see there is no magic if you understand “How CPU Executes The Code..!” well-given Glibc provided a rich set of context switching API. And, from the perspective of low-level developers, it's merely a well-arranged & difficult to organize/maintain(if used raw) context switching function calls. My intention here was to put the foundation for C++20 Coroutine. Because I believe, if you see the code from CPU & compiler’s point of view, then everything becomes easy to reason about in C++. See you next time with my C++20 Coroutine post.

Chain of Responsibility Design Pattern in Modern C++

Vishal Chovatiya — Mon, 05 Oct 2020 03:24:26 +0000

Chain of Responsibility is a Behavioural Design Pattern that provides facility to propagate event/request/command/query to the chain of loosely coupled objects. Chain of Responsibility Design Pattern in Modern C++ lets you pass requests along a chain of handlers & upon receiving a request, each handler decides either to process the request or to forward it to the next handler in the chain.

/!\: This article has been originally published on my blog. If you are interested in receiving my latest articles, please sign up to my newsletter.

By the way, If you haven't check out my other articles on Behavioural Design Patterns, then here is the list:

The code snippets you see throughout this series of articles are simplified not sophisticated. So you often see me not using keywords like override, final, public(while inheritance) just to make code compact & consumable(most of the time) in single standard screen size. I also prefer struct instead of class just to save line by not writing "public:" sometimes and also miss virtual destructor, constructor, copy constructor, prefix std::, deleting dynamic memory, intentionally. I also consider myself a pragmatic person who wants to convey an idea in the simplest way possible rather than the standard way or using Jargons.

Note:

If you stumbled here directly, then I would suggest you go through What is design pattern? first, even if it is trivial. I believe it will encourage you to explore more on this topic.
All of this code you encounter in this series of articles are compiled using C++20(though I have used Modern C++ features up to C++17 in most cases). So if you don't have access to the latest compiler you can use https://wandbox.org/ which has preinstalled boost library as well.

Intent

To provide the chance to handle the request by more than one object/component.

Chain of Responsibility Design Pattern is a chain of loosely coupled objects who all get a chance to process command/query. And they may have some sort of default processing implementation and/or they can also terminate the processing chain and thereby preventing propagation of the event to the rest of the objects.
In other words, its processing pipeline where you just launch-and-leave.

Classic Examples for Chain of Responsibility Design Pattern in C++

A typical use-case for Chain of Responsibility is the login process. That requires a certain number of steps to complete successfully like user name, password, captcha, etc. to matched properly. Consider the following traditional example for the same:

struct Authentication {
    Authentication*     m_next{nullptr};

    virtual bool authenticate() = 0;
    void next_authentication(Authentication *nextAuth) { m_next = nextAuth; }
};

struct UserName : Authentication {
    string      m_name;

    UserName(string name) : m_name(name){}
    bool is_valid_user_name() { return true; }
    bool authenticate() {
        if(!is_valid_user_name()) {
            cout << "Invalid user name" << endl;
            return false;
        }
        else if(m_next) return m_next->authenticate();
        return true;
    }
};

struct Password : Authentication {
    string      m_password;

    Password(string password) : m_password(password){}
    bool is_valid_password() { return true; }
    bool authenticate() {
        if(!is_valid_password()) {
            cout << "Invalid password" << endl;
            return false;
        }
        else if(m_next) return m_next->authenticate();
        return true;
    }
};

int main() {
    Authentication *login{new UserName("John")};
    login->next_authentication(new Password("password"));
    login->authenticate();
    return EXIT_SUCCESS;
}

I know this is not a very good example but sufficient to convey an idea of Chain of Responsibility. As you can see above, Login is a single process which requires multiple subprocesses to be carried out like username & password authentication.
So in our case login->authenticate(); fires the chain of responsibility to verify each step required for login one-by-one.
You can also add more steps in the login process, for example, to add captcha, create captcha class inherited with Authentication & add that class object pointer in the login's next authentication chain as we did for UserName & Password.
Now before we move on to the more sophisticated implementations I just wanted to mention the fact that this particular implementation of a chain of responsibility seems quite artificial. Because essentially what's happening here is you're building a singly linked list so the question is well why not just use a std::list or a std::vector. It's certainly a very valid concern. But as I mentioned earlier, this is how people used to build chain irresponsibilities.

Boost Example for Chain of Responsibility Design Pattern

What you going to see now is a modern way of implementing the Chain of Responsibility Design Pattern that is known as Event Broker. Which is actually a combination of several design patterns like Command, Mediator & Observer.

#include <iostream>
#include <string>
using namespace std;
#include <boost/signals2.hpp>
//using namespace boost::signals2;

struct Query {                          // Command
    int32_t     m_cnt{0};
};

struct EventObserver {                  // Observer
    boost::signals2::signal<void(Query &)>       m_handlers;
};

struct ExampleClass : EventObserver {   // Mediator
    void generate_event() { 
        cout << "Event generated" << endl;
        Query   q;
        m_handlers(q); 
        cout << endl;
    }
};

struct BaseHandler {
    ExampleClass&       m_example;
};

struct Handler_1 : BaseHandler {
    boost::signals2::connection      m_conn;

    Handler_1(ExampleClass &example) : BaseHandler{example}
    {
        m_conn = m_example.m_handlers.connect([&](Query &q) {
            cout << "Serving by Handler_1 : count = " << ++q.m_cnt << endl;
        });
    }
    ~Handler_1() { m_conn.disconnect(); }
};

struct Handler_2 : BaseHandler {
    boost::signals2::connection      m_conn;

    Handler_2(ExampleClass &example) : BaseHandler{example}
    {
        m_conn = m_example.m_handlers.connect([&](Query &q) {
            cout << "Serving by Handler_2 : count = " << ++q.m_cnt << endl;
        });
    }
    ~Handler_2() { m_conn.disconnect(); }
};

int main() {
    ExampleClass example;
    Handler_1 applyThisHandlerOn{example};

    example.generate_event();       // Will be served by Handler_1

    { 
        Handler_2 TemporaryHandler{example};
        example.generate_event();   // Will be served by Handler_1 & Handler_2
    }

    example.generate_event();       // Will be served by Handler_1
    return EXIT_SUCCESS;
}
/*
Event generated
Serving by Handler_1 : count = 1

Event generated
Serving by Handler_1 : count = 1
Serving by Handler_2 : count = 2

Event generated
Serving by Handler_1 : count = 1
*/

So as you can see, we have ExampleClass which generates an event & having boost::signal2 as an observer. We have Query(i.e. Command Design Pattern) to pass between all the register handlers.
Then we have handler arrangement which registers the lambda function to handle the event in constructor & same will be de-register in the destructor.
In main, we have facilitated the ad-hoc registration of handlers just by declaring objects which process the Query passed in ExampleClass::generate_event(). Handler automatically de-registers itself when it goes out of scope thanks to RAII.

Benefits of Chain of Responsibility Design Pattern

Decouples the sender & receiver as we saw a more sophisticated approach using Mediator & Command Design Pattern.
Simplifies code as the object which is generating event does not need to know the chain structure & command/query.
Enhances flexibility of object assigned duties. By changing the members within the chain or change their order, allow dynamically adding or deleting responsibility.
Increase extensibility as adding a new handler is very convenient.

Summary by FAQs

Can I use(or Difference) Chain of Responsibility Design Pattern over Decorator?

-- When you in need of multiple Decorator.
-- While you want to add new functionality dynamically.
-- When you want a change of order in functionality configurable.
-- For example, you created Decorator of WalkingAnimal & BarkingAnimal of Animal, and now you want both combined at run-time. In such case Chain of Responsibility would be the right choice.

When should I use Chain of Responsibility Design Pattern?

-- When there is more than one object to service a request.
-- These objects & its order determined at run time on the basis of request type.
-- When you do not want to bind request & handler tightly.

Proxy Design Pattern in Modern C++

Vishal Chovatiya — Mon, 28 Sep 2020 03:18:21 +0000

In software engineering, Structural Design Patterns deal with the relationship between objects i.e. how objects/classes interact or build a relationship in a manner suitable to the situation. The Structural Design Patterns simplify the structure by identifying relationships. In this article of the Structural Design Patterns, we're going to take a look at Proxy Design Pattern in C++ which dictates the way you access the object.

/!\: This article has been originally published on my blog. If you are interested in receiving my latest articles, please sign up to my newsletter.

If you haven't check out other Structural Design Patterns, then here is the list:

Adapter
Bridge
Composite
Decorator
Facade
Flyweight
Proxy

Note:

If you stumbled here directly, then I would suggest you go through What is design pattern? first, even if it is trivial. I believe it will encourage you to explore more on this topic.
All of this code you encounter in this series of articles are compiled using C++20(though I have used Modern C++ features up to C++17 in most cases). So if you don't have access to the latest compiler you can use https://wandbox.org/ which has preinstalled boost library as well.

Intent

An interface for accessing a particular resource.

The proxy acts as an interface to a particular resource which may be remote, expensive to construct or require some additional functionality like logging or something else.
But the key thing about the proxy is that its interface looks just like the interface of the object that you are actually attempting to access. This interface could be a method, overloaded operator or another object of different/local class.

Proxy Design Pattern Examples in C++

A very sophisticated example of the Proxy Design Pattern in C++ that you're probably using every day already is a smart pointer (like std::unique_ptr, std::shared_ptr, etc.) from the standard library

// Ways to access object through pointer
ptr->print();
*ptr = 5;

So let me give you an explanation as to why a smart pointer would be a proxy. Well just by seeing the above code snippet, you can not decide that ptr is a raw pointer or smart pointer.
Thus smart pointer are proxies as they satisfy both the condition of proxy i.e.
1. Provide an interface to access the resource.
2. The interface looks just like the interface of the object.
There are many different kinds of proxy available like Remote proxy, Virtual proxy, Protection proxy, Communication Proxy. We will see some of them here.

Property Proxy

As you probably know other programming languages such as C# have this idea of properties. There probably is nothing more than a field plus a getter & setter methods for that field. Let's suppose that we wanted to get properties in C++ so we have written Property class as:

template<typename T>
struct Property {
    T   m_value;

    Property(const T initialValue) { * this = initialValue; }
    operator T() { return m_value; }
    T operator = (T newValue) { return m_value = newValue; }
};

struct Creature {
    Property<int32_t>   m_strength{10};
    Property<int32_t>   m_agility{5};
};

int main() {
    Creature creature;
    creature.m_agility = 20;
    cout << creature.m_agility << endl;
    return EXIT_SUCCESS;
}

But seeing above code, you might be wondering that why don't we just declare strength & agility as int32_t. Now let's suppose that for some reason you actually wanted to "intercept" or "have to log" the assignments as well as the access to these fields. So you want something which is effective as a Property rather than designing the getter & setter method for all the attributes.

Virtual Proxy

So another type of proxy that you're bound to encounter at some point is what's called a Virtual Proxy. Now a Virtual Proxy gives you the appearance of working with the same object that you're used to working with even though the object might not have even been created.

struct Image {
    virtual void draw() = 0;
};

struct Bitmap : Image {
    Bitmap(const string &filename) : m_filename(filename) {
        cout << "Loading image from " << m_filename << endl;
        // Steps to load the image
    }
    void draw() { cout << "Drawing image " << m_filename << endl; }

    string      m_filename;
};

int main() {
    Bitmap img_1{"image_1.png"};
    Bitmap img_2{"image_2.png"};

    (rand() % 2) ? img_1.draw() : img_2.draw();

    return EXIT_SUCCESS;
}

As you can see above, Bitmap image is derived from the Image interface having polymorphic behaviour as draw(). Bitmap loads the image eagerly in its constructor.
At first sight, this seems ok, but the problem with this Bitmap is that we don't really need to load the image until the drawing code fires. So there is no point on loading both the images in memory at the time of construction.
Now let me show you how you can improve the above code without changing Bitmap. This kind of technique is quite useful when you are working with a third-party library & wants to write a wrapper around it for some performance improvements.

struct LazyBitmap : Image {
    LazyBitmap(const string &filename) : m_filename(filename) {}
    void draw() {
        if (!m_bmp) m_bmp = make_unique<Bitmap>(m_filename);
        m_bmp->draw();
    }

    unique_ptr<Bitmap>      m_bmp{nullptr};
    string                  m_filename;
};

LazyBitmap img_1{"image_1.png"};
LazyBitmap img_2{"image_2.png"};

As you can see, we are not using Bitmap until we need it. Rather we are just caching file name to create Bitmap whenever somebody wants to draw an image. So if nobody wants to draw the image there is really no point in loading it from the file.

Communication Proxy(Intuitive Proxy Design Pattern in C++)

Communication Proxy is by far the most common & intuitive Proxy Design Pattern in C++ you might have come across. A straight forward example of communication proxy is subscript operator overloading. Consider the following example of user-defined type i.e. arr2D which works exactly as primitive type 2 dimensional array:

template <typename T>
struct arr2D {
    struct proxy {
        proxy(T *arr) : m_arr_1D(arr) {}
        T &operator[](int32_t idx) {
            return m_arr_1D[idx];
        }

        T   *m_arr_1D;
    };

    arr2D::proxy operator[](int32_t idx) {
        return arr2D::proxy(m_arr_2D[idx]);
    }

    T   m_arr_2D[10][10];
};

int main() {
    arr2D<int32_t> arr;
    arr[0][0] = 1;  // Uses the proxy object
    return EXIT_SUCCESS;
}

Benefits of Proxy Design Pattern

The proxy provides a nice & easy interface for even complex data arrangements.
Proxy Design Pattern especially Virtual Proxy also provides performance improvement as we have seen in lazy image loading case above.
Property proxy provides the flexibility of logging access to object attributes without the client even knowing.

Summary by FAQs

Is Decorator & Proxy Design Patterns are the same?

They are kind of similar(as both use composition) but used for a different purpose. For example, if you consider the above examples, Proxy usually manages the life cycle & access to objects, whereas the Decorators is a wrapper of the original object having more functionality.

Difference between Adapter, Decorator & Proxy Design Pattern?

-- Adapter provides a different/compatible interface to the wrapped object
-- Proxy provides a somewhat same or easy interface
-- Decorator provides enhanced interface

What are the use cases of Proxy Design Pattern?

-- When your objects are resource consuming and you have the most of their time stored on disk, you can use the proxy to act as a placeholder(like we did in lazy image loading above).
-- When you want to add access restrictions like object is accessed read-only or making user-based access control before really doing the operations (e.g. if the user is authorised, do the operation, if not, throw an access control exception)

Flyweight Design Pattern in Modern C++

Vishal Chovatiya — Mon, 21 Sep 2020 02:39:31 +0000

Flyweight Design Pattern is a Structural Design Pattern that concerned with space optimization. It is a technique to minimizes memory footprint by sharing or avoiding redundancy as much as possible with other similar objects. Flyweight Design Pattern in Modern C++ is often used in a situation where object count is higher which uses an unacceptable amount of memory. Often some parts of these objects can be shared & kept in common data structures that can be used by multiple objects.

/!\: This article has been originally published on my blog. If you are interested in receiving my latest articles, please sign up to my newsletter.

If you haven't check out my other articles on Structural Design Patterns, then here is the list:

Adapter
Bridge
Composite
Decorator
Facade
Flyweight
Proxy

Note:

If you stumbled here directly, then I would suggest you go through What is design pattern? first, even if it is trivial. I believe it will encourage you to explore more on this topic.
All of this code you encounter in this series of articles are compiled using C++20(though I have used Modern C++ features up to C++17 in most cases). So if you don't have access to the latest compiler you can use https://wandbox.org/ which has preinstalled boost library as well.

Intent

To avoid redundancy when storing data.

Flyway Design Pattern is quite simply a space optimization technique. That allows you to use less memory by storing some of the common data to several items or several objects.
We store it externally and simply refer(by reference, pointer or any other mechanism) to it when we actually need it.

Flyweight Design Pattern Example in C++

Well, the one thing that we want to do if we're storing lots of data is to avoid any redundancy. It's like compression in images or films if you have the same block repeating over and over again. You probably want to actually avoid having that block take up memory. But instead, you just write it and say how many times it repeats.
For example, let say you are designing a game. You're going to have lots of users with identical first and/or last names. You are going to have lots of people called John Smith. But you're also going to have lots of people called John and lots of people whose last name is Smith.
And there are no point in actually storing the same first & last name combinations over & over again. Because you are simply wasting memory. So what you would do instead is you would store a list of names somewhere else. And then you would keep the pointers to those names.

// Note: You can try following code at  https://wandbox.org/. 

#include <boost/bimap.hpp>

struct User {
    User(string f, string l) : m_first_name{add(f)}, m_last_name{add(l)} { }

    string get_first_name() {return names.left.find(m_first_name)->second;}
    string get_last_name() {return names.left.find(m_last_name)->second;}

    friend ostream& operator<<(ostream& os, User& obj) {
        return os <<
            obj.get_first_name() << "(id=" << obj.m_first_name << "), " <<
            obj.get_last_name() << "(id=" << obj.m_last_name << ")" ;
    }

protected:
    using key = uint32_t;
    static boost::bimap<key, string>        names;
    static key                              seed;

    static key add(string s) {
        auto it = names.right.find(s);
        if (it == names.right.end()) {
            names.insert({++seed, s});
            return seed;
        }
        return it->second;
    }

    key     m_first_name, m_last_name;
};

User::key                           User::seed = 0;
boost::bimap<User::key, string>     User::names{};

int main() {
    User john_doe {"John","Doe"};
    User jane_doe {"Jane","Doe"};

    cout << "John Details: " << john_doe << endl;
    cout << "Jane Details: " << jane_doe << endl;

    return EXIT_SUCCESS;
}
/*
John Details: John(id=1), Doe(id=2)
Jane Details: Jane(id=3), Doe(id=2)
*/

If you see the essence from above flyweight implementation, it just storing data in the static qualified data structure by taking care of redundancy. So that it can be reusable between multiple objects of the same type.

Implementing Flyweight Design Pattern using Boost

The Flyweight Design Pattern isn't exactly new. And this approach of caching information is something that people have already packaged into different libraries for you to use.
So instead of building all these wonderful by maps and whatnot what you can do is just use a library solution.

#include <boost/flyweight.hpp>

struct User {
    boost::flyweight<string>   m_first_name, m_last_name;

    User(string f, string l) : m_first_name(f), m_last_name(l) { }
};

int main() {
    User john_doe{ "John", "Doe" };
    User jane_doe{ "Jane", "Doe" };

    cout<<boolalpha ;
    cout<<(&jane_doe.m_first_name.get() == &john_doe.m_first_name.get())<<endl;    // False
    cout<<(&jane_doe.m_last_name.get() == &john_doe.m_last_name.get())<<endl;      // True

    return EXIT_SUCCESS;
}
// Try @ https://wandbox.org/.

As you can see, we are comparing the address of John's last name & Jane's last name in the main() function which prints out to be true if you run the above code suggesting that redundancy is perfectly taken cared by boost::flyweight<>.

Benefits of Flyweight Design Pattern

Facilitates the reuse of many fine-grained objects, making the utilization of large numbers of objects more efficient. -- verbatim GoF.
Improves data caching for higher response time.
Data caching intern increases performance due to a lesser number of heavy objects
Provide a centralized mechanism to control the states/common-attributes objects.

Summary by FAQs

When to use a Flyweight Design Pattern?

-- In need of a large number of objects.
-- When there is a repetitive creation of heavy objects which can be replaced by a few shared objects

Difference between Singleton and Flyweight Design Pattern?

-- In Singleton Design Pattern, you cannot create more than one object. You need to reuse the existing object in all parts of the application.
-- While in Flyweight Design Pattern you can have a large number of similar objects which can share a common single resource.

Drawbacks of Flyweight Design Pattern?

As similar to Singleton Design Pattern, concurrency is also a headache in the Flyweight Design Pattern. Without appropriate measures, if you create Flyweight objects in a concurrent environment, you may end up having multiple instances of the same object which is not desirable.

Facade Design Pattern in Modern C++

Vishal Chovatiya — Mon, 14 Sep 2020 03:44:34 +0000

Facade Design Pattern is a Structural Design Pattern used to provide a unified interface to a complex system. It is same as Facade in building architecture, a Facade is an object that serves as a front-facing interface masking a more complex underlying system. A Facade Design Pattern in C++ can:

Improve the readability & usability of a software library by masking interaction with more complex components by providing a single simplified API.
Provide a context-specific interface to more generic functionality.
Serve as a launching point for a broader refactor of monolithic or tightly-coupled systems in favour of more loosely-coupled code. Frankly speaking, even I don't understand this point. I have just copied this from Wikipedia.

/!\: This article has been originally published on my blog. If you are interested in receiving my latest articles, please sign up to my newsletter.

Before we move forward, Let me correct the spelling of Facade i.e. "Façade" & it pronounces as "fa;sa;d". A hook or tail added under the letters C called a cedilla used in most of the European languages to indicate a change of pronunciation for that particular letter. We will not go into details of it, otherwise, we would be out of topic.

By the way, If you haven't check out my other articles on Structural Design Patterns, then here is the list:

Adapter
Bridge
Composite
Decorator
Facade
Flyweight
Proxy

Note:

If you stumbled here directly, then I would suggest you go through What is design pattern? first, even if it is trivial. I believe it will encourage you to explore more on this topic.
All of this code you encounter in this series of articles are compiled using C++20(though I have used Modern C++ features up to C++17 in most cases). So if you don't have access to the latest compiler you can use https://wandbox.org/ which has preinstalled boost library as well.

Intent

To provide unified interface by hiding system complexities.

This is by far the simplest & easiest design pattern I have ever come across.
In other words, the Facade Design Pattern is all about providing a simple & easy to understand interface over a large and sophisticated body of code.

Facade Design Pattern Example in C++

Imagine you set up a smart house where everything is on the remote. So to turn the lights on you push lights on-button -- And same for TV, AC, Alarm, Music, etc...
When you leave a house you would need to push 100 buttons to make sure everything is off & are good to go which could be a little annoying if you are lazy like me.
So I defined a Facade for leaving & coming back. (Facade functions represent buttons...). So when I come & leave I just make one call & it takes care of everything...

// Stolen from: https://en.wikibooks.org/wiki/C%2B%2B_Programming/Code/Design_Patterns
struct Alarm {
    void alarm_on()    { cout << "Alarm is on and house is secured"<<endl; }
    void alarm_off() { cout << "Alarm is off and you can go into the house"<<endl; }
};

struct Ac {
    void ac_on()    { cout << "Ac is on"<<endl; }
    void ac_off()    { cout << "AC is off"<<endl; }
};

struct Tv {
    void tv_on()    { cout << "Tv is on"<<endl; }
    void tv_off()    { cout << "TV is off"<<endl; }
};

struct HouseFacade {
    void go_to_work() {
        m_ac.ac_off();
        m_tv.tv_off();
        m_alarm.alarm_on();
    }
    void come_home() {
        m_alarm.alarm_off();
        m_ac.ac_on();
        m_tv.tv_on();
    }
private:
    Alarm   m_alarm;
    Ac      m_ac;
    Tv      m_tv;
};

int main() {
    HouseFacade hf;
    //Rather than calling 100 different on and off functions thanks to facade I only have 2 functions...
    hf.go_to_work();
    hf.come_home();
    return EXIT_SUCCESS;
}

Note that we have just combined the different none/somewhat-related classes into HouseFacade. We would also be able to use interface with polymorphic turn_on() & turn_off() method with override in respective subclasses, to create a collection of Ac, Tv, Alarm objects to add Composite Design Pattern for more sophistication.
But that will complicate system further & add the learning curve. Which is exactly opposite for what Facade Design Pattern is used in the first place.

Benefits of Facade Design Pattern

Facade defines a higher-level interface that makes the subsystem easier to use by wrapping a complicated subsystem.
This reduces the learning curve necessary to successfully leverage the subsystem.

Summary by FAQs

Is Facade a class which contains a lot of other classes?

Yes. It is a wrapper for many sub-systems in the application.

What makes it a design pattern? For me, it is like a normal class.

All design patterns too are normal classes.

What is the practical use case of the Facade Design Pattern?

A typical application of Facade Design Pattern is console/terminal/command-prompt you find in Linux or Windows is a unified way to access machine functionality provided by OS.

Difference between Adapter & Facade Design Pattern?

Adapter wraps one class and the Facade may represent many classes

Decorator Design Pattern in Modern C++

Vishal Chovatiya — Mon, 07 Sep 2020 02:39:39 +0000

In software engineering, Structural Design Patterns deal with the relationship between object & classes i.e. how object & classes interact or build a relationship in a manner suitable to the situation. The Structural Design Patterns simplify the structure by identifying relationships. In this article of the Structural Design Patterns, we're going to take a look at the not so complex yet subtle design pattern that is Decorator Design Pattern in Modern C++ due to its extensibility & testability. It is also known as Wrapper.

/!\: This article has been originally published on my blog. If you are interested in receiving my latest articles, please sign up to my newsletter.

By the way, If you haven't check out my other articles on Structural Design Patterns, then here is the list:

Adapter
Bridge
Composite
Decorator
Facade
Flyweight
Proxy

Note:

If you stumbled here directly, then I would suggest you go through What is design pattern? first, even if it is trivial. I believe it will encourage you to explore more on this topic.
All of this code you encounter in this series of articles are compiled using C++20(though I have used Modern C++ features up to C++17 in most cases). So if you don't have access to the latest compiler you can use https://wandbox.org/ which has preinstalled boost library as well.

Intent

To facilitates the additional functionality to objects.

Sometimes we have to augment the functionality of existing objects without rewrite or altering existing code, just to stick to the Open-Closed Principle. This also preserves the Single Responsibility Principle to have extra functionality on the side.

Decorator Design Pattern Examples in C++

And to achieve this we have two different variants of Decorator Design Pattern in C++:
1. Dynamic Decorator: Aggregate the decorated object by reference or pointer.
2. Static Decorator: Inherit from the decorated object.

Dynamic Decorator

struct Shape {
    virtual operator string() = 0;
};

struct Circle : Shape {
    float   m_radius;

    Circle(const float radius = 0) : m_radius{radius} {}
    void resize(float factor) { m_radius *= factor; }
    operator string() {
        ostringstream oss;
        oss << "A circle of radius " << m_radius;
        return oss.str();
    }
};

struct Square : Shape {
    float   m_side;

    Square(const float side = 0) : m_side{side} {}
    operator string() {
        ostringstream oss;
        oss << "A square of side " << m_side;
        return oss.str();
    }
};

So, we have a hierarchy of two different Shapes(i.e. Square & Circle) & we want to enhance this hierarchy by adding colour to it. Now we're suddenly not going to create two other classes e.g. coloured circle & a coloured square. That would be too much & not a scalable option.
Rather we can just have ColoredShape as follows.

struct ColoredShape : Shape {
    const Shape&    m_shape;
    string          m_color;

    ColoredShape(const Shape &s, const string &c) : m_shape{s}, m_color{c} {}
    operator string() {
        ostringstream oss;
        oss << string(const_cast<Shape&>(m_shape)) << " has the color " << m_color;
        return oss.str();
    }
};

// we are not changing the base class of existing objects
// cannot make, e.g., ColoredSquare, ColoredCircle, etc.

int main() {
    Square square{5};
    ColoredShape green_square{square, "green"};    
    cout << string(square) << endl << string(green_square) << endl;
    // green_circle.resize(2); // Not available
    return EXIT_SUCCESS;
}

Why this is a dynamic decorator?
Because you can instantiate the ColoredShape at runtime by providing needed arguments. In other words, you can decide at runtime that which Shape(i.e. Circle or Square) is going to be coloured.

You can even mix the decorators as follows:

struct TransparentShape : Shape {
    const Shape&    m_shape;
    uint8_t         m_transparency;

    TransparentShape(const Shape& s, const uint8_t t) : m_shape{s}, m_transparency{t} {}

    operator string() {
        ostringstream oss;
        oss << string(const_cast<Shape&>(m_shape)) << " has "
            << static_cast<float>(m_transparency) / 255.f * 100.f
            << "% transparency";
        return oss.str();
    }
};

int main() {
    TransparentShape TransparentShape{ColoredShape{Square{5}, "green"}, 51};
    cout << string(TransparentShape) << endl;
    return EXIT_SUCCESS;
}

Limitation of Dynamic Decorator

If you look at the definition of Circle, You can see that the circle has a method called resize(). we can not use this method as we did aggregation on-base interface Shape & bound by the only method exposed in it.

Static Decorator

The dynamic decorator is great if you don't know which object you are going to decorate and you want to be able to pick them at runtime but sometimes you know the decorator you want at compile time in which case you can use a combination of C++ templates & inheritance.

template <class T>  // Note: `class`, not typename
struct ColoredShape : T {
    static_assert(is_base_of<Shape, T>::value, "Invalid template argument"); // Compile time safety

    string      m_color;

    template <typename... Args>
    ColoredShape(const string &c, Args &&... args) : m_color(c), T(std::forward<Args>(args)...) { }

    operator string() {
        ostringstream oss;
        oss << T::operator string() << " has the color " << m_color;
        return oss.str();
    }
};

template <typename T>
struct TransparentShape : T {
    uint8_t     m_transparency;

    template <typename... Args>
    TransparentShape(const uint8_t t, Args... args) : m_transparency{t}, T(std::forward<Args>(args)...) { }

    operator string() {
        ostringstream oss;
        oss << T::operator string() << " has "
            << static_cast<float>(m_transparency) / 255.f * 100.f
            << "% transparency";
        return oss.str();
    }
};

int main() {
    ColoredShape<Circle> green_circle{"green", 5};
    green_circle.resize(2);
    cout << string(green_circle) << endl;

    // Mixing decorators
    TransparentShape<ColoredShape<Circle>> green_trans_circle{51, "green", 5};
    green_trans_circle.resize(2);
    cout << string(green_trans_circle) << endl;
    return EXIT_SUCCESS;
}

As you can see we can now call the resize() method which was the limitation of Dynamic Decorator. You can even mix the decorators as we did earlier.
So essentially what this example demonstrates is that if you're prepared to give up on the dynamic composition nature of the decorator and if you're prepared to define all the decorators at compile time you get the added benefit of using inheritance.
And that way you actually get the members of whatever object you are decorating being accessible through the decorator & mixed decorator.

Functional Approach to Decorator Design Pattern using Modern C++

Up until now, we were talking about the Decorator Design Pattern which decorates over a class but you can do the same for functions. Following is a typical logger example for the same:

// Need partial specialization for this to work
template <typename T>
struct Logger;

// Return type and argument list
template <typename R, typename... Args>
struct Logger<R(Args...)> {
    function<R(Args...)>    m_func;
    string                  m_name;

    Logger(function<R(Args...)> f, const string &n) : m_func{f}, m_name{n} { }

    R operator()(Args... args) {
        cout << "Entering " << m_name << endl;
        R result = m_func(args...);
        cout << "Exiting " << m_name << endl;
        return result;
    }
};

template <typename R, typename... Args>
auto make_logger(R (*func)(Args...), const string &name) {
    return Logger<R(Args...)>(std::function<R(Args...)>(func), name);
}

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

int main() {
    auto logged_add = make_logger(add, "Add");
    auto result = logged_add(2, 3);
    return EXIT_SUCCESS;
}

Above example may seem a bit complex to you but if you have a clear understanding of variadic temple then it won't take more than 30 seconds to understand what's going on here.

Benefits of Decorator Design Pattern

Decorator facilitates augmentation of the functionality for an existing object at run-time & compile time.
Decorator also provides flexibility for adding any number of decorators, in any order & mixing it.
Decorators are a nice solution to permutation issues because you can wrap a component with any number of Decorators.
It is a wise choice to apply the Decorator Design Pattern for already shipped code. Because it enables backward compatibility of application & less unit level testing as changes do not affect other parts of code.

Summary by FAQs

When to use the Decorator Design Pattern?

-- Employ the Decorator Design Pattern when you need to be able to assign extra behaviours to objects at runtime without breaking the code that uses these objects.
-- When the class has final keyword which means the class is not further inheritable. In such cases, the Decorator Design Pattern may come to rescue.

What are the drawbacks of using the Decorator Design Pattern?

-- Decorators can complicate the process of instantiating the component because you not only have to instantiate the component but wrap it in a number of Decorators.
-- Overuse of Decorator Design Pattern may complicate the system in terms of both i.e. Maintainance & learning curve.

Difference between Adapter & Decorator Design Pattern?

-- Adapter changes the interface of an existing object
-- Decorator enhances the interface of an existing object

Difference between Proxy & Decorator Design Pattern?

-- Proxy provides a somewhat same or easy interface
-- Decorator provides enhanced interface

Composite Design Pattern in Modern C++

Vishal Chovatiya — Mon, 31 Aug 2020 13:25:56 +0000

GoF describes the Composite Design Pattern as "Compose objects into a tree structure to represent part-whole hierarchies. Composite lets the client treat individual objects and compositions of objects uniformly". This seems over-complicated to me. So, I would not go into tree-leaf kind of jargon. Rather I directly saw you 2 or 3 different ways to implement Composite Design Pattern in Modern C++. But in simple words, the Composite Design Pattern is a Structural Design Pattern with a goal to treat the group of objects in the same manner as a single object.

/!\: This article has been originally published on my blog. If you are interested in receiving my latest articles, please sign up to my newsletter.

By the way, If you haven't check out my other articles on Structural Design Patterns, then here is the list:

Adapter
Bridge
Composite
Decorator
Facade
Flyweight
Proxy

Note:

If you stumbled here directly, then I would suggest you go through What is design pattern? first, even if it is trivial. I believe it will encourage you to explore more on this topic.
All of this code you encounter in this series of articles are compiled using C++20(though I have used Modern C++ features up to C++17 in most cases). So if you don't have access to the latest compiler you can use https://wandbox.org/ which has preinstalled boost library as well.

Intent

To treat individual & group of objects in a uniform manner.

So what is it all about and why do we need it. Well, we know that objects typically use other objects fields or properties or members through either inheritance or composition.
For example, in drawing applications, you have a Shape(e.g. Circle) that you can draw on the screen but you can also have a group of Shapes(e.g. vector<Circle>) which inherits from a collection Shape.
And they have certain common API which you can then call on one or the other without knowing in advance whether you're working with a single element or with the entire collection.

Composite Design Pattern Examples in C++

So if you think about an application such as PowerPoint or any kind of vector drawing application you know that you can draw & drag individual shapes around.
But you can also group shapes together. And when you group several shapes together you can treat them as if they were a single shape. So you can grab the entire thing and also drag it and resize it and whatnot.
So, we're going to implement the Composite Design Pattern around this idea of several different shapes.

Classical Composite Design Pattern

struct Shape {
    virtual void draw() = 0;
};

struct Circle : Shape {
    void draw() { cout << "Circle" << endl; }
};

struct Group : Shape {
    string              m_name;
    vector<Shape*>      m_objects;

    Group(const string &n) : m_name{n} {}

    void draw() {
        cout << "Group " << m_name.c_str() << " contains:" << endl;
        for (auto &&o : m_objects)
            o->draw();
    }
};

int main() {
    Group root("root");
    root.m_objects.push_back(new Circle);

    Group subgroup("sub");
    subgroup.m_objects.push_back(new Circle);

    root.m_objects.push_back(&subgroup);
    root.draw();

    return EXIT_SUCCESS;
}
/*
Group root contains:
Circle
Group sub contains:
Circle
*/

Composite Design Pattern using Curiously Recurring Template Pattern(CRTP)

As you've probably noticed machine learning is a really hot topic nowadays. And part of the machine learning mechanics is to use of neural networks so that's what we're going to take a look at now.

struct Neuron {
    vector<Neuron*>     in, out;
    uint32_t            id;

    Neuron() {
        static int id = 1;
        this->id = id++;
    }

    void connect_to(Neuron &other) {
        out.push_back(&other);
        other.in.push_back(this);
    }

    friend ostream &operator<<(ostream &os, const Neuron &obj) {
        for (Neuron *n : obj.in)
            os << n->id << "\t-->\t[" << obj.id << "]" << endl;

        for (Neuron *n : obj.out)
            os << "[" << obj.id << "]\t-->\t" << n->id << endl;

        return os;
    }
};

int main() {
    Neuron n1, n2;
    n1.connect_to(n2);
    cout << n1 << n2 << endl;
    return EXIT_SUCCESS;
}
/* Output
[1]    -->    2
1    -->    [2]
*/

As you can see we have a neuron structure which has connections to other neurons that modelled as vectors of pointers for input-output neuron connection. This is a very basic implementation and it works just fine as long as you just have individual neurons. Now the one thing that we haven't accounted for is what happens when you have more than one neuron or group of neurons to connect.
Let's suppose that we decide to make a neuron layer and now a layer of neurons is basically like a collection.

struct NeuronLayer : vector<Neuron> {
    NeuronLayer(int count) {
        while (count-- > 0)
            emplace_back(Neuron{});
    }

    friend ostream &operator<<(ostream &os, NeuronLayer &obj) {
        for (auto &n : obj)
            os << n;
        return os;
    }
};

int main() {
    NeuronLayer l1{1}, l2{2};
    Neuron n1, n2;
    n1.connect_to(l1);  // Neuron connects to Layer
    l2.connect_to(n2);  // Layer connects to Neuron
    l1.connect_to(l2);  // Layer connects to Layer
    n1.connect_to(n2);  // Neuron connects to Neuron

    return EXIT_SUCCESS;
}

Now as you probably guessed if you were to implement this head-on you're going to have a total of four different functions. i.e.

Neuron::connect_to(NeuronLayer&)
NeuronLayer::connect_to(Neuron&)
NeuronLayer::connect_to(NeuronLayer&)
Neuron::connect_to(Neuron&)

So this is state-space explosion & permutation problem and it's not good because we want a single function that enumerable both the layer as well as individual neurons.

template <typename Self>
struct SomeNeurons {
    template <typename T>
    void connect_to(T &other);
};

struct Neuron : SomeNeurons<Neuron> {
    vector<Neuron*>     in, out;
    uint32_t            id;

    Neuron() {
        static int id = 1;
        this->id = id++;
    }

    Neuron* begin() { return this; }
    Neuron* end() { return this + 1; }
};

struct NeuronLayer : vector<Neuron>, SomeNeurons<NeuronLayer> {
    NeuronLayer(int count) {
        while (count-- > 0)
            emplace_back(Neuron{});
    }
};

template <typename Self>
template <typename T>
void SomeNeurons<Self>::connect_to(T &other) {
    for (Neuron &from : *static_cast<Self *>(this)) {
        for (Neuron &to : other) {
            from.out.push_back(&to);
            to.in.push_back(&from);
        }
    }
}

template <typename Self>
ostream &operator<<(ostream &os, SomeNeurons<Self> &object) {
    for (Neuron &obj : *static_cast<Self *>(&object)) {
        for (Neuron *n : obj.in)
            os << n->id << "\t-->\t[" << obj.id << "]" << endl;

        for (Neuron *n : obj.out)
            os << "[" << obj.id << "]\t-->\t" << n->id << endl;
    }
    return os;
}

int main() {
    Neuron n1, n2;
    NeuronLayer l1{1}, l2{2};

    n1.connect_to(l1); // Scenario 1: Neuron connects to Layer
    l2.connect_to(n2); // Scenario 2: Layer connects to Neuron
    l1.connect_to(l2); // Scenario 3: Layer connects to Layer
    n1.connect_to(n2); // Scenario 4: Neuron connects to Neuron

    cout << "Neuron " << n1.id << endl << n1 << endl;
    cout << "Neuron " << n2.id << endl << n2 << endl;

    cout << "Layer " << endl << l1 << endl;
    cout << "Layer " << endl << l2 << endl;

    return EXIT_SUCCESS;
}
/* Output
Neuron 1
[1]    -->    3
[1]    -->    2

Neuron 2
4    -->    [2]
5    -->    [2]
1    -->    [2]

Layer 
1    -->    [3]
[3]    -->    4
[3]    -->    5

Layer 
3    -->    [4]
[4]    -->    2
3    -->    [5]
[5]    -->    2
*/

As you can see we have covered all four different permutation scenarios using a single SomeNeurons::connect_to method with the help of CRTP. And both Neuron & NeuronLayer conforms to this interface via self templatization.
Curiously Recurring Template Pattern comes handy here & has very straight implementation rule i.e. separate out the type-dependent & independent functionality and bind type *independent functionality with the base class using self-referencing template*.
I have written a separate article on Advanced C++ Concepts & Idioms including CRTP.

Benefits of Composite Design Pattern

Reduces code complexity by eliminating many loops over the homogeneous collection of objects.
This intern increases the maintainability & testability of code with fewer chances to break existing running & tested code.
The relationship is described in the Composite Design Pattern isn't a subclass relationship, it's a collection relationship. Which means client/API-user does not need to care about operations(like translating, rotating, scaling, drawing, etc.) whether it is a single object or an entire collection.

Summary by FAQs

When should I use the Composite Design Pattern?

-- You want clients to be able to ignore the difference between the group of objects and individual objects.
-- When you find that you are using multiple objects in the same way, and looping over to perform a somewhat similar action, then composite is a good choice.

What is the common example of the Composite Design Pattern?

-- File & Folder(collection of files): Here File is a single class. Folder inherits File and holds a collection of Files.

What is the difference between Decorator & Composite Design Pattern?

-- Decorator works on enhancing interface.
-- Composition works to unify interfaces for single & group of objects.

Bridge Design Pattern in Modern C++

Vishal Chovatiya — Mon, 24 Aug 2020 04:22:58 +0000

Bridge Design Pattern is a Structural Design Pattern used to decouple a class into two parts -- abstraction and it's implementation -- so that both can be developed independently. This promotes the loose coupling between class abstraction & its implementation. You get this decoupling by adding one more level of indirection i.e. an interface which acts as a bridge between your original class & functionality. Insulation is another name of Bridge Design Pattern in C++ world.

"All problems in computer science can be solved by another level of indirection." -- David Wheeler

By the way, If you haven't check out my other articles on Structural Design Patterns, then here is the list:

Adapter
Bridge
Composite
Decorator
Facade
Flyweight
Proxy

Note:

If you stumbled here directly, then I would suggest you go through What is design pattern? first, even if it is trivial. I believe it will encourage you to explore more on this topic.
All of this code you encounter in this series of articles are compiled using C++20(though I have used Modern C++ features up to C++17 in most cases). So if you don't have access to the latest compiler you can use https://wandbox.org/ which has preinstalled boost library as well.

/!\: This article has been originally published on my blog. If you are interested in receiving my latest articles, please sign up to my newsletter.

Intent

To separate the interface from its implementation.

In other words, It's all about connecting components together through flexible abstractions using aggregation/composition rather than inheritance/generalization.
This pattern involves an interface which acts as a bridge. That makes the functionality of concrete classes independent from interface implementer classes. Both types of classes can alter structurally without affecting each other.

Motivation for Bridge Design Pattern

Bridge Design Pattern prevents Cartesian Product complexity explosion. Don't be scared with this mathematical term, I have simplified it with an example below.
So, for example, let's suppose that you have some base class called Shape and then the Shape can be Circle or Square and it can also be drawn by API 1 or API 2.

struct DrawingAPI_1 { };
struct DrawingAPI_2 { };

struct Shape { virtual void draw() = 0; };

/* 2 x 2 scenario */
struct Circle : Shape, DrawingAPI_1 { };
struct Circle : Shape, DrawingAPI_2 { };

struct Square : Shape, DrawingAPI_1 { };
struct Square : Shape, DrawingAPI_2 { };

This way you end up having a two by two(2×2) scenario. So if you decide to implement it you have to implement four classes. One for you know the Circle with API_1, Circle with API_2 and so on.
The Bridge Design Pattern is precisely the pattern that actually avoids this whole entity explosion.
So instead of having something like above, what we can do is we design the DrawingAPI interface(which later on used to derive API 1 & 2) and aggregate it in Circle & Square.

Bridge Design Pattern C++ Example

So following is the typical implementation of the Bridge Design Pattern. We are not going to look at anything quite so complicated here. But essentially a bridge is a mechanism that decouples the interface or the hierarchy from the implementation.

struct DrawingAPI {
    virtual void drawCircle() = 0;
};

struct DrawingAPI_1 : DrawingAPI {
    void drawCircle() { cout << "Drawn by API 1"<< endl; }
};

struct DrawingAPI_2 : DrawingAPI {
    void drawCircle() { cout << "Drawn by API 2"<< endl; }
};

struct Shape {
    Shape(DrawingAPI &drawingAPI) : m_drawingAPI{drawingAPI} {}
    virtual void draw() = 0;
protected:
    DrawingAPI &m_drawingAPI;   // Now Shapes does not need to worry about drawing APIs
};

struct Circle : Shape {
    Circle(DrawingAPI &drawingAPI) : Shape{drawingAPI} {}
    void draw() { m_drawingAPI.drawCircle(); }
};

int main() {
    DrawingAPI_1 API_1;
    DrawingAPI_2 API_2;
    Circle(API_1).draw();
    Circle(API_2).draw();
    return EXIT_SUCCESS;
}

This way you don't rely as much as on inheritance and aggregation. Rather you rely on the interface.

Bridge Design Pattern using C++ Idiom: Pointer to Implementation(PIMPL)

How can we forget the PIMPLE idiom while we are discussing the Bridge Design Pattern! PIMPLE is the manifestation of the bridge design pattern albeit a slightly different one.
PIMPL idiom is all about hiding the implementation details of a particular class by sticking it into separate implementation pointed by pointer just as the name suggests. Let me show you how this works:

Person.h

#pragma once
#include <string>
#include <memory>

struct Person {
    /* PIMPL ------------------------------------ */
    class PersonImpl;
    unique_ptr<PersonImpl>  m_impl; // bridge - not necessarily inner class, can vary
    /* ------------------------------------------ */
    string                  m_name;

    Person();
    ~Person();

    void greet();
private:
    // secret data members or methods are in `PersonImpl` not here
    // as we are going to expose this class to client
};

Person.cpp <-- will be turned into shared library(.so/.dll), to hide the business logic

#include "Person.h"

/* PIMPL Implementation ------------------------------------ */
struct Person::PersonImpl {
    void greet(Person *p) {
        cout << "hello "<< p->name.c_str() << endl;
    }
};
/* --------------------------------------------------------- */

Person::Person() : m_impl(new PersonImpl) { }
Person::~Person() { delete m_impl; }
void Person::greet() { m_impl->greet(this); }

OK, so this is the pimple idiom in it's kind of concise form shall we say. And the question is Well why would you want to do this in the first place.
Security purpose, you might have a question that any way we are going to expose header file to the client which contains API of a class, then how do we get security here? Well, just think about the data members & private methods. If you have trade secrets & having a data member which contains critical information. Why do you even let the client know the name of the object?
One more benefit of PIMPL is compilation time which is critical for C++ as it widely criticized for it. But this is becoming less and less relevant as the compilers become more and more incremental. And they are really fantastic nowadays.

Secure & Faster PIMPL

As we have to use all the API using indirection provided by std::unique_ptr which accounts for some run-time overhead as we have to dereference the pointer every time for access.
Plus we also have construction & destruction overhead of std::unique_ptr because it creates a memory in a heap which involves many other functions calling along with system calls.
Moreover, we also have to bare some indirection if we want to access the data member of Person in PersonImpl like passing this pointer or so.

Person.h

#pragma once
#include <string>
#include <cstddef>
#include <type_traits>

struct Person {
    Person();
    ~Person();
    void greet();

private:
    static constexpr size_t     m_size = 1024;
    using pimpl_storage_t = aligned_storage<m_size, alignment_of_v<max_align_t>>::type;

    string                      m_name;
    pimpl_storage_t             m_impl;
};

Person.cpp <-- will be turned into shared library(.so/.dll), to hide the business logic

#include "Person.h"
#include <iostream>

struct PersonImpl {
    void greet(string &name) {
        cout << "hello "<< name << endl;
    }
};

Person::Person() {
  static_assert(sizeof(impl) >= sizeof(PersonImpl)); // Compile time safety
  new(&impl) PersonImpl;
}
Person::~Person() { reinterpret_cast<PersonImpl*>(&impl)->~PersonImpl(); }
void Person::greet() { reinterpret_cast<PersonImpl*>(&impl)->greet(name);  }

So let's address this issue with placement new operator & preallocated aligned memory buffer. reinterpret_cast is just compile-time substitute so there won't be any other indirection.

Benefits of Bridge Design Pattern

Bridge Design Pattern provides flexibility to develop abstraction(i.e. interface) and the implementation independently. And the client/API-user code can access only the abstraction part without being concerned about the Implementation part.
It preserves the Open-Closed Principle, in other words, improves extensibility as client/API-user code relies on abstraction only so implementation can modify or augmented any time.
By using the Bridge Design Pattern in the form of PIMPL. We can hide the implementation details from the client as we did in PIMPL idiom example above.
The Bridge Design Pattern is an application of the old advice, "prefer composition over inheritance" but in a smarter way. It comes handy when you must subclass different times in ways that are orthogonal with one another(say 2×2 problem discuss earlier).
A compile-time binding between an abstraction and its implementation should be avoided. So that an implementation can select at run-time.

Summary by FAQs

What is the practical use case of Bridge Design Pattern?

Plugins in any internet browser leverage this pattern directly where browser specifies only abstraction & implementation varies by different types of plugins.

When to use Bridge Design Pattern?

-- When you are unsure of implementation or its variations & still you want to move forward with development.
-- In case of a behaviour permutation problem i.e. Cartesian Product Complexity Explosion.

What are the differences between Adapter & Bridge Design Pattern?

-- Adapter is commonly used with an existing app to make some otherwise-incompatible classes work together nicely.
-- Bridge is usually designed up-front, letting you develop parts of an application independently of each other.

What are the differences between Strategy & Bridge Design Pattern?

-- Strategy is a single dimension problem like Multi-bit screwdriver.
-- Bridge is a multi-dimension problem like communication types & devices.

Adapter Design Pattern in Modern C++

Vishal Chovatiya — Mon, 17 Aug 2020 03:43:19 +0000

In software engineering, Structural Design Patterns deal with the relationship between object & classes i.e. how object & classes interact or build a relationship in a manner suitable to the situation. The structural design patterns simplify the structure by identifying relationships. In this article of the Structural Design Patterns, we're going to take a look at Adapter Design Pattern in Modern C++ which used to convert the interface of an existing class into another interface that client/API-user expect. Adapter Design Pattern makes classes work together that could not otherwise because of incompatible interfaces.

/!\: This article has been originally published on my blog. If you are interested in receiving my latest articles, please sign up to my newsletter.

By the way, If you haven't check out my other articles on Structural Design Patterns, then here is the list:

Adapter
Bridge
Composite
Decorator
Facade
Flyweight
Proxy

Note:

If you stumbled here directly, then I would suggest you go through What is design pattern? first, even if it is trivial. I believe it will encourage you to explore more on this topic.
All of this code you encounter in this series of articles are compiled using C++20(though I have used Modern C++ features up to C++17 in most cases). So if you don't have access to the latest compiler you can use https://wandbox.org/ which has preinstalled boost library as well.

Intent

To get the interface you want from the interface you have.

An adapter allows two incompatible classes to work together by converting the interface of one class into an interface expected by the client/API-user without changing them. Basically, adding intermediate class i.e. Adapter.
If you find yourself in a situation of using Adapter then you might be working on compatibility between libraries, modules, plugins, etc. If not then you might have serious design issues because, if you have followed Dependency Inversion Principle early in the design. Use of Adapter Design Pattern won't be the case.

Adapter Design Pattern Examples in C++

Implementing an Adapter Design Pattern is easy, just determine the API you have & the API you need. Create a component which aggregates(has a reference to,...) the adaptee.

Classical Adapter

struct Point {
    int32_t     m_x;
    virtual void draw(){ cout<<"Point\n"; }
};

struct Point2D : Point {
    int32_t     m_y;
    void draw(){ cout<<"Point2D\n"; }
};

void draw_point(Point &p) {
    p.draw();
}

struct Line {
    Point2D     m_start;
    Point2D     m_end;
    void draw(){ cout<<"Line\n"; }
};

struct LineAdapter : Point {
    Line&       m_line;
    LineAdapter(Line &line) : m_line(line) {}
    void draw(){ m_line.draw(); }
};

int main() {
    Line l;
    LineAdapter lineAdapter(l);
    draw_point(lineAdapter);
    return EXIT_SUCCESS;
}

You can also create a generic adapter by leveraging C++ template as follows:

template<class T>
struct GenericLineAdapter : Point {
    T&      m_line;
    GenericLineAdapter(T &line) : m_line(line) {}
    void draw(){ m_line.draw(); }
};

The usefulness of the generic approach hopefully becomes more apparent when you consider that when you need to make other things Point-like, the non-generic approach becomes quickly very redundant.

Pluggable Adapter Design Pattern using Modern C++

The Adapter should support the adaptees(which are unrelated and have different interfaces) using the same old target interface known to the client/API-user. Below example satisfy this property by using C++11's lambda function & functional header.

/* Legacy code -------------------------------------------------------------- */
struct Beverage {
    virtual void getBeverage() = 0;
};

struct CoffeeMaker : Beverage {
    void Brew() { cout << "brewing coffee" << endl;}
    void getBeverage() { Brew(); }
};

void make_drink(Beverage &drink){
    drink.getBeverage();                // Interface already shipped & known to client
}
/* --------------------------------------------------------------------------- */

struct JuiceMaker {                     // Introduced later on
    void Squeeze() { cout << "making Juice" << endl; }
};

struct Adapter : Beverage {              // Making things compatible
    function<void()>    m_request;

    Adapter(CoffeeMaker* cm) { m_request = [cm] ( ) { cm->Brew(); }; }
    Adapter(JuiceMaker* jm) { m_request = [jm] ( ) { jm->Squeeze(); }; }

    void getBeverage() { m_request(); }
};

int main() {
    Adapter adp1(new CoffeeMaker());
    make_drink(adp1);

    Adapter adp2(new JuiceMaker());
    make_drink(adp2);
    return EXIT_SUCCESS;
}

The pluggable adapter sorts out which object is being plugged in at the time. Once an object has been plugged in and its methods have been assigned to the delegate objects(i.e. m_request in our case), the association lasts until another set of methods is assigned.
What characterizes a pluggable adapter is that it will have constructors for each of the types that it adapts. In each of them, it does the delegate assignments (one, or more than one if there are further methods for rerouting).
Pluggable adapter provides the following two main benefits:
1. You can bind an interface(bypassing lambda function in constructor argument), unlike the object we did in the above example.
2. This also helps when adapter & adaptee have a different number of the argument.

Benefits of Adapter Design Pattern

Open-Closed Principle: One advantage of the Adapter Pattern is that you don't need to change the existing class or interface. By introducing a new class, which acts as an adapter between the interface and the class, you avoid any changes to the existing code.
This also limits the scope of your changes to your software component and avoids any changes and side-effects in other components or applications.
By above two-point i.e. separate class(i.e. Single Responsibility Principle) for special functionality & fewer side-effects, it's obvious we do requires less maintenance, learning curve & testing.
AdapterDesing Pattern also adheres to the Dependency Inversion Principle, due to which you can preserve binary compatibility between multiple releases.

Summary by FAQs

When to use the Adapter Design Pattern?

-- Use the Adapter class when you want to use some existing class, but its interface isn't compatible with the rest of your code.
-- When you want to reuse several existing subclasses that lack some common functionality that can't be added to the superclass.
-- For example, let say you have a function which accepts weather object & prints temperature in Celsius. But now you need to print the temperature in Fahrenheit. In this case of an incompatible situation, you can employ the Adapter Design Pattern.

Real-life & practical example of the Adapter Design Pattern?

-- In STL, stack, queue & priority_queue are adaptors from deque & vector. When stack executes stack::push(), the underlying vector does vector::push_back().
-- A card reader which acts as an adapter between the memory card and a laptop.
-- Your mobile & laptop charges are kind of adapter which converts standard voltage & current to the required one for your device.

What are the differences between Bridge & Adapter Design Pattern?

What is the difference between Decorator & Adapter Design Pattern?

-- Adapter converts one interface to another, without adding additional functionalities\
-- Decorator adds new functionality into an existing interface.

What is the difference between Proxy & Adapter Design Pattern?

-- Adapter Design Pattern translates the interface for one class into a compatible but different interface.
-- Proxy provides the same but easy interface or some time act as the only wrapper.

Introduction to Regular Expression With Modern C++

Vishal Chovatiya — Mon, 10 Aug 2020 03:46:46 +0000

Regular expressions (or regex in short) is a much-hated & underrated topic so far with Modern C++. But at the same time, correct use of regex can spare you writing many lines of code. If you have spent quite enough time in the industry. And not knowing regex then you are missing out on 20-30% productivity. In that case, I highly recommend you to learn regex, as it is one-time investment(something similar to learn once, write anywhere philosophy).

/!\: This article has been originally published on my blog. If you are interested in receiving my latest articles, please sign up to my newsletter.

Initially, In this article, I have decided to include regex-in-general also. But it doesn't make sense, as there is already people/tutorial out there who does better than me in teaching regex. But still, I left a small section to address Motivation & Learning Regex. For the rest of the article, I will be focusing on functionality provided by C++ to work with regex. And if you are already aware of regex, you can use the above mind-map as a refresher.

Pointer: The C++ standard library offers several different "flavours" of regex syntax, but the default flavour (the one you should always use & I am demonstrating here) was borrowed wholesale from the standard for ECMAScript.

Motivation

I know its pathetic and somewhat confusing tool-set. Consider the below regex pattern for an example that extract time in 24-hour format i.e. HH:MM.

\b([01]?[0-9]|2[0-3]):([0-5]\d)\b

I mean! Who wants to work with this cryptic text?
And whatever running in your mind is 100% reasonable. In fact, I have procrastinated learning regex twice due to the same reason. But, believe me, all the ugly looking things are not that bad.
The way(↓) I am describing here won't take more than 2-3 hours to learn regex that too intuitively. And After learning it you will see the compounding effect with return on investment over-the-time.

Learning Regex

Do not google much & try to analyse which tutorial is best. In fact, don't waste time in such analysis. Because there is no point in doing so. At this point in time(well! if you don't know the regex) what really matters is "Getting Started" rather than "What Is Best!".
Just go to https://regexone.com without much overthinking. And complete all the lessons. Trust me here, I have explored many articles, courses(<=this one is free, BTW) & books. But this is best among all for getting started without losing motivation.
And after it, if you still have an appetite to solve more problem & exercises. Consider the below links:
1. Exercises on regextutorials.com
2. Practice problem on regex by hackerrank

std::regex & std::regex_error Example

int main() {
    try {
        static const auto r = std::regex(R"(\)"); // Escape sequence error
    } catch (const std::regex_error &e) {
        assert(strcmp(e.what(), "Unexpected end of regex when escaping.") == 0);
        assert(e.code() == std::regex_constants::error_escape);
    }
    return EXIT_SUCCESS;
}

You see! I am using raw string literals. You can also use the normal string. But, in that case, you have to use a double backslash for an escape sequence.
The current implementation of std::regex is slow(as it needs regex interpretation & data structure creation at runtime), bloated and unavoidably require heap allocation(not allocator-aware). So, beware if you are using std::regex in a loop(see C++ Weekly -- Ep 74 -- std::regex optimize by Jason Turner). Also, there is only a single member function that I think could be of use is std::regex::mark_count() which returns a number of capture groups.
Moreover, if you are using multiple strings to create a regex pattern at run time. Then you may need exception handling i.e. std::regex_error to validate its correctness.

std::regex_search Example

int main() {
    const string input = "ABC:1->   PQR:2;;;   XYZ:3<<<"s;
    const regex r(R"((\w+):(\w+);)");
    smatch m;

    if (regex_search(input, m, r)) {
        assert(m.size() == 3);
        assert(m[0].str() == "PQR:2;");                // Entire match
        assert(m[1].str() == "PQR");                   // Substring that matches 1st group
        assert(m[2].str() == "2");                     // Substring that matches 2nd group
        assert(m.prefix().str() == "ABC:1->   ");      // All before 1st character match
        assert(m.suffix().str() == ";;   XYZ:3<<<");   // All after last character match

        // for (string &&str : m) { // Alternatively. You can also do
        //     cout << str << endl;
        // }
    }
    return EXIT_SUCCESS;
}

smatch is the specializations of std::match_results that stores the information about matches to be retrieved.

std::regex_match Example

Short & sweet example that you may always find in every regex book is email validation. And that is where our std::regex_match function fits perfectly.

bool is_valid_email_id(string_view str) {
    static const regex r(R"(\w+@\w+\.(?:com|in))");
    return regex_match(str.data(), r);
}

int main() {
    assert(is_valid_email_id("vishalchovatiya@ymail.com") == true);
    assert(is_valid_email_id("@abc.com") == false);
    return EXIT_SUCCESS;
}

I know this is not full proof email validator regex pattern. But my intention is also not that.
Rather you should wonder why I have used std::regex_match! not std::regex_search! The rationale is simple std::regex_match matches the whole input sequence.
Also, Noticeable thing is static regex object to avoid constructing ("compiling/interpreting") a new regex object every time the function entered.
The irony of above tiny code snippet is that it produces around 30k lines of assembly that too with -O3 flag. And that is ridiculous. But don't worry this is already been brought to the ISO C++ community. And soon we may get some updates. Meanwhile, we do have other alternatives (mentioned at the end of this article).

Difference Between std::regex_match & std::regex_search?

You might be wondering why do we have two functions doing almost the same work? Even I had the doubt initially. But, after reading the description provided by cppreference over and over. I found the answer. And to explain that answer, I have created the example(obviously with the help of StackOverflow):

int main() {
    const string input = "ABC:1->   PQR:2;;;   XYZ:3<<<"s;
    const regex r(R"((\w+):(\w+);)");
    smatch m;

    assert(regex_match(input, m, r) == false);

    assert(regex_search(input, m, r) == true && m.ready() == true && m[1] == "PQR");

    return EXIT_SUCCESS;
}

std::regex_match only returns true when the entire input sequence has been matched, while std::regex_search will succeed even if only a sub-sequence matches the regex.

std::regex_iterator Example

std::regex_iterator is helpful when you need very detailed information about matched & sub-matches.

#define C_ALL(X) cbegin(X), cend(X)

int main() {
    const string input = "ABC:1->   PQR:2;;;   XYZ:3<<<"s;
    const regex r(R"((\w+):(\d))");

    const vector<smatch> matches{
        sregex_iterator{C_ALL(input), r},
        sregex_iterator{}
    };

    assert(matches[0].str(0) == "ABC:1" 
        && matches[0].str(1) == "ABC" 
        && matches[0].str(2) == "1");

    assert(matches[1].str(0) == "PQR:2" 
        && matches[1].str(1) == "PQR" 
        && matches[1].str(2) == "2");

    assert(matches[2].str(0) == "XYZ:3" 
        && matches[2].str(1) == "XYZ" 
        && matches[2].str(2) == "3");

    return EXIT_SUCCESS;
}

Earlier(in C++11), there was a limitation that using std::regex_interator is not allowed to be called with a temporary regex object. Which has been rectified with overload from C++14.

std::regex_token_iterator Example

std::regex_token_iterator is the utility you are going to use 80% of the time. It has a slight variation as compared to std::regex_iterator. The difference between std::regex_iterator & std::regex_token_iterator is
- std::regex_iterator points to match results.
- std::regex_token_iterator points to sub-matches.
In std::regex_token_iterator, each iterator contains only a single matched result.

#define C_ALL(X) cbegin(X), cend(X)

int main() {
    const string input = "ABC:1->   PQR:2;;;   XYZ:3<<<"s;
    const regex r(R"((\w+):(\d))");

    // Note: vector<string> here, unlike vector<smatch> as in std::regex_iterator
    const vector<string> full_match{
        sregex_token_iterator{C_ALL(input), r, 0}, // Mark `0` here i.e. whole regex match
        sregex_token_iterator{}
    };
    assert((full_match == decltype(full_match){"ABC:1", "PQR:2", "XYZ:3"}));

    const vector<string> cptr_grp_1st{
        sregex_token_iterator{C_ALL(input), r, 1}, // Mark `1` here i.e. 1st capture group
        sregex_token_iterator{}
    };
    assert((cptr_grp_1st == decltype(cptr_grp_1st){"ABC", "PQR", "XYZ"}));

    const vector<string> cptr_grp_2nd{
        sregex_token_iterator{C_ALL(input), r, 2}, // Mark `2` here i.e. 2nd capture group
        sregex_token_iterator{}
    };
    assert((cptr_grp_2nd == decltype(cptr_grp_2nd){"1", "2", "3"}));

    return EXIT_SUCCESS;
}

Inverted Match With std::regex_token_iterator

#define C_ALL(X) cbegin(X), cend(X)

int main() {
    const string input = "ABC:1->   PQR:2;;;   XYZ:3<<<"s;
    const regex r(R"((\w+):(\d))");

    const vector<string> inverted{
        sregex_token_iterator{C_ALL(input), r, -1}, // `-1` = parts that are not matched
        sregex_token_iterator{}
    };
    assert((inverted == decltype(inverted){
                            "",
                            "->   ",
                            ";;;   ",
                            "<<<",
                        }));

    return EXIT_SUCCESS;
}

std::regex_replace Example

string transform_pair(string_view text, regex_constants::match_flag_type f = {}) {
    static const auto r = regex(R"((\w+):(\d))");
    return regex_replace(text.data(), r, "$2", f);
}

int main() {
    assert(transform_pair("ABC:1, PQR:2"s) == "1, 2"s);

    // Things that aren't matched are not copied
    assert(transform_pair("ABC:1, PQR:2"s, regex_constants::format_no_copy) == "12"s);
    return EXIT_SUCCESS;
}

You see in 2nd call of transform_pair, we passed flag std::regex_constants::format_no_copy which suggest do not copy thing that isn't matched. There are many such useful flags under std::regex_constant.
Also, we have constructed the fresh string holding the results. But what if we do not want a new string. Rather wants to append the results directly to somewhere(probably container or stream or already existing string). Guess what! the standard library has covered this also with overloaded std::regex_replace as follows:

int main() {
    const string input = "ABC:1->   PQR:2;;;   XYZ:3<<<"s;
    const regex r(R"(-|>|<|;| )");

    // Prints "ABC:1     PQR:2      XYZ:3   "
    regex_replace(ostreambuf_iterator<char>(cout), C_ALL(input), r, " ");

    return EXIT_SUCCESS;
}

Use Cases

Splitting a String With Delimiter

Although std::strtok is best suitable & optimal candidate for such a task. But just to demonstrate how you can do it with regex:

#define C_ALL(X) cbegin(X), cend(X)

vector<string> split(const string& str, string_view pattern) {
    const auto r = regex(pattern.data());
    return vector<string>{
        sregex_token_iterator(C_ALL(str), r, -1),
        sregex_token_iterator()
    };
}

int main() {
    assert((split("/root/home/vishal", "/")
                == vector<string>{"", "root", "home", "vishal"}));
    return EXIT_SUCCESS;
}

Trim Whitespace From a String

string trim(string_view text) {
    static const auto r = regex(R"(\s+)");
    return regex_replace(text.data(), r, "");
}

int main() {
    assert(trim("12   3 4      5"s) == "12345"s);
    return EXIT_SUCCESS;
}

Finding Lines Containing or Not Containing Certain Words From a File

string join(const vector<string>& words, const string& delimiter) {
    return accumulate(next(begin(words)), end(words), words[0],
            [&delimiter](string& p, const string& word)
            {
                return p + delimiter + word;
            });
}

vector<string> lines_containing(const string& file, const vector<string>& words) {
    auto prefix = "^.*?\\b("s;
    auto suffix = ")\\b.*$"s;

    //  ^.*?\b(one|two|three)\b.*$
    const auto pattern = move(prefix) + join(words, "|") + move(suffix);

    ifstream        infile(file);
    vector<string>  result;

    for (string line; getline(infile, line);) {
        if(regex_match(line, regex(pattern))) {
            result.emplace_back(move(line));
        }
    }

    return result;
}

int main() {
   assert((lines_containing("test.txt", {"one","two"})
                                        == vector<string>{"This is one",
                                                          "This is two"}));
    return EXIT_SUCCESS;
}
/* test.txt
This is one
This is two
This is three
This is four
*/

Same goes for finding lines that are not containing words with the pattern ^((?!(one|two|three)).)*$.

Finding Files in a Directory

namespace fs = std::filesystem;

vector<fs::directory_entry> find_files(const fs::path &path, string_view rg) {
    vector<fs::directory_entry> result;
    regex r(rg.data());
    copy_if(
        fs::recursive_directory_iterator(path),
        fs::recursive_directory_iterator(),
        back_inserter(result),
        [&r](const fs::directory_entry &entry) {
            return fs::is_regular_file(entry.path()) &&
                   regex_match(entry.path().filename().string(), r);
        });
    return result;
}

int main() {
    const auto dir        = fs::temp_directory_path();
    const auto pattern    = R"(\w+\.png)";
    const auto result     = find_files(fs::current_path(), pattern);
    for (const auto &entry : result) {
        cout << entry.path().string() << endl;
    }
    return EXIT_SUCCESS;
}

Tips For Using Regex-In-General

Use raw string literal for describing the regex pattern in C++.
Use the regex validating tool like https://regex101.com. What I like about regex101 is code generation & time-taken(will be helpful when optimizing regex) feature.
Also, try to add generated explanation from validation tool as a comment exactly above the regex pattern in your code.
Performance:
- If you are using alternation, try to arrange options in high probability order like com|net|org.
- Try to use lazy quantifiers if possible.
- Use non-capture groups wherever possible.
- Disable Backtracking.
- Using the negated character class is more efficient than using a lazy dot.

Parting Words

It's not just that you will use regex with only C++ or any other language. I myself use it mostly on IDE(in vscode to analyse log files) & on Linux terminal. But, bear in mind that overusing regex gives the feel of cleverness. And, it's a great way to make your co-workers (and anyone else who needs to work with your code) very angry with you. Also, regex is overkill for most parsing tasks that you'll face in your daily work.

The regexes really shine for complicated tasks where hand-written parsing code would be just as slow anyway; and for extremely simple tasks where the readability and robustness of regular expressions outweigh their performance costs.

One more notable thing is current regex implementation(till 19th June 2020) in standard libraries have performance & code bloating issues. So choose wisely between Boost, CTRE and Standard library versions. Most probably you might go with the Hana Dusíková's work on Compile Time Regular Expression. Also, her CppCon talk from 2018 & 2019's would be helpful especially if you plan to use regex in embedded systems.

Using std::map Wisely With Modern C++

Vishal Chovatiya — Mon, 03 Aug 2020 04:31:00 +0000

std::map and its siblings(std::multimap, std::unordered_map/multimap) used to be my favourite containers when I was doing competitive programming. In fact, I still like them(though using less frequently nowadays). And with Modern C++, we now have more reasons to use std::map. That's why I have decided to address this topic by writing an article summarizing these new features. So, without much gibberish, let's dive-in directly.

/!\: This article has been originally published on my blog. If you are interested in receiving my latest articles, please sign up to my newsletter.

std::map::contains(C++20)

std::map::contains member function is a good step towards code expressiveness. And I am also tire of writing :

if (auto search = freq_of.find(2); search != freq_of.end()) {
    cout << "Found" << endl;
}
// Where assume, freq_of = map<uint32_t, uint32_t>{{3, 1}, {1, 1}, {2, 1}};

Rather, from C++20, you can write:

if (freq_of.contains(2)) {
    cout << "Found" << endl;
}

The code we write is written first for human consumption & only secondarily for the computer to understand.

- John Sonmez

std::map::try_emplace(C++17)

While inserting into the map, we have 2 different possibilities:
1. The key doesn't exist yet. Create a fresh key-value pair.
2. The key does exist already. Take the existing item and modify it.
A typical approach to insert an element in std::map is by using operator[ ], std::map::insert or std::map::emplace . But, in all of these cases, we have to bear the cost of default/specialized constructor or assignment call. And the worst part is if an item already exists, we have to drop the freshly created item.

int main() {
    vector v{3, 4, 5, 8, 7, 3, 5, 2, 4};
    map<uint32_t, uint32_t> freq_of;

    for (const auto &n : v) {
        if (const auto &[it, inserted] = freq_of.emplace(n, 1); !inserted) {
            it->second++;  // Exists already
        }
    }

    assert(freq_of[3] == 2);

    return EXIT_SUCCESS;
}

Instead:

if (const auto &[it, inserted] = freq_of.try_emplace(n, 1); !inserted) {
    it->second++;
}

But, since C++17, there is this std::map::try_emplace method that creates items only if the key doesn't exist yet. This boosts the performance in case objects of that type are expensive to create.
Although the above example hasn't showcased the expensive to create items. But, yes! whenever you encounter such a situation, must be known how to handle it with std::map::try_emplace.

std::map::insert_or_assign(C++17)

When you have to insert element anyhow. For the sake of convenience, you use std::map::operator[ ]. Which is OK( and dangerous)! Unless you have any constraint on insertion or assignment.
For example, while counting the frequency of elements with the added constraint that when an element is repeated(i.e. assigned) you have to remove all the element lesser than the current one.
In such a situation, std::map::operator[ ] isn't feasible. Rather, std::map::insert_or_assign is more appropriate and returns more information than std::map::operator[ ]. It also does not require default-constructibility of the mapped type. Consider the following example for the same.

int main() {
    vector v{8, 3, 9, 5, 8};
    map<uint32_t, uint32_t> freq_of;

    for (auto &&n : v) {
        const auto &[it, is_inserted] = freq_of.insert_or_assign(n, 1);

        if (!is_inserted) { // remove all lesser element then current one if repeated
            freq_of.erase(begin(freq_of), it);
        }
    }

    assert((freq_of == decltype(freq_of){
                           {8, 1},
                           {9, 1},
                       }));

    return EXIT_SUCCESS;
}

std::map::insert With Hint(C++11/17)

Looking up items in an std::map takes O(log(n)) time. This is the same for inserting new items. Because the position where to insert them must looked up. Naive insertion of M new items would thus take O(M * log(n)) time.
In order to make this more efficient, std::map insertion functions accept an optional insertion hint parameter. The insertion hint is basically an iterator, which points near the future position of the item that is to be inserted. If the hint is correct, then we get amortized O(1) insertion time.
This is quite useful from a performance point of view when the insertion sequence of items is somewhat predictable. For example:

int main() {
    map<uint32_t, string> m{{2, ""}, {3, ""}};
    auto where(end(m));

    for (const auto &n : {8, 7, 6, 5, 4, 3, 2, 1}) { // Items in non-incremental order
        where = m.insert(where, {n, ""});
    }

    // How it is not done!
    // m.insert(end(m), {0, ""});

    for (const auto &[key, value] : m) {
        cout << key << " : " << value << endl;
    }

    return EXIT_SUCCESS;
}

A correct hint will point to an existing element, which is greater than the element to be inserted so that the newly inserted key will be just before the hint. If this does not apply for the hint the user provided during insertion, the insert function will fall back to a nonoptimized insertion, yielding O(log(n)) performance again.
For the above example, the first insertion, we got the end iterator of the map, because we had no better hint to start with. After installing an 8 in the tree, we knew that installing 7 will insert a new item just in front of the 8, which qualified it to be a correct hint. This applies to 6 as well, if put into the tree after inserting the 7, and so on. This is why it is possible to use the iterator, which was returned in the last insertion for the next insertion.
You can play around the above example to justify the performance gain with quick-benchmark.

**Note:* It is important to know that before C++11, insertion hints were considered correct when they pointed before the position of the newly inserted item.*

std::map::merge(C++17)

Same as std::list:splice, which transfers the elements from one list to another. we have std::map::merge which can merge the two same type of std::map.

int main() {
    map<uint32_t, string> fruits{{5, "grapes"}, {2, "tomoto"}};
    map<uint32_t, string> person{{2, "mickel"}, {10, "shree"}};
    map<uint32_t, string> fruits_and_persons;

    fruits_and_persons.merge(fruits);
    assert(fruits.size() == 0);

    fruits_and_persons.merge(person);
    assert(person.size() == 1);
    assert(person.at(2) == "mickel"); // Won't overwrite value at 2 i.e.`mickel`

    assert((fruits_and_persons == decltype(fruits){
                                      {2, "tomoto"},
                                      {5, "grapes"},
                                      {10, "shree"},
                                  }));

    return EXIT_SUCCESS;
}

The thing here to note is what happens when there are duplicates! The duplicated elements are not transferred. They're left behind in the right-hand-side map.

std::map::extract(C++17)

Unlike std::map::merge that transfers the elements in bulk, std::map::extract along with std::map::insert transfers element piecewise. But what is the more compelling application of std::map::extract is modifying keys.
As we know, for std::map keys are always unique and sorted. Hence, It is crucial that users cannot modify the keys of map nodes that are already inserted. In order to prevent the user from modifying the key items of perfectly sorted map nodes, the const qualifier is added to the key type.
This kind of restriction is perfectly valid because it makes harder for the user to use std::map the wrong way. But what if we really need to change the keys of some map items?
Prior to C++17, we had to remove & reinsert the items in order to change the key. The downside of this approach is memory allocation & deallocation, which sounds bad in terms of performance. But, from C++17, we can remove & reinsert std::map nodes without any reallocation of memory.

int main() {
    map<int, string> race_scoreboard{{1, "Mickel"}, {2, "Shree"}, {3, "Jenti"}};
    using Pair = map<int, string>::value_type;

    {
        auto Jenti(race_scoreboard.extract(3));
        auto Mickel(race_scoreboard.extract(1));

        swap(Jenti.key(), Mickel.key());

        auto [it, is_inserted, nh] = race_scoreboard.insert(move(Jenti)); // nh = node handle
        assert(*it == Pair(1, "Jenti") && is_inserted == true && nh.empty());

        race_scoreboard.insert(move(Mickel));
    }

    assert((race_scoreboard == decltype(race_scoreboard){
                                   {1, "Jenti"},
                                   {2, "Shree"},
                                   {3, "Mickel"},
                               }));

    return EXIT_SUCCESS;
}

Consider the above example of the racing scoreboard where you have employed std::map to imitate the racing position. And after a while, Jenti took the lead & Mickel left behind. In this case, how we have switched the keys(position on a race track) of those players.
std::map::extract comes in two flavours:

node_type extract(const_iterator position);
node_type extract(const key_type& x);

In the above example, we used the second one, which accepts a key and then finds & extracts the map node that matches the key parameter. The first one accepts an iterator, which implies that it is faster because it doesn't need to search for the item.

What If the Node With a Particular Key Does Not Exist?

If we try to extract an item that doesn't exist with the second method (the one that searches using a key), it returns an empty node_type instance i.e. node handle. The empty() member method or overloaded bool operator tells us that whether a node_type instance is empty or not.

OK! Then How Do I Modify std::map Keys?

After extracting nodes, we were able to modify their keys using the key() method, which gives us non-const access to the key, although keys are usually const.
Note that in order to reinsert the nodes into the map again, we had to move them into the insert function. This makes sense because the extract is all about avoiding unnecessary copies and allocations. Moreover, while we move a node_type instance, this does not result in actual moves of any of the container values.

Can I Modify Associated Values in std::map Also?

Yes! You can use the accessor methods nh.mapped()(instead of nh.key()) to manipulate the pieces of the entry in a std::map (or nh.value() for the single piece of data in an element of a std::set). Thus you can extract, manipulate, and reinsert a key without ever copying or moving its actual data.

But What About Safety?

If you extract a node from a map and then throw an exception before you've managed to re-insert it into the destination map.
A node handle's destructor is called and will correctly clean up the memory associated with the node. So, technically std::map::extract by-default(without insert) will act as std::map::erase!

There Is More! Interoperability

Map nodes that have been extracted using the std::map::extract are actually very versatile. We can extract nodes from a map instance and insert it into any other map or even multimap instance.
It does also work between unordered_map and unordered_multimap instances, as well as with set/multiset and respective unordered_set/unordered_multiset.
In order to move items between different map/set structures, the types of key, value and allocator need to be identical.

Difference Between operator[ ] vs insert() vs at()

This is trivial for experienced devs but, still I want to go over it quickly.

std::map::operator[ ]

Operation: find-or-add; try to find an element with the given key inside the map, and if it exists it will return a reference to the stored value. If it does not, it will create a new element inserted in place with default initialization and return a reference to it.
Applicability:
- Not usable for const std::map, as it will create the element if it doesn't exist.
- Not suitable for value type that does not default constructible and assignable(in layman term, doesn't have default constructor & copy/move constructor).
When key exists: Overwrites it.

std::map::insert

Operation: insert-or-nop; accepts a value_type (std::pair) and uses the key(first member) and to insert it. Asstd::map does not allow for duplicates, if there is an existing element it will not insert anything.
Applicability:
- Liberty in calling insert different ways that require the creation of the value_type externally and the copy of that object into the container.
- Highly applicable when item insertion sequence is somewhat predictable to gain the performance.
When key exists: Not modify the state of the map, but instead return an iterator to the element that prevented the insertion.

std::map::at

Operation: find-or-throw; returns a reference to the mapped value of the element with key equivalent to input key. If no such element exists, an exception of type std::out_of_range is thrown.
Applicability:
- Not recommended using at() when accessing const maps and when element absence is a logic error.
- Yes, it's better to use std::map::find() when you're not sure element is there. Because, throwing and catching std::logic_error exception will not be a very elegant way of programming, even if we don't think about performance.
When key exists: returns a reference to mapped value.

Parting Words

If you see the table of content for this article above, more than half of the member functions are around inserting the elements into the map. To the newbie, this is the reason for anxiety(or standard committee would say modernness). But if you account for the new features & complexity of language those are pretty much justified. BTW, this modernness doesn't stop here, we do have other specialization also available for map like std::swap(C++17), std::erase_if(C++20) & bunch of comparison operators.

DEV Community: Vishal Chovatiya

C++20 Coroutine: Under The Hood

What Is Coroutine In General?

What Is C++20 Coroutine?

Why Do You Even Need Coroutine?

Understanding C++20 Coroutine With Examples

Suspending a Coroutine

Returning a Value From Coroutine

Yielding a Value From Coroutine

Generating Integer Sequence Using C++20 Coroutine

C++20 Coroutine Terminology

Awaitable

Awaiter

co_await

Promise

Coroutine Handle

Coroutine State

How Does Coroutine Gets Executed!

Hypothesis 1

Hypothesis 2

Summary

Subroutine vs Coroutine

Compiler Transformation Of Coroutine Related Keywords

Parting Words With FAQs

Implementation of Coroutine in C Language

Prerequisites

Coroutine Basics

What Is Coroutine?

Why Do We Need Coroutine?

To-the-point Context Switching API Theory

Data Strucutre To Store Execution Context

int setcontext(const ucontext_t *ucp)

int getcontext(ucontext_t *ucp)

void makecontext(ucontext_t *ucp, void (*func)(), int argc, ...)

int swapcontext(ucontext_t *oucp, ucontext_t *ucp)

[Example 1]: Understanding Context Switching With setcontext & getcontext Functions

[Example 2]: Understanding Control Flow With makecontext & swapcontext Functions

Coroutine in C Language

coroutine.h

coroutine.c

Coroutine Lifetime

Coroutine Usage Example

coroutine_example.c

Compiling

Parting Words

Chain of Responsibility Design Pattern in Modern C++

Intent

Classic Examples for Chain of Responsibility Design Pattern in C++

Boost Example for Chain of Responsibility Design Pattern

Benefits of Chain of Responsibility Design Pattern

Summary by FAQs

Proxy Design Pattern in Modern C++

Intent

Proxy Design Pattern Examples in C++

Property Proxy

Virtual Proxy

Communication Proxy(Intuitive Proxy Design Pattern in C++)

Benefits of Proxy Design Pattern

Summary by FAQs

Flyweight Design Pattern in Modern C++

Intent

Flyweight Design Pattern Example in C++

Implementing Flyweight Design Pattern using Boost

Benefits of Flyweight Design Pattern

Summary by FAQs

Facade Design Pattern in Modern C++

Intent

Facade Design Pattern Example in C++

Benefits of Facade Design Pattern

Summary by FAQs

Decorator Design Pattern in Modern C++

Intent

Decorator Design Pattern Examples in C++

Dynamic Decorator

Limitation of Dynamic Decorator

Static Decorator

Functional Approach to Decorator Design Pattern using Modern C++

Benefits of Decorator Design Pattern

Summary by FAQs

Composite Design Pattern in Modern C++

`co_await`

`int setcontext(const ucontext_t *ucp)`

`int getcontext(ucontext_t *ucp)`

`void makecontext(ucontext_t ucp, void (func)(), int argc, ...)`

`int swapcontext(ucontext_t oucp, ucontext_t ucp)`

[Example 1]: Understanding Context Switching With `setcontext` & `getcontext` Functions

[Example 2]: Understanding Control Flow With `makecontext` & `swapcontext` Functions

`coroutine.h`

`coroutine.c`

`coroutine_example.c`