# C++: Pattern Matching Template Types

**How to check if a template type matches a pattern? Something like**

`is_like_v<T, vector<int,_>>`

.
A previous post considered function overload resolution in the presence of forwarding references, and proposed a design pattern of merging all the overloads of a function into one, using `if constexpr`

to implement the desired overload resolution logic for various argument types. This was restricted to using `std::is_same_v`

and `std::decay_t`

for exact type matches, up to const and ref qualifiers.

A follow up post extended this to checks of whether a given type is an instantiation of a given template, introducing a new type trait `is_instance_of_v`

, used as e.g. `is_instance_of_v<T, std::vector>`

.

In this post we go further again to implement pattern matching on template types. Patterns are written as e.g. `A<_,_>`

for an instantiation of a class template `A`

with two template arguments, or `A<int,_>`

where the first template argument must be `int`

but the second may be anything, or even nested patterns such as `B<_, A<int,_>>`

. We then introduce a new type trait `is_like_v`

to allow matching of types against such patterns, used as e.g. `is_like_v<T, A<int,_>>`

or `is_like_v<T, std::vector<_, std::allocator<_>>`

.

## Motivation

Consider a template type such as `std::vector`

:

```
template<
class T,
class Allocator = std::allocator<T>
> class vector;
```

It has two template parameters, `T`

and `Allocator`

, the first giving the element type, the second the allocator type. We may want to query whether some type is an instantiation of `std::vector`

but with a specific element type, say `int`

, while allowing for any allocator type. Effectively we’re looking for a partial match, a bit like a partial specialization of a template. We cannot do this with `std::is_same_v`

or the `is_instance_of_v`

type traits used in previous posts, however.

In this post we develop a new type trait `is_like_v`

that works a bit like `std::is_same_v`

, but with support for partial matches using a wildcard denoted by the underscore `_`

(using the underscore for fun, mostly—alternatives are possible). It will be used something like this:

```
if constexpr (is_like_v<T,vector<double,_>>) {
// ...do something
}
```

## Implementation

We start with a basic declaration of `is_like_v<T,P>`

, where `T`

denotes a type, and `P`

a pattern against which to match it. The pattern is itself a type, but it may include the wildcard `_`

.

The initial definition equates `is_like_v<T,P>`

with `std::is_same_v<T,P>`

, i.e. two types are alike if they are the same:

```
template<class T, class P>
inline constexpr bool is_like_v = std::is_same_v<T,P>;
```

Next, we introduce a type to denote wildcards in template patterns. For fun and nice-looking patterns, we’re going to make this the underscore `_`

, although in practice we should be wary of name collisions and reserved words:

```
struct _ {};
```

All types match the wildcard:

```
template<class T>
inline constexpr bool is_like_v<T,_> = true;
```

The final piece is more complicated: two template types are alike if they are instantiations of the same class template, and their template arguments are alike:

```
template<template<class...> class T, class... Ts, class... Us>
requires (sizeof...(Ts) == sizeof...(Us))
inline constexpr bool is_like_v<T<Ts...>,T<Us...>> = (is_like_v<Ts,Us> && ...);
```

Here we use a plentiful mix of modern C++ features: template parameter packs and the `sizeof...`

operator, template template arguments (as we did for `is_instance_of_v`

), constraints and concepts (the `requires`

) to check for the same number of template arguments, and fold expressions (the `(is_like<Ts,Us> && ...)`

).

But those few lines are all we need.

This does pattern matching up to const and ref qualifiers. To ignore const and ref qualifiers, massage in

`std::decay_t`

as in the first post.

## Demonstration

We can now use `is_like_v`

along the following lines:

```
is_like_v<std::vector<int>, std::vector<int,_>>; // true
is_like_v<std::vector<int>, std::vector<_,_>>; // true
is_like_v<std::vector<int>, std::list<int,_>>; // false
is_like_v<std::vector<int>, std::list<_,_>>; // false
is_like_v<std::vector<int>, std::vector<_, std::allocator<_>>>; // true
```

We can use such checks in `if constexpr`

statements to implement the body of a function with forwarding reference arguments, as suggested in the first post, but also other circumstances.

## Bonus: one-of-a-set

Let’s get beyond single wildcards, and consider sets of patterns as well. Given two or more patterns, we would like `is_like_v`

to give true if the given type matches at least one of those patterns.

By way of motivation, consider a numerical library where expression templates are used to represent mathematical formulae that are lazily evaluated. A linear expression of $x$ such as $ax + c$ may be represented by the type `Add<Mul<double,T>,double>`

, where `T`

is the generic type of $x$ (either a simple arithmetic type such as `double`

or a nested expression template type). But because multiplication and addition are commutative, i.e. $xy = yx$ and $x + y = y + x$, a linear expression of $x$ may emerge with any one of the types `Add<Mul<double,T>,double>`

, `Add<Mul<T,double>,double>`

, `Add<double,Mul<double,T>>`

or `Add<double,Mul<T,double>>`

.

How to match all of these?

Similar to the wildcard type `_`

, we can introduce a set type `in`

that collects together multiple patterns:

```
template<class... Ps>
struct in {};
```

Now extend `is_like_v`

with a new specialization to handle the `in`

type:

```
template<class T, class... Ps>
inline constexpr bool is_like_v<T,in<Ps...>> = (is_like_v<T,Ps> || ...);
```

This uses a fold expression to give true if the type `T`

matches any of the patterns `Ps...`

. We can now use something like the following:

```
is_like_v<T, in<
Add<Mul<double,_>,double>,
Add<Mul<_,double>,double>,
Add<double,Mul<double,_>>,
Add<double,Mul<_,double>>
>>;
```

If the pattern is to be reused, or if we just prefer the aesthetic, we can declare the pattern first:

```
using linear_pattern = in<
Add<Mul<double,_>,double>,
Add<Mul<_,double>,double>,
Add<double,Mul<double,_>>,
Add<double,Mul<_,double>>
>;
is_like_v<T, linear_pattern>;
```

Implementing a function with forwarding reference parameters may then look something like this:

```
template<class T>
void f(T&& x) {
if constexpr (is_like_v<std::decay_t<T>, linear_pattern>) {
// implementation for linear expression
std::cerr << "f(linear x)" << std::endl;
} else {
// implementation for everything else
std::cerr << "f(T&& x)" << std::endl;
}
}
```

This approach may reduce code size compared to separate function overloads for each of the linear expression types.

## Limitations

There are some limitations to pattern matching template types in this way.

Because the wildcard `_`

is defined as a type, it cannot be substituted for non-type template parameters. That precludes its use where value template parameters are involved, as for the second argument of `std::array`

(which gives the static size of the array):

```
template<
class T,
std::size_t N
> struct array;
```

or where template template parameters are involved, as for the `is_instance_of_v`

introduced previously.

Where duck-typed class templates are involved, we get away with using `_`

as a template argument in patterns because, while those patterns are types, they are not used in such a way that requires their instantiation. On the other hand, where class templates with concept or SFINAE constraints are involved, `_`

may be rejected as a template argument prior to instantiation, in which case the approach will not work.

The same applies to the set type `in`

.

A workaround for some of these limitations is to specialize `is_like_v`

for particular types. Consider `std::array`

again; if appropriate for the use case, we could specialize `is_like_v`

to match the value type `T`

, but ignore the length `D`

:

```
template<class T, size_t M, class U, size_t N>
inline constexpr bool is_like_v<std::array<T,M>,std::array<U,N>> = is_like_v<T,U>;
```

Where concept or SFINAE constraints are in use, we might also specialize those constraints for the wildcard `_`

and set `in`

types to satisfy them artificially. How will depend on the specifics of the constraints, but will likely involve the specialization of certain other type traits for these two types.

Mileage will vary, and the implementation of `is_like_v`

may need to be specific to the circumstances.

## Conclusion

This is the final of three posts inspired by the idea of establishing a design pattern for overloading functions in the presence of forwarding references, with greater control over overload resolution. Putting them all together, the suggested paradigm is to:

- Combine all function overloads into one with forwarding reference parameters.
- Within the body of that one function, use
`if constexpr`

to provide implementations for different argument types. - Within each
`if constexpr`

condition, use type traits such as`std::is_same_v`

, or the new type traits introduced in these posts,`is_instance_of_v`

and`is_like_v`

, to check for types. - Within each
`if constexpr`

body, provide the appropriate implementation for those types.

Taking this approach can reduce repeated code in situations where multiple function overloads would otherwise be required, especially so where several of those overloads would have essentially the same implementation. It can also provide finer control over behavior where the usual overload resolution rules do not yield the desired precedence, as the body of the one function can be implemented with arbitrary selection logic for the argument types.

Here’s a complete example for further experimentation with `is_like_v`

:

```
#include <type_traits>
#include <iostream>
#include <vector>
#include <list>
#include <array>
template<class T, class P>
inline constexpr bool is_like_v = std::is_same_v<T,P>;
struct _ {};
template<class T>
inline constexpr bool is_like_v<T,_> = true;
template<template<class...> class T, class... Ts, class... Us>
requires (sizeof...(Ts) == sizeof...(Us))
inline constexpr bool is_like_v<T<Ts...>,T<Us...>> = (is_like_v<Ts,Us> && ...);
template<class T, size_t M, class U, size_t N>
inline constexpr bool is_like_v<std::array<T,M>,std::array<U,N>> = is_like_v<T,U>;
template<class... Ps>
struct in {};
template<class T, class... Ps>
inline constexpr bool is_like_v<T,in<Ps...>> = (is_like_v<T,Ps> || ...);
int main() {
std::cerr << is_like_v<std::vector<int>, std::vector<int,_>> << std::endl; // true
std::cerr << is_like_v<std::vector<int>, std::vector<_,_>> << std::endl; // true
std::cerr << is_like_v<std::vector<int>, std::list<int,_>> << std::endl; // false
std::cerr << is_like_v<std::vector<int>, std::list<_,_>> << std::endl; // false
std::cerr << is_like_v<std::vector<int>, std::vector<_, std::allocator<_>>> << std::endl; // true
std::cerr << is_like_v<std::array<int,10>, std::array<_,20>> << std::endl; // true, due to specialization
using pattern = in<
std::vector<_,std::allocator<_>>,
std::list<_,std::allocator<_>>
>;
std::cerr << is_like_v<std::vector<int>,pattern> << std::endl; // true
return 0;
}
```