Contents
概要
C言語における配列では、定義時に予めサイズを指定し、その配列サイズの中でやりくりする必要がありました。
vectorは動的配列であり、後から要素数を変更することが出来ます。
詳しい使い方はよその丁寧に説明されているサイトを見て、どうぞ。
イテレータ
vectorとお友達になるにはイテレータを知る必要があります。ググって。
Tips
競プロは時間との勝負なので、defineやusingを使って積極的にタイプ数を減らしましょう。
std::vector<long long> vec; // ... std::sort(vec.begin(), vec.end()); // とするが毎回このように記述するのは面倒なので using namespace std; using ll = long long; using vll = vector<ll>; #define all(v) v.begin(), v.end() // と予め記述しておけば vll vec; // ... sort(all(v)); // と省略できる
vector系はとりあえず何でも省略しておいたほうが楽なので、二次元配列くらいまではusingで型エイリアスを貼って省略しちゃいましょう。
using ll = long long; using ld = long double; using vi = vector<int>; using vvi = vector<vi>; using vll = vector<ll>; using vvll = vector<vll>; using vb = vector<bool>; using vs = vector<string>;
頻出メソッド
キーワードを書きなぐっておきます。
詳しい使い方は丁寧なサイトを見てどうぞ。
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しておけば、全部使えるようになります。
#include <bits/stdc++.h>
std::sort
vector内の要素を昇順でソートします。
std::sort(v.begin(), v.end()); // 以下の表現でも同じ動作をする #define all(v) v.begin(), v.end() std::sort(all(v));
また、第3引数に比較関数を指定することで、好きなようにソートすることも出来ます。
// 降順ソート
bool comp(const ll &lhs, const ll &rhs) {
return lhs > rhs;
};
std::sort(all(v), comp);
// ただの降順ならSTLで用意されている
std::sort(all(v), std::greater<ll>());
計算量は配列の長さをNとした時、O(N logN)となります。
std::find
template< class InputIterator, class T > InputIt find( InputIterator first, InputIterator last, const T& value );
範囲 [first, last) 内の特定の基準を満たす最初の要素を取得します。
その様な要素がない場合、lastを返します。
計算量は配列の長さをNとした時、O(N)となります。
std::binary_search
template< class ForwardIt, class T > bool binary_search( ForwardIt first, ForwardIt last, const T& value ); template< class ForwardIt, class T, class Compare > bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );
二分探索でvector内に目的の値が存在するかを確認します。
存在すればtrue、しなければfalseを返します。
※使用先のvectorは予め昇順にsortされている必要があります。特殊な順番でソートしている場合、sort時と同じ比較関数を第4引数のcompに指定してください。
計算量は配列の長さをNとした時、O(logN)となります。
std::lower_bound
template< class ForwardIterator, class T > ForwardIt lower_bound( ForwardIterator first, ForwardIterator last, const T& value ); template< class ForwardIterator, class T, class Compare > ForwardIt lower_bound( ForwardIterator first, ForwardIterator last, const T& value, Compare comp );
二分探索を用い、範囲 [first, last) 内の value 以上の最初の要素を指すイテレータを取得します。
そのような要素がない場合、 last を返します。
※使用先のvectorは予め昇順にsortされている必要があります。
計算量は配列の長さをNとした時、O(logN)となります。
std::upper_bound
template< class ForwardIterator, class T > ForwardIt upper_bound( ForwardIterator first, ForwardIterator last, const T& value ); template< class ForwardIterator, class T, class Compare > ForwardIt upper_bound( ForwardIterator first, ForwardIterator last, const T& value, Compare comp );
二分探索を用い、範囲 [first, last) 内の value より大きい最初の要素を指すイテレータを取得します。
そのような要素がない場合、 last を返します。
※使用先のvectorは予め昇順にsortされている必要があります。
計算量は配列の長さをNとした時、O(logN)となります。
std::next_permutation
vector内の要素を入れ替えていき、順列の全列挙を行います。
※使用先のvectorは予め昇順にsortされている必要があります。
- 使用例
sort(all(v));
do {
// do something
} while (next_permutation(all(v)));
// sortの仕方が特殊な場合はnext_permutationの第3引数にも比較関数を指定する
std::sort(all(v), comp);
do {} while (next_permutation(all(v), comp));
例題
- Average Length (ABC145)