int[]とarrayとvector

　配列を定義するにはおおきくわけて以下の $3$ つがあります。

int a[100];

array<int,100> a;

vector<int> a(100);

　それぞれの利点を一言でまとめると、

int[] : 速い
array : ある程度速くて安全
vector : 長さを変えられる

　となります。実際に速さを計ってみます。大量の配列の読み書きをさせます。vector は、最初に長さを確保するもの（fixed）と、逐次的に長さを確保していくもの（not fixed）とわけます。配列サイズは 2e6 程度、回数は 1e8 程度です。

ベンチマークコード

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

using ll = long long;

template <class F>
double bench(const string& name, F f) {
    auto st = chrono::high_resolution_clock::now();

    volatile ll res = f(); // 最適化で消されるのを防ぐ

    auto ed = chrono::high_resolution_clock::now();
    double ms = chrono::duration<double, milli>(ed - st).count();

    cout << name << ": " << ms << " ms, res = " << res << '\n';
    return ms;
}

int main() {
    constexpr int N = 2000000;
    constexpr int LOOP = 50;

    static int c_array[N];
    static array<int, N> std_array;
    vector<int> vec_fix(N);

    bench("C array write", [&]() -> ll {
        ll s = 0;
        for (int r = 0; r < LOOP; r++) {
            for (int i = 0; i < N; i++) {
                c_array[i] = i;
            }
        }
        for (int i = 0; i < N; i++) s += c_array[i];
        return s;
    });

    bench("std::array write", [&]() -> ll {
        ll s = 0;
        for (int r = 0; r < LOOP; r++) {
            for (int i = 0; i < N; i++) {
                std_array[i] = i;
            }
        }
        for (int i = 0; i < N; i++) s += std_array[i];
        return s;
    });

    bench("vector fixed write", [&]() -> ll {
        ll s = 0;
        for (int r = 0; r < LOOP; r++) {
            for (int i = 0; i < N; i++) {
                vec_fix[i] = i;
            }
        }
        for (int i = 0; i < N; i++) s += vec_fix[i];
        return s;
    });

    bench("vector not fixed write", [&]() -> ll {
        ll s = 0;
        vector<int> v;
        v.reserve(N);
        for (int r = 0; r < LOOP; r++) {
            v.clear();
            for (int i = 0; i < N; i++) {
                v.push_back(i);
            }
            if(r == LOOP-1){
                for(int i = 0; i < N; i++){
                    s += v[i];
                }
            }
        }
        return s;
    });

    cout << '\n';

    bench("C array read", [&]() -> ll {
        ll s = 0;
        for (int r = 0; r < LOOP; r++) {
            for (int i = 0; i < N; i++) {
                s += c_array[i];
            }
        }
        return s;
    });

    bench("std::array read", [&]() -> ll {
        ll s = 0;
        for (int r = 0; r < LOOP; r++) {
            for (int i = 0; i < N; i++) {
                s += std_array[i];
            }
        }
        return s;
    });

    bench("vector read", [&]() -> ll {
        ll s = 0;
        for (int r = 0; r < LOOP; r++) {
            for (int i = 0; i < N; i++) {
                s += vec_fix[i];
            }
        }
        return s;
    });
}

C array write: 81.0115 ms, res = 1999999000000
std::array write: 124.096 ms, res = 1999999000000
vector fixed write: 302.737 ms, res = 1999999000000
vector not fixed write: 1198.77 ms, res = 1999999000000

C array read: 147.627 ms, res = 99999950000000
std::array read: 129.98 ms, res = 99999950000000
vector read: 290.593 ms, res = 99999950000000

int[] > array > vector(fixed)>>> vector(not fixed)

　という感じです。vector(not fixed) は、サイズ更新や容量チェックなどが入るため、添字アクセスでの代入より遅くなっています。

　ただ、これだけ大規模に書き込ませる問題は稀だと思うので、この差によって TLE でペナることまずないと思います。更に言えば、特殊な設定な問題でない限り、入力の最大サイズは明らかなので、先に最大長を確保しておけばその差は更に縮まります。

危険な要素

　int の生配列はいちばんプリミティブです。シンプルかつ速いですが色々危険です。

int main(){
    int a[10];
    for(int i = 0; i < 20; i++){
        cout << a[i] << endl;
    }
}

（ローカルでは初期化していないと）めちゃくちゃな値がでてきますし、範囲外も指定できるのでバグの元です。array と vector は範囲外を at するとエラーが出るので安心です。

種類	速度	初期化	範囲外参照
`int[]`	◎	されない	ノーチェック
`array`	◎	されない	`at()` はチェック
`vector`	◯	される	`at()` はチェック

vector に対する操作色々

　vector は実行時にサイズを指定できます。以下のような命令があります。

resize
reserve
assign

　resize と assign はほとんど使い方は同じです。

int main(){
    vector<int> a;
    a.resize(4,3); // {3,3,3,3}
    vector<int> b;
    b.assign(4,3); // {3,3,3,3}
}

　このふたつはどちらも同じ {3,3,3,3} になります。

　違いが出るのは既存の配列に変更を加えたときです。

int main(){
    vector<int> a = {3,3,3,3};
    a.resize(5,6); // {3,3,3,3,6}
    vector<int> b = {3,3,3,3};
    b.assign(5,6); // {6,6,6,6,6}
}

　resize は既存の要素に変更を加えません。なので、初期化したと思ったらしていない事故が起こります。配列を初期化して使い回すような場合は、assign の方が良いでしょう。

　reserve はちょっと特殊で、メモリだけを先に確保します。これによって動的確保が起こらずに速くなるらしいです。ベンチマークをしてみましょう。

ベンチマークコード

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

using ll = long long;

template <class F>
double bench(const string& name, F f) {
    auto st = chrono::high_resolution_clock::now();

    volatile ll res = f(); // 最適化で消されるのを防ぐ

    auto ed = chrono::high_resolution_clock::now();
    double ms = chrono::duration<double, milli>(ed - st).count();

    cout << name << ": " << ms << " ms, res = " << res << '\n';
    return ms;
}

int main() {
    constexpr int N = 2000000;
    constexpr int LOOP = 50; // N * LOOP = 1e8

    bench("vector resize + index write", [&]() -> ll {
        ll s = 0;
        vector<int> v;

        for (int r = 0; r < LOOP; r++) {
            v.resize(N);

            for (int i = 0; i < N; i++) {
                v[i] = i;
            }

            if (r == LOOP - 1) {
                for (int i = 0; i < N; i++) {
                    s += v[i];
                }
            }
        }

        return s;
    });

    bench("vector assign + index write", [&]() -> ll {
        ll s = 0;
        vector<int> v;

        for (int r = 0; r < LOOP; r++) {
            v.assign(N, 0);

            for (int i = 0; i < N; i++) {
                v[i] = i;
            }

            if (r == LOOP - 1) {
                for (int i = 0; i < N; i++) {
                    s += v[i];
                }
            }
        }

        return s;
    });

    bench("vector reserve + push_back", [&]() -> ll {
        ll s = 0;
        vector<int> v;
        v.reserve(N);

        for (int r = 0; r < LOOP; r++) {
            v.clear();

            for (int i = 0; i < N; i++) {
                v.push_back(i);
            }

            if (r == LOOP - 1) {
                for (int i = 0; i < N; i++) {
                    s += v[i];
                }
            }
        }

        return s;
    });

    bench("vector push_back without reserve", [&]() -> ll {
        ll s = 0;

        for (int r = 0; r < LOOP; r++) {
            vector<int> v;

            for (int i = 0; i < N; i++) {
                v.push_back(i);
            }

            if (r == LOOP - 1) {
                for (int i = 0; i < N; i++) {
                    s += v[i];
                }
            }
        }

        return s;
    });
}

vector resize + index write: 297.01 ms, res = 1999999000000
vector assign + index write: 341.335 ms, res = 1999999000000
vector reserve + push_back: 972.193 ms, res = 1999999000000
vector push_back without reserve: 1437.46 ms, res = 1999999000000

　速度については、resize≒assign >> reserve + push_back > push_back without reserve という感じです。

　なので、reserve をあえて使う意味は（競プロ的な文脈では）あまりないと思います。~~そもそも reverse と紛らわしすぎる~~。

push_back と emplace_back

　vector に要素を追加するときの命令。push_back では要素そのものを、emplace_back では要素をつくるときのコンストラクタを呼びます。emplace_back の方が速いらしいです。比較してみましょう。

ベンチマークコード

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

using ll = long long;

template <class F>
double bench(const string& name, F f) {
    auto st = chrono::high_resolution_clock::now();

    volatile ll res = f(); // 最適化で消されるのを防ぐ

    auto ed = chrono::high_resolution_clock::now();
    double ms = chrono::duration<double, milli>(ed - st).count();

    cout << name << ": " << ms << " ms, res = " << res << '\n';
    return ms;
}

int main() {
    constexpr int N = 500000;
    constexpr int LOOP = 50; // N * LOOP = 1e8

    bench("pair push_back({a,b})", [&]() -> ll {
        ll s = 0;
        vector<pair<int, int>> v;
        v.reserve(N);

        for (int r = 0; r < LOOP; r++) {
            v.clear();

            for (int i = 0; i < N; i++) {
                v.push_back({i, i + 1});
            }

            if (r == LOOP - 1) {
                for (int i = 0; i < N; i++) {
                    s += v[i].first;
                    s += v[i].second;
                }
            }
        }

        return s;
    });

    bench("pair emplace_back(a,b)", [&]() -> ll {
        ll s = 0;
        vector<pair<int, int>> v;
        v.reserve(N);

        for (int r = 0; r < LOOP; r++) {
            v.clear();

            for (int i = 0; i < N; i++) {
                v.emplace_back(i, i + 1);
            }

            if (r == LOOP - 1) {
                for (int i = 0; i < N; i++) {
                    s += v[i].first;
                    s += v[i].second;
                }
            }
        }

        return s;
    });
}

pair push_back({a,b}): 998.568 ms, res = 250000000000
pair emplace_back(a,b): 1104.2 ms, res = 250000000000

　なぜか push_back の方が速くなりましたが、正直誤差レベルな感じです。もはや趣味でいいと思います。

違いがでるとき

　以下のような場合では挙動に違いが出ます。

int main(){
    vector<vector<int>> a;
    a.push_back({3,4}); // {3,4} という vector<int> を追加
    vector<vector<int>> b;
    b.emplace_back(3,4); // vector<int>(3,4) を追加、つまり {4,4,4} を追加
}