C#11のリストパターン、便利そうだなぁ。そうだ！C++でも作ろう！


C# 11 に[リスト パターン](https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/proposals/csharp-11.0/list-patterns)というものが追加されたそうです。

```c#
int[] numbers = { 1, 2, 3 };

Console.WriteLine(numbers is [1, 2, 3]);  // True
Console.WriteLine(numbers is [1, 2, 4]);  // False
Console.WriteLine(numbers is [1, 2, 3, 4]);  // False
Console.WriteLine(numbers is [0 or 1, <= 2, >= 3]);  // True
```

```c#
List<int> numbers = new() { 1, 2, 3 };

if (numbers is [var first, _, _])
{
    Console.WriteLine($"The first element of a three-item list is {first}.");
}
// Output:
// The first element of a three-item list is 1.
```
（ https://learn.microsoft.com/ja-jp/dotnet/csharp/language-reference/operators/patterns#list-patterns より引用）

なるほど、便利そうです。
C++でも使いたいです。

**作ります。**

# C++ 版リストパターン

<details>
<summary>Qiita で直接見たい人はこちら</summary>

```c++
#include <functional>
#include <iterator>
#include <tuple>
#include <type_traits>

#include <iostream>
#include <vector>
#include <list>

template <class T, class = void>
struct is_sized : std::false_type {};
template <class T>
struct is_sized<T, decltype(
    std::size(std::declval<T&>())
, void())> : std::true_type {};
template <class T>
constexpr bool is_sized_v = is_sized<T>::value;

template <class T, class U, class = void>
struct is_equality_comparable_with  : std::false_type {};
template <class T, class U>
struct is_equality_comparable_with<T, U, decltype(
    std::declval<const std::remove_reference_t<T>&>() == std::declval<const std::remove_reference_t<U>&>()
, void())> : std::true_type {};
template <class T, class U>
constexpr bool is_equality_comparable_with_v = is_equality_comparable_with<T, U>::value;

template <class T>
struct is_reference_wrapper : std::false_type {};
template <class T>
struct is_reference_wrapper<std::reference_wrapper<T>> : std::true_type {};
template <class T>
constexpr bool is_reference_wrapper_v = is_reference_wrapper<T>::value;

struct range_pattern_placeholder_t {};
namespace range_pattern_placeholder {
    inline constexpr range_pattern_placeholder_t _;
}

template <class... Types>
class range_pattern {
public:
    constexpr range_pattern(const Types&... args) : value{ args... } {}

    template <class R>
    constexpr bool match(R&& r) const {
        if constexpr (is_sized_v<R>) {
            if (std::size(r) != sizeof...(Types)) {
                return false;
            }
        }
        return match_impl(std::forward<R>(r), std::make_index_sequence<sizeof...(Types)>{});
    }

    template <class R>
    friend constexpr bool operator==(R&& r, const range_pattern& m) {
        return m.match(std::forward<R>(r));
    }

private:
    std::tuple<const Types&...> value;

    template <class R, std::size_t... I>
    constexpr bool match_impl(R&& r, std::index_sequence<I...>) const {
        auto first = std::begin(r);
        auto last = std::end(r);
        bool result = ((first != last && [&]() -> bool {  // while (first != last)
            using T = std::tuple_element_t<I, std::tuple<Types...>>;
            if constexpr (is_reference_wrapper_v<T> || std::is_same_v<T, range_pattern_placeholder_t>)
                return ++first, true;
            else if constexpr (is_equality_comparable_with_v<decltype(*first), const T&>)
                return *first++ == std::get<I>(value);
            else
                return std::get<I>(value)(*first++);
        }()) && ...) && first == last;
        if (result) {
            auto it = std::begin(r);
            ([&] {
                using T = std::tuple_element_t<I, std::tuple<Types...>>;
                if constexpr (is_reference_wrapper_v<T>) std::get<I>(value).get() = *it++;
                else ++it;
            }(), ...);
        }
        return result;
    }
};

int main() {
    constexpr auto _ = range_pattern_placeholder::_;

    {
        std::vector numbers{ 1, 2, 3 };

        std::cout << std::boolalpha;
        std::cout << (numbers == range_pattern{ 1, 2, 3 }) << '\n';  // numbers is [1, 2, 3]
        std::cout << (numbers == range_pattern{ 1, 2, 4 }) << '\n';  // numbers is [1, 2, 4]
        std::cout << (numbers == range_pattern{ 1, 2, 3, 4 }) << '\n';  // numbers is [1, 2, 3, 4]
        std::cout << (numbers == range_pattern{
            [](int x) { return x == 0 || x == 1; },
            [](int x) { return x <= 2; },
            [](int x) { return x >= 3; },
        }) << '\n';  // numbers is [0 or 1, <= 2, >= 3]
    }

    {
        std::list<int> numbers{ 1, 2, 3 };
        
        if (int first; numbers == range_pattern{ std::ref(first), _, _ }) {
            std::cout << "The first element of a three-item list is " << first << ".\n";
        }
    }
}
```

</details>

[GitHub Gist で見たい人はこちら](https://gist.github.com/Raclamusi/25826d7eac4f7a066f2cea65e8a4181d)
[Wandbox で試したい人はこちら](https://wandbox.org/permlink/YzqgrzMTHUE7PFfz)

作りました。
`(レンジ) == range_pattern{ (パターン)... }` で C# のリスト パターンっぽいことができます。

## 対応パターン

再現した C# のパターンとその説明を以下に示します（需要あるのか？）。

- 定数パターン
    - 値を指定します
    - その値との `==` が `true` になる値がマッチします
    - 使用例: `range_pattern{ 0, x, f() }`
- リレーショナル パターン、論理パターン
    - 関数オブジェクトを指定します
    - その関数オブジェクトに渡して `true` が返るような値がマッチします
    - 使用例: `range_pattern{ [](auto x) { return x < 3; } }`
- var パターン
    - `std::reference_wrapper` のオブジェクトを指定します
    - 任意の値にマッチします
    - `range_pattern` 全体がマッチしたときに、このパターンにマッチした値がその参照に書き込まれます
    - 使用例: `range_pattern{ std::ref(a) }`
- 破棄パターン
    - `range_pattern_placeholder::_` を指定します
    - 任意の値にマッチします
    - 使用例: `range_pattern{ range_pattern_placeholder::_ }`
- ほかのパターン
    - 諦めました

## 実装

[AtCoder](https://atcoder.jp/?lang=ja) で使いたかったので、 C++17 で実装しました。

一番のお気に入りポイントは、ラムダ式と畳み込み式によるループです！

```c++
bool result = ((first != last && [&]() -> bool {
    using T = std::tuple_element_t<I, std::tuple<Types...>>;
    if constexpr (is_reference_wrapper_v<T> || std::is_same_v<T, range_pattern_placeholder_t>)
        return ++first, true;
    else if constexpr (is_equality_comparable_with_v<decltype(*first), const T&>)
        return *first++ == std::get<I>(value);
    else
        return std::get<I>(value)(*first++);
}()) && ...) && first == last;
```

`([] { /* ... */ }() && ...)` とすることで、 constexpr if を使って評価方法を変えながら `std::all_of` みたいなことができます。
読みにくさ抜群！

（「演算子のオペランド間の評価順序は未規定で……」みたいなコメントが来るんじゃないかとビクビクしていましたが、 `&&` や `,` などは大丈夫そうです[^races]。）

[^races]: https://timsong-cpp.github.io/cppwp/n4861/intro.races#7

# 競プロで使ってみた

`range_pattern` を使って [ABC278 の D 問題](https://atcoder.jp/contests/abc278/tasks/abc278_d)を解いてみました。
クエリをさばくところがいい感じに書けてる気がします。（ほんとか？）

https://atcoder.jp/contests/abc278/submissions/37266097

# 参考サイト

[パターン マッチング - is および switch 式、パターン内の演算子 and、or、not | Microsoft Learn](https://learn.microsoft.com/ja-jp/dotnet/csharp/language-reference/operators/patterns)