std::vector

概要

C言語における配列では、定義時に予めサイズを指定し、その配列サイズの中でやりくりする必要がありました。

vectorは動的配列であり、後から要素数を変更することが出来ます。

詳しい使い方はよその丁寧に説明されているサイトを見て、どうぞ。

イテレータ

vectorとお友達になるにはイテレータを知る必要があります。ググって。

Tips

競プロは時間との勝負なので、defineやusingを使って積極的にタイプ数を減らしましょう。

vector系はとりあえず何でも省略しておいたほうが楽なので、二次元配列くらいまではusingで型エイリアスを貼って省略しちゃいましょう。

 

頻出メソッド

キーワードを書きなぐっておきます。
詳しい使い方は丁寧なサイトを見てどうぞ。

vector::begin

vectorの始めの要素を指すiteratorを返します。

vector::end

vectorの末尾の次を示すiteratorを返します。

vector::rbegin

vectorの末尾の要素を指すイテレータを返します。
逆順で見れます。

vector::rend

先頭要素の前を指す逆イテレータを返します。

vector::size

vectorの要素数を返します。

vector::push_back

vectorの末尾に要素を追加します。

vector::emplace_back

push_backの強いバージョン(正確には違う)。

std::pairやstd::tupleのvectorを使用する場合、こっちのほうが高速かつ便利。

vector::erase

vector内の任意の箇所の要素を削除します。
重いので基本使わない。

vector::insert

vector内の任意の箇所に要素を追加します。
重いので基本使わない。

eraseやinsertを使う必要がある場合、std::set等の別の型を使用したほうが良い可能性が高いです。

関連メソッド

以下の機能を用いれば、vectorをもっと便利に扱えます。

これ以降で紹介する機能を用いるにはそれぞれに対応したヘッダーファイルをincludeする必要がありますが、どれがどれとか毎回紹介するのは面倒なので割愛します。
GCCならとりあえずbits/stdc++.hをincludeしておけば、全部使えるようになります。

std::sort

vector内の要素を昇順でソートします。

また、第3引数に比較関数を指定することで、好きなようにソートすることも出来ます。

計算量は配列の長さをNとした時、O(N logN)となります。

std::find

範囲 [first, last) 内の特定の基準を満たす最初の要素を取得します。
その様な要素がない場合、lastを返します。

計算量は配列の長さをNとした時、O(N)となります。

std::binary_search

二分探索でvector内に目的の値が存在するかを確認します。
存在すればtrue、しなければfalseを返します。

※使用先のvectorは予め昇順にsortされている必要があります。特殊な順番でソートしている場合、sort時と同じ比較関数を第4引数のcompに指定してください。

計算量は配列の長さをNとした時、O(logN)となります。

std::lower_bound

二分探索を用い、範囲 [first, last) 内の value 以上の最初の要素を指すイテレータを取得します。
そのような要素がない場合、 last を返します。

※使用先のvectorは予め昇順にsortされている必要があります。

計算量は配列の長さをNとした時、O(logN)となります。

std::upper_bound

二分探索を用い、範囲 [first, last) 内の value より大きい最初の要素を指すイテレータを取得します。
そのような要素がない場合、 last を返します。

※使用先のvectorは予め昇順にsortされている必要があります。

計算量は配列の長さをNとした時、O(logN)となります。

std::next_permutation

vector内の要素を入れ替えていき、順列の全列挙を行います。
※使用先のvectorは予め昇順にsortされている必要があります。

  • 使用例

例題