入出力は大事

　入力やデバッグの速度は、早解きにも難問考察にも密接に関わってくるため、競プロのパフォーマンスのあらゆる面に影響を及ぼすといっても過言ではないでしょう（私調べ）。

　例えば、C++ では cout printf がデバッグに使えますが、これは int double string といった基本的な型しかサポートしていないという難点があります。Python だったら大体なんでも print で一括表示してくれるのに！

　これをもっと便利にできないでしょうか。

具体例

　より具体的な話をします。以下のような簡単なプログラムを考えます。

整数 $N$ と、長さ $N$ の配列が与えられるので、それを出力をしなさい。

　Python だったら、

n = int(input())
a = list(map(int, input().split(' ')))
print(*a)

　という 3 行で実装できますが、C++ の場合（以下、C++ のコードは #include の類を省略）、

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << (i + 1 != n ? ' ' : '\n');
    }
}

　と、かなりの量になります。for 文はマクロでいくらか省略化できますが、それでも n 回のループを回さなければいけないことに変わりはありません。

　ひとつの解決策は、専用の関数を用意することです。

　しかし、これにも難点があって、すべての型に対して専用の関数を用意しなければいけません。テンプレートを使えばいくらか一括して定義できますが、階層構造になったデータ型に対してもすべて定義しようとすると、かなり膨大な量になります（型の種類を $N$、階層の深さを $M$ とすると、おおよそ $O(N^m)$ の量になります）。

　やはり、理想としては、

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    cin >> a;
    cout << a << endl;
}

　こう書きたい。

オーバーロード

　これは、オーバーロードによって実現できます。

template <typename T>
istream &operator>>(istream &is, vector<T> &v)
{
    for (T &in : v)
        is >> in;
    return is;
}

　これにより、vector に対して >> でデータを入力した場合、vector の長さの分だけ自動的に入力を読み取らせる、ということが可能になります。

　また、これは当然 cout に対しても行うことができます。同様に、以下をオーバーロードします。

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    for (int i = 0; i < (int)v.size(); i++)
    {
        os << v[i] << (i + 1 != (int)v.size() ? " " : "");
    }
    return os;
}

　これにより、以下のようなシンプルな書き方が可能になります。

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    cin >> a;
    cout << a << endl;
}

入力

5
1 2 3 4 5

出力

1 2 3 4 5

vector 以外も

　話は当然 vector だけに収まりません。

　例えば、pair ではどうでしょうか。プリミティブな環境では、入出力は以下のようになると思います。

int main()
{
    int a, b;
    cin >> a >> b;
    pair<int, int> p = {a, b};
    cout << "(" << p.first << "," << p.second << ")" << endl;
}

　入力もそうですが、出力が特に面倒くさいです。難問の考察で極限状態になっている時に追加でこんなコードを書かなければいけないとしたらストレスマックスです。

　これも、入出力をオーバーロードします。

template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p)
{
    is >> p.first >> p.second;
    return is;
}

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p)
{
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

　これにより、以下のようなシンプルな書き方ができます。

int main(){
    pair<int,int> p;
    cin >> p;
    cout << p << endl;
}

入力

1 2

出力

(1,2)

再帰的に処理できる

　オーバーロードの強力な点は、階層構造になったデータに対しても順次、再帰的に処理できる、という点です。

　例えば、一度 vector<> に対するオーバーロードを行えば、vector<vector<>> に対しても中身が vector<> である限り同じ処理を行うことができます。

　つまり、先程の入出力のオーバーロードを定義するだけで、

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    cin >> a;
    cout << a << endl;
}

　二次元ベクトルに対しても、このように簡潔な記述にすることができます。

　しかし、これは注意点があります。

　例えば、このような入力を考えます。

入力

　上のコードの出力は、以下のようになります。

出力

1 2 3 4 5 6 7 8 9 10 11 12

　これはオーバーロードの記述の仕方によるものです。わかりやすく括弧をつけると、

[[1 2 3] [4 5 6] [7 8 9] [10 11 12]]

　というような入れ子構造になっています。vector 単体での出力には改行を含めない方が便利なことが多いのでこうしていますが、二次元で表示したい場合は少し不便です。ここら辺は個人の好みの領域になりますが、例えば以下のようなカスタマイズが考えられます。

template <typename T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v)
{
    for (int i = 0; i < (int)v.size(); i++)
    {
        os << v[i] << endl;
    }
    return os;
}

　こうすれば出力は以下のようになります。

出力

1 2 3 4
5 6 7 8
9 10 11 12

　他にも、上に述べた pair と組み合わせれば、以下のようなこともできます。

int main()
{
    int n;
    cin >> n;
    vector<pair<int,int>> a(n);
    cin >> a;
    cout << a << endl;
}

入力

4
1 2 3 4 5 6 7 8

出力

(1,2) (3,4) (5,6) (7,8)

　この再帰的な性質により、一通り型に対してオーバーロードを定義すればどんな深い階層の型に対しても対応可能になります（型の種類を $N$ とすると、おおよそ $O(N)$。上に述べたように、細かいカスタマイズは出てくるでしょうが）。この点も、専用関数を定義する方法よりも優れている点です。

どんどんやっていこう

　不定長のデータ構造だと出力だけになってしまいますが、それでもデバッグが爆速になることに変わりはありません。

map

template <typename T, typename S>
ostream &operator<<(ostream &os, const map<T, S> &mp)
{
    for (auto &[key, val] : mp)
    {
        os << key << ":" << val << " ";
    }
    cout << endl;
}

set

template <typename T>
ostream &operator<<(ostream &os, const set<T> &st)
{
    auto itr = st.begin();
    for (int i = 0; i < (int)st.size(); i++)
    {
        os << *itr << (i + 1 != (int)st.size() ? " " : "");
        itr++;
    }
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, multiset<T> st)
{
    auto itr = st.begin();
    for (int i = 0; i < (int)st.size(); i++)
    {
        os << *itr << (i + 1 != (int)st.size() ? " " : "");
        itr++;
    }
    return os;
}

queue

template <typename T>
ostream &operator<<(ostream &os, queue<T> q)
{
    while (q.size())
    {
        os << q.front() << " ";
        q.pop();
    }
    return os;
}

stack

template <typename T>
ostream &operator<<(ostream &os, stack<T> st)
{
    while (st.size())
    {
        os << st.top() << " ";
        st.pop();
    }
    return os;
}

prioirity_queue

template <class T, class Container, class Compare>
ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq)
{
    while (pq.size())
    {
        os << pq.top() << " ";
        pq.pop();
    }
    return os;
}

　出力の例。

int main()
{
    map<int,int> mp;
    set<int> st;
    multiset<int> mst;
    queue<int> q;
    stack<int> s;
    priority_queue<int> pq;
    for (int i = 0; i < 10; i++)
    {
        mp[i] = i / 2; 
        st.insert(i / 2);
        mst.insert(i / 2);
        q.push(i / 2);
        s.push(i / 2);
        pq.push(i/ 2);
    }
    cout << mp << endl;
    cout << st << endl;
    cout << mst << endl;
    cout << q << endl;
    cout << s << endl;
    cout << pq << endl;
}

出力

0:0 1:0 2:1 3:1 4:2 5:2 6:3 7:3 8:4 9:4 
0 1 2 3 4
0 0 1 1 2 2 3 3 4 4
0 0 1 1 2 2 3 3 4 4
4 4 3 3 2 2 1 1 0 0
4 4 3 3 2 2 1 1 0 0

極端な例ですが、こんな込み入ったデータ構造でも大丈夫です。

int main()
{
    map<int, queue<pair<int, int>>> mp;
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 5; j++)
        {
            mp[i].push({j, j + 1});
        }
    }
    cout << mp << endl;
}

出力

0:(0,1) (1,2) (2,3) (3,4) (4,5)  1:(0,1) (1,2) (2,3) (3,4) (4,5)  2:(0,1) (1,2) (2,3) (3,4) (4,5)  3:(0,1) (1,2) (2,3) (3,4) (4,5)  4:(0,1) (1,2) (2,3) (3,4) (4,5)

全部まとめて

　ここまで出てきたオーバーロードをすべてまとめます。これをソースコードに貼り付ければあなたの cin と cout は今日から爆速に！

template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p)
{
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p)
{
    is >> p.first >> p.second;
    return is;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    for (int i = 0; i < (int)v.size(); i++)
    {
        os << v[i] << (i + 1 != (int)v.size() ? " " : "");
    }
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v)
{
    for (int i = 0; i < (int)v.size(); i++)
    {
        os << v[i] << endl;
    }
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v)
{
    for (int i = 0; i < (int)v.size(); i++)
    {
        os << "i = " << i << endl;
        os << v[i];
    }
    return os;
}

template <typename T>
istream &operator>>(istream &is, vector<T> &v)
{
    for (T &in : v)
        is >> in;
    return is;
}

template <typename T, typename S>
ostream &operator<<(ostream &os, const map<T, S> &mp)
{
    for (auto &[key, val] : mp)
    {
        os << key << ":" << val << " ";
    }
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const set<T> &st)
{
    auto itr = st.begin();
    for (int i = 0; i < (int)st.size(); i++)
    {
        os << *itr << (i + 1 != (int)st.size() ? " " : "");
        itr++;
    }
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &st)
{
    auto itr = st.begin();
    for (int i = 0; i < (int)st.size(); i++)
    {
        os << *itr << (i + 1 != (int)st.size() ? " " : "");
        itr++;
    }
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, queue<T> q)
{
    while (q.size())
    {
        os << q.front() << " ";
        q.pop();
    }
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, deque<T> q)
{
    while (q.size())
    {
        os << q.front() << " ";
        q.pop_front();
    }
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, stack<T> st)
{
    while (st.size())
    {
        os << st.top() << " ";
        st.pop();
    }
    return os;
}

template <class T, class Container, class Compare>
ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> pq)
{
    while (pq.size())
    {
        os << pq.top() << " ";
        pq.pop();
    }
    return os;
}

ACL も

　使いこなせれば強力な武器となる ACL（AtCoder Libray）の modint も、デバッグがすぐできた方が便利です。これは先に include しないとエラーになってしまうので、上の一覧にはいれてませんでしたが、これも一応。

#include <atcoder/modint>
using namespace atcoder;
using mint = modint998244353;
// using mint = modint1000000007; 問題によって使い分け

ostream &operator<<(ostream &os, const mint &i)
{
    os << i.val();
    return os;
}

ostream &operator<<(ostream &os, const vector<mint> &v)
{
    for (int i = 0; i < (int)v.size(); i++)
    {
        os << v[i].val() << (i + 1 != (int)v.size() ? " " : "");
    }
    return os;
}

int main()
{
    mint n = 1;
    cout << n << endl;
}

出力