3匹の猫

みみねこの競プロ精進メモ

【C++】グローバルに置いたvectorの要素数を入力に応じて変更したい。

C++

競技プログラミングでdfsとかする時に、配列をグローバルで宣言すれば引数にいちいち含めなくても良くなるので楽だと思った。しかし、グローバルで宣言したvectorは要素数(長さ)をあらかじめ決めておく必要があるっぽい。困った

要求

以下のように入力が与えられるとします：

N
a_1\ a_2\ \dots\ a_N

この配列aを、グローバル変数として宣言したvectorオブジェクトvecで受け取りたい。ただしvecの要素数はNである(つまり可変である)。どうするか？

作戦A：要素数を仮決め ＆ erase()関数で削除

競プロなので要素数Nには制約があるはず。制約があるならその最大値を要素数にしちゃえば良い。例えば
1 \leq N \leq 10^5
という制約ならば、要素数が100000あればOK。
しかし、これだとNの値にかかわらず要素数が100000になってしまうので、 erase() を使い後方の使っていない部分を削除する。具体的には、vec.erase(a, b)で[a, b)の区間の要素を削除してくれる。

最初に100000個分の場所を確保するのでメモリ効率は悪い。そしてせっかく確保した場所をerase()で消してるのがかなり無駄な気がする。

#include <bits/stdc++.h>
using namespace std;
vector<int> vec(100000);
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++){
        cin >> vec[i];
    }
    vec.erase(vec.begin() + n, vec.end());
    return 0;
}

作戦B：vec=vector<int>(n)してから受け取る

空っぽのvecにvector<int>(n)を代入してやる。単純で分かりやすいし無駄がない。また、同じ長さの配列が2つ以上あるようなケースでも、例えばvectorオブジェクトa, bがあったとして
a = b = vector<int>(n);
としてやると1行で書ける。
ところで「vector<int>(n)」みたいなのって何て呼べばいいんだろうか…。知ってる人だれか教えてください。

#include <bits/stdc++.h>
using namespace std;
vector<int> vec;
int main(){
    int n;
    cin >> n;
    vec = vector<int>(n);
    for(int i = 0; i < n; i ++){
        cin >> vec[i];
    }
    return 0;
}

作戦C：vec.resize(N)してから受け取る

実は、vectorには要素数を自由に変えられるresize()関数なるものが存在する！vec.resize(n)で要素数をnに変更する。ちなみに、増えた部分は0埋めされる。
書き方もすっきりしてるし、vectorのちゃんとしたメンバ関数を使っているので謎の安心感もある。

#include <bits/stdc++.h>
using namespace std;
vector<int> vec;
int main(){
    int n;
    cin >> n;
    vec.resize(n);
    for(int i = 0; i < n; i ++){
        cin >> vec[i];
    }
    return 0;
}

作戦D：vec.push_back()して受け取る

これまでvectorオブジェクトで配列を受け取るときは、cin >> vec[i]のように、何番目の要素に代入するかを指定してきた。しかしpush_back()関数を使うと配列の末尾に要素を追加できる。vec.push_back(a)で、aという値をvecの末尾に追加する。このとき、当然要素数も1増える。余談だが、もし要素数が与えられずに配列のみ入力されたとしても、push_back()を使うと比較的楽に書けたりする。
ただし、ループ内で入力を仮に受け取るためだけにわざわざ変数を宣言しなくてはならないのが少し面倒。あと要素を追加する際に確保してあるメモリ領域が足りない場合は領域の再確保が行われるので、実行時間は少し遅くなると思う。本当にカスみたいな差だと思うけど。

#include <bits/stdc++.h>
using namespace std;
vector<int> vec;
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++){
        int a;
        cin >> a;
        vec.push_back(a);
    }
    return 0;
}

結論

個人的にオススメなのは作戦Bの代入するやつ。ただ、vecの要素数を気にしないのであれば作戦Aの方が早く書ける。作戦CとDは状況による。特に作戦Dのpush_back()を使ったことがない人は暇なとき書いて遊んでみるといい。


内容・ソースコードに関して間違いがあったら遠慮なく教えてください。