vector

概要

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

普通の変数をデータ $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()

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 より前かどうかを判定する。
すなわち、以下のように判定する。

• 前から順に、初めて同じ位置に異なる要素があるところを探す
• その異なった場所で s の方が前であるかを判定する。

- 前であるとは、値が小さいか、配列がもう終了していること

逆向きの > も使える。
<= や >= も使える。

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

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

メモリ確保 .reserve(要素数)（C問題相当）

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

別にこれをやらなくても、よしなに引越ししてくれるため、必須ではない。
とはいえ、長い文字列の引越しが発生したせいでTLEしたら悲しい。

配列編集系（全体的にB問題相当）

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

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

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

末尾要素の次を指すイテレータを取得する。

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

逆順での先頭、つまり末尾要素を指す逆イテレータを取得する。

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

逆順での末尾の次、つまり先頭要素の $1$ つ前を指す逆イテレータを取得する。

先頭参照 .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(); で、vec の最後の $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() 以降で初めて 3 がある場所を検索する。
返り値はイテレータで、第 $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) {
  // 中身の要素 i に対してしたいことを書く
}

中身の書き換えまでしたい場合は 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)$ かかる。
コードの見た目で処理時間を見積もると、わりと痛い目を見るので注意。

関連アルゴリズム

string型

文字や要素を一列に並べて保持し、添字アクセスや末尾への追加・削除などができる点で似ている。

size_t型

.size() の返り値には、size_t 型が使われる。

イテレータ

.begin() や .end() でイテレータを取得し、範囲の指定や要素の挿入・削除などに用いる。

多次元vector

vector の要素をさらに vector にすることで、多次元配列として扱える。