内容別リスト/変数とデータ構造/vector - 競技プログラミング用 知識集積所

---

雑な説明

動的配列。
変数を一列にずらっと並べたようなデータ構造。
多数の、または不特定個数のデータを扱う上で最も基本となる。

レベル

ABCのA問題レベル。

詳細な説明

動的配列。
普通の変数をデータ1つを書いておけるホワイトボードとするなら、配列はそのホワイトボードを大量に連結したもの。
動的とは、その連結する個数を後から増やしたり減らしたりできるものという意味である。

string型と扱いが似ている（というか、string型がvectorに似ている）。

宣言と初期化

宣言だけする場合

vector<int> vec;                // <int>型用の、要素数0のvectorができる
vector<double> vec;             // <double>型用の、要素数0のvectorができる
vector<string> vec;             // <string>型用の、要素数0のvectorができる

要素数だけ指定する場合

vector<int> vec(10);            // <int>型用の、要素数10のvectorができる
vector<long long> vec(10000);   // <long long>型用の、要素数10000のvectorができる
vector<double> vec(n);          // <double>型用の、要素数nのvectorができる

代入で初期化する場合

vector<int> vec = {1,2,3};      // 固定値で初期化
vector<int> vec = vector(5,-1); // 要素数と文字種で初期化、この場合は5個の-1となる
vector<int> vec = v;            // 他の配列で初期化

（コピー）コンストラクタで初期化する場合

vector<int> vec{1,2,3};         // 固定値で初期化
vector<int> vec(5,-1);          // 要素数と文字種で初期化、この場合は5個の-1となる
vector<int> vec(v);             // 他の配列で初期化
vector<int> vec(v.begin()+1,v.end()-3);   // イテレータで初期化 (vectorから)
vector<int> vec(que.begin(),que.end());   // イテレータで初期化 (dequeから）
vector<int> vec(s.begin(),s.end());       // イテレータで初期化 (setから）

型を推論に任せる

初期化もする場合、型が明らかな場合は<>部分を略してもよい
ただし、string型の場合は、推論が難しいようなので明示的に書いた方がよい。

vector vec = {1,2,3};
vector vec(5,-1);

可能な演算

基本的なもの

i番目を参照 .at(i) または [i]

例えば

vec.at(3)

と書けば、「vecという配列の3番目」という中身と同じ型の変数であるかのように扱える。
ただし、コンピューター的には添字は0から始まるため、{1,2,3,4,5}の3番目は4であることに注意。
以後の計算でも全て同様。

vec[3]

と書いてもほぼ同じ。
違いは、範囲外（3要素しかないのに5番目を参照しようとする）などしたときの挙動の違い。
前者はエラーしてくれるのでバグの修正がしやすいがコードがちょっと見にくい。
後者はちょっとコードが見やすいが、エラーせず強引に実行して変な結果を出すだけなのでバグの修正が大変。
急いでバグ修正する必要がある競プロでは.at(i)を使う方が無難。

長さの取得 .size() または .length()

vec.size()

で配列vecの長さをsize_t型で取得できる。
size_t型は扱いの注意点も多いので、取得したらそのままint型変数に一度代入してしまうのも1つの手。

代入 =

vec=v; で、配列vecの中身をvに書き換える。
要素数の変更も行ってくれる。
数学とは違い、左右を逆にして v=vec; と書くと意味が変わるので注意。

空判定 .empty()

vec.empty()で、vecが空っぽかどうかをbool型で返す。
結果自体はvec.size()==0と書くのと変わらない。
一応、.empty()の方が高速らしいが、誤差レベルなので書きやすさ優先で選んでよし。

一致判定 ==

vec==vで、配列が一致するか判定する。
すなわち、長さが同じで、各位置の要素もすべて一致するか判定する。
!=も使える。

辞書順判定 <

vec<vで、辞書順でvecがvより前かどうかを判定する。
すなわち、前から順に初めて同じ位置に異なる要素があるところを探し、その異なった場所がvecの方が前（小さいか、配列がもう終了している）であるかを判定する。
逆向きの>も使える。
<=や>=も使える。

コンストラクタ vector(要素数,中身) （B問題レベル）

vector<int>(5,-1)と書くと、-1を5個並べた配列{-1,-1,-1,-1,-1}を意味する。
5個くらいなら直接書いてもいいが、100個並べる場合などにはコンストラクタで書いた方が便利。

メモリ確保 .reserve(要素数) （C問題レベル）

vec.reserve(100000)と書くと、100000要素分のメモリを確保する。
確保できない場合は、今のうちに100000要素確保できるところにデータをお引越ししてくれる。
後で要素をどんどん追加して長くなっていく場合に、可能性のある最大要素数以上に確保しておくとよい。

別にこれをやらなくても、足りなくなった時点で自動的にメモリが空いてるところにお引越ししてくれるため、必須ではない。
とはいえ、99999要素まで書いたところで「メモリの連続空きスペースが足らなくなったので、この99999要素全部お引越ししまーす」という不要な処理が発生してTLEしたら悲しい。

配列編集系（全体的にB問題レベル）

先頭イテレータ取得 .begin()

先頭を指すイテレータ※を取得する。

末尾イテレータ取得 .end()

末尾を指すイテレータ※を取得する。

先頭逆イテレータ取得 .rbegin()

先頭を指す逆イテレータ※を取得する。

末尾逆イテレータ取得 .rend()

末尾を指す逆イテレータ※を取得する。

先頭参照 .front()

vec.front()で先頭の要素を参照する。
……普通にvec.at(0)でいい気も。

末尾参照 .back()

vec.back()で末尾の要素を参照する。
配列の長さが途中で変化するような場合には便利。

末尾挿入 .emplace_back(要素)

vec.emplace_back(3);ならvecの最後に3を追加する。
また。string型のように.push_back()も使えるが、何もメリットはない。

末尾削除 .pop_back()

vec.pop_back();で、sの最後の1文字を削除する。

途中挿入 .insert(イテレータ,要素)または.insert(イテレータ,イテレータ,イテレータ)

vec.insert(itr,10);で、itrの位置に10を挿入する。
vec.insert(itr,{10,11,12});と要素リストを作ってまとめて挿入もできる。
vec.insert(itr1,itr2,itr3);で、itr1の位置にitr2からitr3までの要素を挿入する。
itr2とitr3はvecとは別のvectorのイテレータでもよい。

途中削除 .erase(イテレータ)または.erase(イテレータ,イテレータ)

vec.erase(itr);なら、itr位置の要素を削除する。
vec.erase(itr1,itr2)とすると、itr1からitr2までを削除する。

全削除 .clear()

vec.clear();でvecを空配列にする。

サイズ変更 .resize(要素数,要素)

配列の長さを変更する。
短くする場合は後ろを削除、長くする場合は後ろを指定要素で埋める。
例えばvecの中身が{1,2,3}である場合、vec.resize(2)なら{1,2}に、vec.resize(5,-1)なら{1,2,3,-1,-1}になる。

交換 .swap(別の配列)

vec.swap(v);で、vecとvの中身が入れ替わる。
swap(vec,v);でも同じ。
実は中身ではなく配列の名前などの情報の方を入れ替えるので、中身が長くても一瞬で終わる。

検索系（全体的にB問題レベル）

配列検索 find(イテレータ,イテレータ,要素)

find(vec.begin(),vec.end(),3)と書けば、vec.begin()以降で初めて"abc"という並びがある場所を検索する。
返り値はイテレータで、第2引数のところまで存在しなかった場合は第2引数をそのまま返す。
string型と書き方も返り値も全く違うので注意。

該当要素数カウント count(イテレータ,イテレータ,要素)

count(vec.begin(),vec.end(),3)と書けば、vec内に3が何個あるかを数える。

よく使う処理

配列を標準入力から受け取る

string型とは異なり、一度にcinで中身を受け取ることはできない。

vector<int> a(n);
for (int i=0; i<n; i++) {
  cin >> a.at(i);
}

または

vector<int> a(n);
for (int& i : a) {
  cin >> i;
}

というように、forループを用いて1つずつ受け取る。

中身を逆順に並べなおす

reverse(vec.begin(),vec.end());

配列が逆順の方が都合がいい場合などに。
また、配列の前にたくさん挿入したい場合に、「逆順にして、後ろに追加して、また逆順にする」という方法が使える。

中身を小さい順に並べる

sort(vec.begin(),vec.end());

数列の並び順はもはや壊れてもいいので、中身を全部小さい順に並べてほしい場合に。

sort(vec.rbegin(),vec.rend());

なら、逆順に並ぶ。

1要素ずつ何か処理する

.at(i)で1要素ずつ見ていく。
長さnが与えられている場合

for (int i=0; i<n; i++) {
  // 中身の要素vec.at(i)に対してしたいことを書く
}

長さnが与えられていない場合
（一度.size()で長さを取得してから上のやつを用いてもよい）

for (size_t i=0; i<vec.size(); i++) {
  // 中身の要素vec.at(i)に対してしたいことを書く
}

1要素ずつ何か処理する、その2（B問題レベル）

範囲for文※で1文字ずつ取り出すことができる。

for (int i : vec) {
  // 中身の要素vec.atiに対してしたいことを書く
}

中身の書き換えまでしたい場合はint&として参照渡し※をする。

順に増える内容で初期化する（B問題レベル）

iota関数※を使う。

vector<int> vec(n);
iota(vec.begin(),vec.end(),0);

とすれば、0からn-1まで順に入った数列を用意できる。
第3引数を1にすれば、1からnまで順に入った数列を用意できる。
forループで自分で書くのと、あんまり手間が変わってない気も。

全部合計する（B問題レベル）

accumulate関数※を使う。

accumulate(vec.begin(),vec.end(),0)

で、第3引数にvecの全ての数を前から順に+した値を返してくれる。
int型から溢れそうな場合は、第3引数を0LLにするとlong long型で計算してくれる。
これも、forループで自分で書くのと、あんまり手間が変わってない気も。

注意点

処理速度に注意。（C問題レベル）

長さnのvectorは、プログラム上1行で書いても当然中身はn個ある。
中身を1要素ずつ見ていく系の処理や、先頭や途中の文字が増減する処理は、O(n)かかる。
コードの見た目で処理時間を見積もるとわりと痛い目を見るので注意。

関連アルゴリズム