C++ Lambda Idioms

The closure type for a lambda-expression has a public inline function call operator(for a non-generic lambda) or function call operator template (for a generic lambda) whose parameters and return type are described by the lambda-expression‘s parameter-declaration-clause and trailing-returning-type respectively, and whose template-parameter-list consists of the specified template-parameter-list, if any. The requires-clause of the function call operator template is the requires-clause immediately following < template-parameter-list >, if any. The trailing requires-clause of the function call operator or operator template is the requires-clause of the lambda-declarator, if any.

[](const Person &lhs, const Person &rhs) {
  return lhs.name < rhs.name;
};

The version after compiled.

• Lambda has no default noexcept attribute, if you want the call operator to be noexcept, you have to write noexcept keyword.

struct __lambda_1 {
  inline bool operator()(const Person &lhs,
                         const Person &rhs) const {
    return lhs.name < rhs.name;
  };
  
  // not default-constructible!
  __lambda_1() = delete;
  // not assignable!
  __lambda_1& operator=(const __lambda_1&) = delete;
};

// call a lambda
// this instance is auto-generated by the
// compiler, so no error.
__lambda_1();

Do not capture anything.

Lambdas do not have a state, so if the [] is empty, the lambda have an implicit conversion to raw function pointer. So we have some kind of legacy call here like C APIs do that very often they take a raw function pointer.

void legacy_call(int(*f)(int)) {
  std::cout << f(7) << '\n';
}

int main() {
  // OK, implicit conversion to function pointer.
  legacy_call([](int i) {
    return i * i;
  }); // prints 49
  
}

Something like this: __func_type.

struct __lambda_1 {
  inline bool operator()(const Person& lhs,
                         const Person& rhs) const {
    return lhs.name < rhs.name;
  };
  
  // not default-constructible
  __lambda_1() = delete;
  // not copyable or assignable!
  __lambda_1& operator=(const __lambda_1&) = delete;
  
  using __func_type = bool(*)(const Person&,
                              const Person&);
  inline operator __func_type() const noexcept {
    return &__invoke;
  }
  
private:
  static inline bool __invoke(const Person& lhs,
                              const Person& rhs) {
    return lhs.name < rhs.name;
  }
};

Idiom 1: Unary Plus Trick

DO NOT USE THIS IN PRODUCTION CODE.

It’s kind of really interesting it teaches us something about lambda does work. We’ve already known that no-capturing lambda would implicitly convert to function pointer but what if we need explicit conversion to function pointer?

int main() {
  // this will introduce error since compiler cannot
  // deduce auto * type from i * i.
  auto *fptr = [](int i) { return i * i; };
  
  // So we can use static_cast for explicitly casting.
  auto *fptr = static_cast<int(*)(int)>([](int i) {
    return i * i;
  });
  
  // 
  auto *fptr = +[](int i) { return i * i; }
}

The unary operator is obviously not defined for lambdas. However, the unary plus operator is defined for pointers including pointers to function. So if the compiler sees the unary plus operator, it says okay well that only works for pointers, therefore I’m going to implicitly convert this to a pointer. So your lambda is going to be implicitly converted to function pointer, and then a unary plus operator is going to be applied to that function pointer. And what does the unary plus operator do? When it applies to a pointer, nothing will do exactly. So all it does is it’s going to static_cast the lambda to a function pointer.

Lambda Captures

Capture is when you capture a variable from the scope where the lambda expression is. So it means the lambda now has states.

Capture by Value

int i = 0;
int j = 0;
auto f = [=] { reutrn i == j; };

After compiled:

struct __lambda_2 {
  __lambda_2(int i, int j) : __i(i), __j(j) {}
  inline bool operator()() const {
    return __i == __j;
  }
  
private:
  int __i;
  int __j;
};

__lambda_2(i, j);

When the lambda captures two variables i and j, then compiler is going to add two private members data non-static data members to your closure type, and it’s going to initialize those data members with the values of the variables that you have captured. For each entity captured by copy, an unnamed non-static data member is declared in the closure type. The declaration order of these members is unspecified.

Capture by Reference

When you capture by reference.

int i = 0;
int j = 0;
auto f = [&] { reutrn i == j; };

After compiled:

struct __lambda_2 {
  __lambda_2(int &i, int &j) : __i(i), __j(j) {}
  inline bool operator()() const {
    return __i == __j;
  }
  
private:
  int &__i;
  int &__j;
};

__lambda_2(i, j);

When the lambda captures two variables i and j by reference, then compiler will add two private reference members. An entity is captured by reference if it is implicitly or explicitly captured but not captured by copy. It is unspecified whether additional unnamed non-static data members are declared in the closure type for entities captured by reference. If declared, such non-static data member shall be of literal type.

Capture this

struct X {
  void printAsync() {
    callAsync([this] {
      std::cout << i << '\n';
    });
  }
  
private:
  int i = 42;
};

After compiled:

struct X {
  void printAsync() {
    struct __lambda_3 {
      __lambda_3(X* _this) : __this(_this) {}
      void operator()() const {
        std::cout << __this->i << '\n';
      }
      
    private:
      X* __this;
    };
    callAsync(__lambda_3(this));
  }
  
private:
  int i = 42;
};

If you capture this, then you get to call members and member functions that object that you are in so that you can have lambda inside a member function of a class and just naturally refer to other members of that class inside that.

Lambda Capture Gotchas

One really important thing is that you can only capture local variables. For example, you can not capture the static variable i.

int main() {
  static int i = 42;
  // This capture fails since lambda cannot capture
  // non-static variables.
  auto f = [=] { ++i; };
  f();
  
  return i; // return 43!
}

You actually don’t capture global variable, you are just accessing it. For example, the code is as follows,

int i = 42;

int main() {
  auto f = [] { ++i; };
  f();
  
  return i; // return 43!
}

You also don’t capture variables even if they are local if the lambda doesn’t ODR use them. You only capture the things that are ODR used inside the lambda. ODR are used is kind of a term from the standards you can again look it up what it means exactly.

Such as the following case, the lambda expression uses constexpr variable. Because the constexpr is a compile-time expression that is not an ODR use of the variable, that means you don’t have to capture I. So again, the capture is empty, but you can use i for printing. However, if you want to take the address of that variable

int main() {
  constexpr int i = 42;
  // OK: 'i' is not odr-used
  auto f = [] { std::cout << i << '\n'; };
  f();
}

int main() {
  constexpr int i = 42;
  // ERROR: `i` is odr-used but not captured.
  auto f = [] { std::cout << &i << '\n'; };
  f();
}

Besides, const int variable also can not be captured by lambda expression since const is implicit constexpr.

int main() {
  const int i = 42;
  // ERROR: `i` is odr-used but not captured.
  auto f = [] { std::cout << &i << '\n'; };
  f();
}

If it has a const float not an integer type, therefore, this logic doesn’t apply. You must capture it if you want to use it inside the lambda.

int main() {
  const float f = 42;
  // ERROR: `f` is not captured.
  []{ std::cout << f << '\n'; }();
}

The right way to use const float variable inside the lambda is as follows.

int main() {
  const float f = 42;
  // OK: `f` should be captured explicitly.
  [&f] { std::cout << f << '\n'; }();
}

Idiom 2: Immediately Invoked Function Expressions (IIFE)

This idiom is so useful and it’s really practice and I think it can be useful in many situations. For example:

What is Immediately Invoked Function Expressions? We don’t necessarily have to assign a lambda expression to a variable. So if we have a lambda expression hever, we can also instead just call it right there. This immediately invoked lambda are really useful.

int main() {
  [] { std::cout << "Hello world\n"; }();
}

The following code is not a good practice for foo variable initialization. This if-else statement may introduce undefined behavior. Besides, if Foo class is not default-constructible, this code may not be compiled. The third issue is that if const Foo foo, we cannot assign to a const object using if-else statement. In java, if we use final keyword, this means foo variable is only be assigned once, so the following code could be compiled in java. But in C++, the const keyword means you only get to initialize it once and it has to be at the point where you declare it. So we have problem if we declare foo as const.

int main() {
  // some code...
  const Foo foo; // Foo does not have default-constructible.
  
  if (hasDatabase) {
    // Error: cannot assign to const object.
    foo = getFooFromDatabase();
  } else {
    // Error: cannot assign to const object.
    foo = getFooFromElsewhere();
  }
}

Without lambda, we can use following method to solve this problem. But the code like this is ugly and unreadable.

int main() {
  const Foo foo = hasDatabase ?
      ? getFooFromDatabase()
      : getFooFromElsewhere();
}

The other method is that we can extract foo initialization process into a real function. This can split logic into other function, and initialization process is not localization anymore. If the initialization depends on local variables, you now have to pass these local variables as a parameter to function. So it all just gets messy.

Foo getFoo() {
  if (hasDatabase)
    return getFooFromDatabase();
  else
    return getFooFromElsewhere();
}

int main() {
  // some code...
  const Foo foo = getFoo();
}

If we use lambda, it should be great. Using immediately invoked lambda, you can just assign return value to foo, and this solves the problem. This also gets benefits for make_shared/make_unique all of that stuff.

int main() {
  // some code...
  const Foo foo = [&] {
    if (hasDatabase)
      return getFooFromDatabase();
    else
      return getFooFromElsewhere();
  }(); // immediately invoke lambda.
}

Using std::invoke function, it takes a function and calls it right away. This looks a little bit more visible because it’s like right there in the beginning. You actually could do more cool stuff with these immediately invoked lambdas.

int main() {
  // some code...
  std::vector<Foo> foos;
  foos.emplace_back(std::invoke([] { // since C++17
    if (hasDatabase)
      return getFooFromDatabase();
    else
      return getFooFromElsewhere();
  }));
}

Idiom 3: Call-Once Lambda

Daisy Hollman: “What you can learn from being too cute.”

For example, here you have some kind of struct X and has a constructor. And you want to run this code when you construct an object but only once, and then never again. When we have more than one initialization calls, we still want this code bo only be called at the first time and never again. How you will do this?

struct X {
  X() { std::cout << "Called once!\n"; }
};

int main() {
  X x1;
  X x2;
  X x3;
  
}

Using static immediately invoked lambda, you can exactly only execute constructor once. Since C++11 if you initialize a static object, it’s guaranteed to be initialized exactly once. And this initialization is also thread safe. So which means you can actually initialize these X objects from multiple threads simultaneously, and you will still only call this constructor only once, and it’s going to be thread-safe. So the compiler will insert invisible locks to make sure it’s all thread-safe and to make sure that this code is only going to be called only once. There is one caveat here which is if you run this constructor a second time, there will be an implicit check which is some kind of atomic flag whether this has already been called yet in order to make sure that it’s not going to be called again. So this is going to be a little bit of a runtime overhead.

struct X {
  X() {
    static auto _ = [] {
      std::cout << "Called once!\n"; return 0;
    }
  };();
};

int main() {
  X x1;
  X x2;
  X x3;
  
}

C++14 Generic Lambdas

We can use auto keyword as lambda’s parameter type. This is really cool because the compiler is going to deduce the type for us.

std::map<int, std::string> httpErrors = {
    {400, "Bad Request"},
    {401, "Unauthorised"},
    {403, "Forbidden"},
    {404, "Not Found"},
};

std::for_each(
    httpErrors.begin(), httpErrors.end(),
    [](const auto &item) {
      std::cout << item.first << ':'
                << item.second << '\n';
    });

For example, if we have the following lambda code like this.

[](auto i) {
  std::cout << i << '\n';
}

After compiled this code, you may get the following closure.

struct __lambda_6 {
  template <typename T>
  void operator()(T i) const {
    std::cout << i << '\n';
  }
  
  template <typename T>
  using __func_type = void(*)(T i);
  
  template <typename T>
  inline operator __func_type<T>() const noexcept {
    return &__invoke<T>;
  }
  
private:
  template <typename T>
  static void __invoke(T i) {
    std::cout << i << '\n';
  }
};
__lambda_6();

So if you write generic lambda, it creates a call operator which is a function template.

Besides, if your lambda does not capture anyone, you can still get the implicit conversion to function pointer. But now that conversion operator is also going to be a template.

However, the + operator doesn’t work anymore because the compiler literally does not know what type you need what type you’re trying to create here, what’s the concrete function pointer type, it’s not clear. So that’s not going to work.

int main() {
  // Error: can't deduce template argument.
  auto *fptr = +[](auto i) {
    return i * i;
  };
}

The another cool thing about generic lambda is that they support the perfect forwarding. So if you write the auto ref ref, that’s a forwarding reference.

std::vector<std::string> v;
auto f [&v](auto&& item) {
  v.push_back(std::forward<decltype(item)>(item));
};

The compiler generates code is more or less like this. You get a function template calling operator.

struct __lambda_7 {
  __lambda_7(std::vector<std::string& _v)
    : _v(v) {}
    
  template <typename T>
  void operator()(T&& item) const {
    __v.push_back(std::forward<decltype(item)>(item));
  }
  
private:
  std::vector<std::string>& __v;
};

It also supports variate lambdas.

auto f [](auto&&... args) {
  // Fold expression (since C+17).
  (std::cout << ... << args);
};

f(42, "Hello", 1.5);

Because you can use auto keyword, you can pass lambdas into other lambdas. You can have a lambda that takes another lambda as its argument using auto keyword. You can do many cool meta-programming stuff with this.

auto twice = [](auto&& f) {
  return [=] { f(); f(); };
};

auto print_hihi = twice([] {
  std::cout << "hi";
});
print_hihi(); // hihi

Idiom 4: Variable Template Lambda

std::vector<std::string> v;
auto f = [&v](auto&& item) {
  v.push_back(std::forward<decltype(item)>(item));
};

If you have a generic lambda, the call operator is going to be a template.

struct __lambda_7 {
  __lambda_7(std::vector<std::string>& _v)
    : _v(v) {}
  
  template <typename T>
  void operator()(T&& item) const {
    __v.push_back(std::forward<decltype(item)>(item));
  }
  
private:
  std::vector<std::string>& __v;
};

What if we could make the lambda itself also a template.

That you can make a lambda a variable template and access the template parameter in it.

We define a variable template, and then we assign a generic lambda to it, and now what happens conceptually?

• Your Code

  template <typename T>
  constexpr auto c_cast = [](auto x) {
    return (T)x;
  };

• Compiler

  template <typename T>
  struct __lambda_9 {
    template <typename U>
    inline auto operator()(U x) const {
      return (T)x;
    }
  };
  
  template <typename T>
  auto c_cast = __lambda_9<T>();

Now we have a lambda template definition. Besides, we have a template call operator with different type of lambda template’s type since we use generic lambda.

template <typename T>
struct __lambda_9 {
  //...
  template <typename U>
  inline auto operator()(U x) const {
    // ...
  }
  //...  
};

This can be useful in a very particular scenario.

using ms = std::chrono::milliseconds;
using us = std::chrono::microseconds;
using ns = std::chrono::nanoseconds;

// we have a struct for storing a time point
// for some reason we use a variant(like union).
struct Time {
  std::variant<ms, ns> time;
  // this convert function takes a convert function
  // and applies it to the variant using std::visit.
  auto convert(const auto &converter) {
    return std::visit(converter, time);
  }
};

int main() {
  Time t(ns(3000));
  std::cout << t.convert(std::chrono::duration_cast<us>).count();
  // Error: This will get error since
  // `std::chrono::duration_cast<>` has three template parameters.
  // we cannot deduce the other two template parameters since
  // this duration_cast function is used as a argument
  // for other function.
}

We should specify conversion types for duration_cast using variable template. We can wrap the duration_cast into a helper struct. You can split template parameters into two parts:

1. the template parameters that you should specify explicitly;
2. the template parameters that should be deduced during callsite.

So this is a good practice for splitting template parameters into two parts, and using a helper variable template to specify the explicit parameters and deduce the other template parameters.

struct Time {
  std::variant<ms, ns> time;
  auto convert(const auto &converter) {
    return std::visit(converter, time);
  }
};

template <typename T>
constexpr auto duration_cast = [](auto d) {
  // The first template parameter is specified
  // explicitly. And the other two parameters
  // are deduced when this duration_cast
  // function called.
  return std::chrono::duration_cast<T>(d);
};

int main() {
  Time t(ns(3000));
  // Works.
  std::cout << t.convert(duration_cast<us>).count();
}

C++14 Init Capture

Using Init Capture, we can capture some non-copyable object.

• Your Code

  struct Widget {};
  auto ptr = std::make_unique<Widget>();
  
  // move happens here.
  auto f = [ptr = std::move(ptr)] {
    std::cout << ptr.get() << '\n';
  };
  
  assert(ptr == nullptr); // assert passes
  f();

• Compiler

  struct __lambda_8 {
    __lambda_8(std::unique_ptr<Widget> _ptr)
      : __ptr(std::move(_ptr)) {}
    inline void operator()() const {
      std::cout << __ptr.get() << '\n';
    }
    
  private:
    // type deduced as if by 'auto' decl.
    std::unique_ptr<Widget> __ptr;
  };
  
  __lambda_8(std::move(ptr));

Idiom 5: Init Capture Optimization

Reference Book: Bartlomiej Filipek: “C++ Lambda Story”

const std::vector<std::string> vs = {"apple",
                                     "orange",
                                     "foobar",
                                     "lemon"};
const std::string prefix = "foo";

auto result = std::find_if(
    vs.begin(), vs.end(),
    [&prefix](const std::string &s) {
      return s == prefix + "bar";
    });

if (result != vs.end()
  std::cout << prefix << "-something found!\n";

In the upper case, we concatenate a new string using prefix and "bar" in every loop iteration. But the result is always the same. So if we use the Init Capture, we can optimize this operation. The concatenation operation is performed only once. In this way, you saved a lot of CPU cycles because we can just do this operation once.

const std::vector<std::string> vs = {"apple",
                                     "orange",
                                     "foobar",
                                     "lemon"};
const std::string prefix = "foo";

auto result = std::find_if(
    vs.begin(), vs.end(),
    [str = prefix + "bar"](const std::string& s) {
        return s == str;
    });
if (result != vs.end())
  std::cout << prefix << "-something found!\n";

C++17 constexpr

In C++17, we can use constexpr because you can execute them at compile time. The result of a lambda as a non-type template parameter.

auto f = []() constexpr {
  return sizeof(void*);
};

std::array<int, f()> arr = {};

Class Template Argument Deducton (CTAD)

You don’t need to specify all template parameters since compiler can deduce these parameters.

// std::vector<int> deduced.
std::vector vec = {1, 2, 3, 4, 5, 6, 7};

Idiom 6: Lambda Overload Set

This is a very cool tool to have in your toolbox. If you want to create an object that is a callable object. So you can call it using the usual function called syntax, but it acts as an overload set. we also have a set of lambdas for overload. Because lambda is a struct type after compiler compile it. So you can inherit a lambda. This is really cool technique. You can do is you can write a variadic template which takes a bunch of template parameters by a bunch of types, and it’s going to inherit from all of these types. And then it’s going to use the call operator of all these types. So which means if you write using Ts operator. using Ts::operator()... means it’s kind of inheriting the call operators. The other interesting thing is that overload is an aggregate because it has no user-defined Constructors, it has no private members or anything like this, which means it’s an aggregate and the elements of the aggregate are the base classes. So what we can do is we can initialize an overload object with aggregate initialization using the braces. You can give it a bunch of lambdas, and those lambdas are going to be the base classes of that overload class, and it’s going to inherit the call operator from them.

We also need to write a deduction guide which is like two more lines.

template <typename... Ts>
struct overload : Ts... {
  using Ts::operator()...;
};

// C++17 should declare a deduction guide,
// C++20 doesn't need it anymore.
template <typename... Ts>
overload(Ts...) -> overload<Ts...>;

int main() {
  // aggregate initialization.
  overload f = {
      [](int f) { std::cout << "int thingy"; },
      [](float f) { std::cout << "float thingy"; }
  };
  
}

C++20

struct Widget {
  float x, y;
};

auto [x, y] = Widget();
auto f = [=] {
  std::cout << x << ", " << y << '\n';
};

• Lambda can capture parameter packs.

  auto foo(auto... args) {
    std::cout << sizeof...(args) << '\n';
  }
  
  template <typename... Args>
  auto delay_invoke_foo(Args... args) {
    return [args...]() -> decltype(auto) {
      return foo(args...);
    };
  }

• Lambda can be constval. This means it can only be called at compile-time.

  auto f = [](int i) constval {
    return i * i;
  };
  
  f(5); // OK, constant expression.
  int x = 5;
  f(x); // Error: call to immediate function 'f'
        //        is not a constant expression.

Template Lambda

std::vector<int> data = {1, 2, 3, 4, 5};
std::erase_if(
    data,
    // in generate lambda, you do not
    // need to specify types.
    [](auto i) { return i % 2; });

In C++20, you can explicitly use template lambda.

std::vector<int> data = {1, 2, 3, 4, 5};
std::erase_if(
    data,
    []<typename T>(T i) { return i % 2; });

Some interesting lambda expression features in C++20.

• Lambdas allowed in unevaluated contexts.
• Lambdas without captures are now:
  • default-constructible
  • assignable

Before C++20, it is not possible to have a lambda be a data member of a class, because you cannot write this

class Widget {
  // Error: non-static data member
  //        cannot be 'auto'.
  auto f = [] {};
};

Since C++20, you can write a lambda in an undivided context like this using decltype.

class Widget {
  decltype([]{}) f; // OK, since C++20
};

This can be useful when

template <typename T>
using MyPtr =
    std::unique_ptr<T, decltype([](T *t) {
      myDeleter(t);
    })>;

MyPtr<Widget> ptr;

Some tricky questions.

auto f1 = [] {};
auto f2 = [] {};
// f1 and f2 have different types since compiler
// generates different struct closure for each
// lambda respectively.

auto f1 = [] {};
auto f2 = f1;
// f1 and f2 have the same type.

auto f1 = [] {};
decltype(f1) f2;
// f1 and f2 have the same type. Because there is
// only one lambda type.

using t = decltype([] {});
t f1;
t f2;
// f1 and f2 have the same type.

decltype([] {}) f1;
decltype([] {}) f2;
// f1 and f2 have different lambda types.

template <auto = []{}>
    struct X {};

X x1;
X x2;

// x1 and x2 have different types.
// Because every time you define a lambda,
// compiler will generate a new struct
// closure, then there will be a different type.

Idiom 7: Unique types generator

Since C++20.

Idiom 8: Recursive Lambdas

Naive approach:

int main() {
  auto f = [](int i) {
    if (i == 0)
      return 1;
    // Error: 'f' declared with 'auto'
    // cannot appear in its own initializer!
    return i * f(i - 1);
  };
  
  std::cout << f(5) << '\n';
  
  return 0;
}

Using std::function(Still not great).

int main() {
  std::function<int(int)> f = [&](int i) {
    if (i == 0) return 1;
    return i * f(i - 1);
  };
  
  std::cout << f(5) << '\n';
  
  return 0;
}

We cannot name the lambda within itself, but we can template it on the function that it’s going to be calling within itself. And then we can pass itself to itself like this.

int main() {
  auto f = [](auto&& self, int i) {
    if (i == 0) return 1;
    // We can pass itself to itself like this.
    // But this looks awkward that this does not
    // look like a normal function call because
    // you always have to pass the lambda to itself
    // by argument.
    return i * self(self, i - 1);
  };
  std::cout << f(f, 5) << '\n'; // prints 120
  
  return 0;
}

// C++ deducing this: it just works
int main() {
  // this is an implicit argument, we don't need to
  // pass it, we just call f act like a normal
  // function call. Because if the compiler is going
  // to be like you want to have this implicit first
  // parameter which is this pointer, let's deduce
  // what it is, let's deduce the type and now you
  // can name this parameter. That's a good convention
  // that's what python people use. This must be good.
  auto f = [](this auto&& self, int i) {
    if (i == 0) return 1;
    return i * self(i - 1);
  };
  std::cout << f(5) << '\n'; // prints 120
  
  return 0;
}

Idiom 6 + 8: Recursive Lambda Overload Set

Ben Deane: Deducing this patterns

This is an example where you want to tree traversal. You have a binary tree. You are going to implement it as a variant. So every tree is either a leaf or a node, and it’s kind of recursive. And then what you want to traverse the tree you recursively and count the number of leaves. We can use the recursive lambda overload pattern here. Do this varient and we are going to have two lambdas here, one overload for the leaf, and one for the node, and if you have a node, you count the least by taking the left child and counting the leaves and taking the right child and counting leaves, so you are going to call it recursively. And the really cool thing here is that if you call this thing from within itself recursively using reducing this. Deducing this because it’s using the normal rules of function template argument deduction it’s going to deduce the fully derived like in so far as it s known at compile time, which in this case it is. So if you refer to self here, the self is not the lambda. The self is the fully derived type which is the whole overload set.
This is a classic job interview question. So next time somebody wanted to implement tree traverse, you can write it like this and you can really impress your interviewer. This is only supported in Microsoft compiler.

struct Leaf {};
struct Node;
using Tree = std::variant<Leaf, Node*>;
struct Node {
  Tree left, right;
};

template <typename... Ts>
struct overload : Ts... { using Ts::operator()...; };

// C++17 should define a guide deduction,
// C++20 doesn't need it anymore.
template <typename... Ts>
overload(Ts...) -> overload<Ts...>;

int countLeaves(const Tree &tree) {
  return std::visit(overload{
    [](const Leaf&) { return 1; },
    [](this const auto &self, const Node *node) -> int {
      return visit(self, node->left) +
             visit(self, node->right);
    }
  }, tree);
  
}

References

• expr.prim.lambda
• Timur Audio’s Blog