競プロC++テンプレートまとめ

はじめに

個人的によく使っている競プロテンプレートをまとめました。

一つでも参考になれば幸いです。

repマクロ

for文を短縮できるかの有名なマクロです。

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; (i) < (n); ++(i))

int main() {
    // [0, 10)を回す
    rep(i, 10) {
        cout << i << '\n';
    }
}

上のような形が基本です。

僕は以下のようなものを使っています。

#include <bits/stdc++.h>
using namespace std;

#define OVERLOAD_REP(_1, _2, _3, name, ...) name
#define REP1(i, n) for (auto i = std::decay_t<decltype(n)>{}; (i) != (n); ++(i))
#define REP2(i, l, r) for (auto i = (l); (i) != (r); ++(i))
#define rep(...) OVERLOAD_REP(__VA_ARGS__, REP2, REP1)(__VA_ARGS__)

int main() {
    // 2引数にも3引数にも対応
    // [0, 5)
    rep(i, 5) {
        cout << i << '\n';
    }
    // [1, 5)
    rep(i, 1, 5) {
        cout << i << '\n';
    }

    vector<int> a{1, 2, 3};
    // イテレータも回せる
    rep(i, a.begin(), a.end()) {
        cout << *i << '\n';
    }
}

• 2引数にも3引数にも対応している
• イテレータも回せる

という点が便利です。

ここでは、マクロのオーバーロード(？)テクニックが使われています。

// 4番目の引数を選ぶマクロ
#define OVERLOAD_REP(_1, _2, _3, name, ...) name
// ...

// 引数が2つ -> REP1が選ばれる
// 引数が3つ -> REP2が選ばれる
#define rep(...) OVERLOAD_REP(__VA_ARGS__, REP2, REP1)(__VA_ARGS__)

引数の個数に応じて処理を変更したいので、引数によってうまく使用されるマクロ (REP1, REP2) が切り替わるようになっています。

allマクロ

こちらも一般的なマクロです。開始イテレータと終了イテレータを一度に書くことができます。

#define all(a) (a).begin(), (a).end()

all マクロ同様に rall マクロも用意しておくと便利です。

#include <bits/stdc++.h>
using namespace std;

// 汎用性向上のためstd::begin, std::endを使用(残念ながらADLを活用することはできない)
#define all(...) std::begin(__VA_ARGS__), std::end(__VA_ARGS__)
#define rall(...) std::rbegin(__VA_ARGS__), std::rend(__VA_ARGS__)

int main() {
    vector<int> a{1, 3, 2};

    sort(all(a)); // a.begin(), a.end() を省略
    sort(rall(a)); // a.rbegin(), a.rend() を省略
}

std::vector<bool> の実装を修正する

実は std::vector<bool, Allocator> は特殊な実装がされており、競プロにおいても罠となり得ます。

例えば、こんな恐ろしいことが起こります。

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<bool> a{false};

    auto x = a[0]; // なんとxはbool型ではなく特別な型
    x = true; // さらにa[0]の変更もできてしまう

    cout << a[0] << '\n';
}

これを回避してみます。

std::vector と似たクラスとして std::basic_string があり、これについては bool 型に対しての特殊な実装はされていません。

そのため std::vector<bool> が std::basic_string<bool> を継承するように実装を特殊化することにより、通常の挙動に戻すことができます。

template<>
struct std::vector<bool>: std::basic_string<bool> {
    using std::basic_string<bool>::basic_string, std::basic_string<bool>::operator =;
    explicit vector(size_t n): vector(n, false) {}
};

このコードを先ほどの例に加えてみると結果が変わることが確認できると思います。

RecLambda

通常ラムダ式で再帰は行えないので、それを可能にするクラスです。

普通の関数と比べて、ラムダ式では自動で変数をキャプチャしてくれるので、変数をグローバルに置き直したり、参照渡しさせたりする手間が省けます。

#include <bits/stdc++.h>
using namespace std;

template<class F>
struct RecLambda {
private:
    F func;
public:
    template<class G>
    constexpr RecLambda(G&& func) noexcept: func(std::forward<G>(func)) {}
    template<class... Args>
    constexpr decltype(auto) operator ()(Args&&... args) const noexcept(std::is_nothrow_invocable_v<F, Args...>) {
        return func(*this, forward<Args>(args)...);
    }
};
template<class G>
RecLambda(G&&) -> RecLambda<std::decay_t<G>>;

int main() {
    // 1. 戻り値の型を書く必要がある
    // 2. 第一引数を auto&& 関数名 にする必要がある
    RecLambda fib = [](auto&& fib, int n) -> int {
        return n < 2 ? n : fib(n - 1) + fib(n - 2);
    };

    cout << fib(10) << '\n';
}

• 戻り値の型を書く必要がある
• 第一引数を auto&& 関数名 にする必要がある

ことだけ注意が必要です。

lambdaマクロ

C++のラムダ式は少し記述が重いので、JavaScriptのように気軽に書けることを目標にしたマクロです。

#include <bits/stdc++.h>
using namespace std;

// 引数を取得するマクロ
#define $(idx) (std::get<(idx)>(std::forward_as_tuple(_args...)))
// ラムダ式を短く書くマクロ
#define lambda(...) ([&](auto&&... _args) { return (__VA_ARGS__); })

int main() {
    // $(0)で第一引数、$(1)で第二引数を取得
    auto func = lambda($(0) * 3 + 1);

    cout << func(2) << '\n';
}

多次元vector生成関数

多次元vectorを作成する場合記述が長くなってしまうので、簡潔に書けるようにする関数です。

#include <bits/stdc++.h>
using namespace std;

template<class T, size_t n, size_t idx = 0>
auto make_vec(const size_t (&d)[n], const T& init) noexcept {
    if constexpr (idx < n) return std::vector(d[idx], make_vec<T, n, idx + 1>(d, init));
    else return init;
}

template<class T, size_t n>
auto make_vec(const size_t (&d)[n]) noexcept {
    return make_vec(d, T{});
}

int main() {
    // 2×2×2で全要素が1のvectorを作成
    auto a = make_vec<int>({2, 2, 2}, 1);

    // 2×2×2で全要素が0のvectorを作成
    auto b = make_vec<int>({2, 2, 2});
}

exit_with, continue_with, break_with

#include <bits/stdc++.h>
using namespace std;

#define exit_with(...) ({ __VA_ARGS__; exit(0); })
#define break_with(...) ({ __VA_ARGS__; break; })
#define continue_with(...) ({ __VA_ARGS__; continue; })

int main() {
    for (int i = 0; i < 10; ++i) {
        // これを4行で書くのが煩わしい時に役立つ
        // if (i == 3) {
        //     cout << i << '\n';
        //     break;
        // }
        if (i == 3) break_with(cout << i << '\n');
    }
}

exit(0), continue, break といった抜け出す処理の前に何かやりたい場合に、一行で書くことができるマクロです。

GNU拡張が必要な上にそこまで便利ではないので、最近は使っていません。

switch文を簡潔に書くマクロ

#include <bits/stdc++.h>
using namespace std;

#define OVERLOAD_MATCH(_1, _2, _3, _4, name, ...) name
#define MATCH1(_1) break; case _1:
#define MATCH2(_1, _2) break; case _1: case _2:
#define MATCH3(_1, _2, _3) break; case _1: case _2: case _3:
#define MATCH4(_1, _2, _3, _4) break; case _1: case _2: case _3: case _4:
#define match(...) OVERLOAD_MATCH(__VA_ARGS__, MATCH4, MATCH3, MATCH2, MATCH1)(__VA_ARGS__)
#define otherwise break; default:

int main() {
    int x;
    cin >> x;
    switch (x) {
        match (0, 1) {
            cout << "Less than two\n";
        } match (2) {
            cout << "Two\n";
        } otherwise {
            cout << "Greater than two\n";
        }
    };
}

switch文が気持ち悪いので作りました。

そもそもswitch文を競プロでは使わないので、使用頻度は低いです。

終わりに

時間がなかったので、コードの解説をほとんどしていません。

気が向いたら追加していこうと思います。

最後までご覧いただきありがとうございました。