STL vector の基本操作・サイズ・イテレーター・操作・交換・判定

http://program.station.ez-net.jp/special/handbook/cpp/stl/vector.asp
より転載

可変長配列 std::vector<> を使用する

C++ では、可変長の配列を簡単に利用できる std::vector<> というテンプレートクラスが用意されています。

これを使用することで、要素を追加したり削除したり、挿入したりといったことが簡単にできます。同じようなものに std::list がありますけど、こちらと違ってインデックス番号を使って任意の要素を自由に取り出せるのも魅力です。

テンプレートクラスなので、任意のデータ型を扱えるのも便利です。

使用準備

C++ で std::vector<> を使用するには、次のようにヘッダーファイルをインクルードする必要があります。

#include <vector>

このようにすることで、std::vector<> テンプレートクラスが利用できるようになります。

また、この std::vector<> を操作するのに使う一部の関数は、次のヘッダーに用意されています。

#include <algorithm>

これをインクルードすることで、並び替えなどの外部関数を使うことができます。

初期化

std::vector<> インスタンスは、次のようにして生成します。

std::vector<int> vector;

左側で指定している "std::vector<int>" がデータ型になります。

ここで "<int>" としているのは、この std::vector<> が int 型を扱うということを意味しています。ここを使いたい型に変えることで、任意の型を std::vector<> で扱うことが可能です。

その後の "vector" は、自由につけられる変数名です。

利用できるメソッド

std::vector<> には、動的配列を手軽に操作するためのメソッドがたくさん用意されています。

その中の、良く使いそうなメソッドをいくつか紹介します。

基本操作

TYPE at(sizet index)	指定したインデックス番号の要素を取得します。[] 演算子と違って、無効なインデックスを指定した場合は out_of_range 例外が発生するので、間違いを検出しやすくなっています。
void clear()	格納されている要素を全て削除します。
void push_back(const TYPE& value)	指定した値を最後尾に追加します。新しい値は std::vector<> 内の要素を格納するメモリに代入文で設定されます。このとき、追加済みの全ての要素が再構築されます。
void pop_back()	最後尾の要素を削除します。
TYPE front()	先頭要素を取得します。
TYPE back()	最終要素を取得します。

std::vector<> は、スタック的な動作をするメソッドが用意されています。

push_back で最後尾に値を追加し、pop_back で最後尾の要素を削除します。

このとき、値の追加の際には、既存の全ての要素がコピーコンストラクタを使って再構築され、それまで使っていた値は全て破棄されます。最後尾の削除については、最後の要素が破棄されるだけで、その他の要素はそのままのようです。

最後尾の要素の値を取得したい場合には back を使用します。

また、std::vector<> では任意の場所の値を at メソッドまたは [] 演算子を使って取得できます。

どちらも 0 から始まるインデックス番号で要素を指定することができますが、存在しない要素を指定した場合、at メソッドでは out_of_range 例外が発生します。[] 演算子の場合は、不正のまま続行されます。

状態の取得

size_t size()	格納されている要素数を取得します。
void empty()	要素が格納されていない場合に true を返します。

std::vector<> では、要素の数を知るための size メソッドの他にも、要素があるかどうかを調べるための empty メソッドも用意されています。

イテレータ

iterator begin()	要素の先頭を示すイテレータを取得します。
iterator end()	要素の末尾 (EOF) を示すイテレータを取得します。最終要素はこのひとつ前にあります。
reverse_iterator rbegin()	要素の末尾を示すリバースイテレータを取得します。
reverse_iterator rend()	要素の先頭 (EOF) を示すリバースイテレータを取得します。先頭要素はこのひとつ前にあります。

イテレータというのは、繰り返し処理を支援する仕組みです。

std::vector<>::iterator 型のイテレータでは、アロー演算子 (->) を使うことで、そのイテレータが示す位置にある値のポインタを取り出すことができるようになっています。このイテレータの値を足したり引いたりすることで、位置を前後に移動することもできます。

std::vector<>::reverse_iterator 型のリバースイテレータは、通常のイテレータの逆順に動作するイテレータです。

また、std::vector<> を const 指定で使用している場合、これらのイテレータは読み取り専用のものが取得されます。

その時に begin メソッドや end メソッドなどで取得できるイテレータの型は普段とは異なり、それぞれ std::vector<>::const_iterator と std::vector<>::const_reverse_iterator になります。

特定の要素の操作

iterator erase(iterator pos) iterator erase(iterator start, iterator end)	イテレータで指定した pos 位置の、または start から end までの要素を削除します。戻り値は削除された要素の次を示します。
iterator insert(iterator pos, const TYPE& value) void insert(iterator pos, size_t num, const TYPE& value)	イテレータで指定した pos 位置に値 value を挿入します。このとき num が指定されていれば、

イテレータで要素の位置を指定することで、それが示す要素を削除したり、そこに新しい要素を追加したりすることもできます。

要素の交換

void swap(std::vector<>& source)	指定された std::vector<> の要素と、自身が保持する要素とを入れ替えます。

2 つの std::vector<> の要素を交換するメソッドも用意されていました。

使用できる演算子

一致の判定

==	ふたつの std::vector<> が一致するかを調べます。要素は == 演算子を使って評価されます。
!=	ふたつの std::vector<> が一致しないかを調べます。要素は == 演算子を使って評価されます。

std::vector<> での一致判定は、2 つの std::vector<> の .size() が一致するかどうかと、同じインデックス番号の要素がそれぞれ全て一致するかで判定されます。

全てを満たす時に true、どれかが満たされない場合に false となります。

このとき、== でも != でも、要素ごとの判定は "==" が使われるようでしたが、処理系に依存するかもしれません。また、判定は条件が満たされなくなったところで打ち切られるようでした。

順位の判定

<=	左の std::vector<> が右の std::vector<> 以下かを調べます。
>=	左の std::vector<> が右の std::vector<> 以上かを調べます。
<	左の std::vector<> が右の std::vector<> 未満かを調べます。
>	左の std::vector<> が右の std::vector<> より大きいかを調べます。

std::vector<> での順位判定は、std::lexicographically_compare 関数のような自書式順序で比較が行われるそうです。

辞書式順序というのは Wikipedia: 辞書式順序 にも詳しく記載されていますが、C 文字列の比較 strcmp と同じと思うと判りやすいと思います。つまり > や < などで途中まで一致していても、最後の要素で大小関係が正しく成り立っている場合は true になります。

これを判定するとき、内部ではどうやら要素を比較するとき、与えられた std::vector<> の順序とそれを逆順にしたのとのそれぞれで < 演算を行うことで、小さいのか、大きいのか、どちらでもない（等しい）のかを判定しているようでしたが、処理系に依存するかもしれません。また、判定は条件が満たされなくなったところで打ち切られるようでした。

要素の操作

[]	std::vector<> の指定されたインデックス番号の要素を取得します。
=	左の std::vector<> に、右の std::vector<> を代入します。このとき、要素は新しいものが作られてコピーされます。

std::vector<> では [] 演算子を使って指定した要素を取り出せるようになっています。

ただし、存在する要素の範囲を超えたインデックスを指定すると、[] の場合は不正な値を取得して処理を続けてしまいます。

確実に範囲内にある場合はいいでしょうけど、確実でない場合は at() メソッドを使って取得する方が、範囲外にアクセスしたときに out_of_range 例外が発生するので安全です。

代入演算子では、左に指定した std::vector<> に右の要素を代入します。

このとき、もともとあった要素は全て破棄されて、新しく代入される要素はコピーコンストラクタを使って新しい別の値として代入されます。

□ 要素をインデックスを指定して取得するとき

std::vector<> では、インデックス番号を使って要素を取得することができます。

このとき、std::vector<> では [] 演算子を使って要素を取得することもできますが、at() メソッドを使用した方が安全です。

int value = vector.at(5);

指定したインデックスが、std::vector<> が持っている要素を超えた場合、[] 演算子では不正な値を取得して処理が続行されますが、at() メソッドを使用した場合は out_of_range 例外が発生するようになります。

指定するインデックスが、既存の要素を超えないことがあまりにも確実な場合は、もしかすると [] 演算子の方が高速なのかもしれないですけど、処理速度の効率化が余程必要なところでなければ、at() メソッドを使っておいた方が無難です。

□ std::vector<> でクラスインスタンスを扱う場合

クラスの値を扱う場合

std::vector<> ではクラスインスタンスも扱うことができます。

std::vector<CMyClass> vector;

たとえばこのようにすることで、CMyClass 型を扱う std::vector<> を使えます。

この時、push_back メソッドで挿入されるインスタンスは、通常はコピーコンストラクタを使って生成された新しいインスタンスになります。poo_back メソッドで削除されたインスタンスは、デストラクタが呼び出されます。

ここで気になるのが、push_back メソッドを実行した時です。

このとき vector に既に値が格納されていた場合、それらの値が全てコピーコンストラクタを使って生成し直されます。

コピーにそれほどコストがかからないクラスならいいのですけど、メモリを大きく使用するクラスなどの場合は、要素が追加されるたびに全て生成し直されるのは都合が悪い場合があります。

これについては C++11 で実装されたムーブコンストラクタを実装することで、コピーにかかる負荷を最小限に抑えることができます。

それについては 右辺値参照とムーブコンストラクタの使い方 に詳しくまとめておきます。

クラスのポインターを扱う場合

クラスのポインターを持つ std::vector<> を作成した場合は、そこに格納したポインタが指すインスタンスの管理は自分で行う必要があります。

std::vector<CMyClass*> vector;

この場合は、push_back メソッドでの代入時のインスタンス確保と、pop_back メソッドでの破棄前に、必要なインスタンスの構築や破棄を適切に行う必要があります。

その辺りについては 可変長配列 std::vector でインスタンスのポインタを扱っている場合の削除方法 の方に整理しておきました。

□ イテレータを使って繰り返し処理を行う

std::vector<> ではイテレータを使って繰り返し処理を行えます。

このとき、イテレータの型は std::vector<>::iterator になり、これに整数を足したり引いたりすることで任意の場所へ簡単に移動することができるようになっています。

const 指定の std::vector<> の場合には、イテレータは std::vector<>::const_iterator を使います。

// イテレータを格納する変数を準備します。

std::vector<CMyClass>::iterator iterator;

// 最初のイテレータから、最後のイテレータになるまで、イテレータを一つずつ先に進めます。

for (iterator = vector.begin(); iterator != vector.end(); ++iterator)

{

// ここで、要素毎の操作を行います。

CMyClass* element = &(*iterator);

}

このように、イテレータを for 構文の中で使用して、最初の要素の先頭を使って初期化してから、最後を示すイテレータが現れるまでの間、イテレータをひとつひとつ進めることで、全ての要素を繰り返し処理しています。

このとき、end メソッドで取得できる最後のイテレータは、最後の要素の次の位置を示しているので、end メソッドによって得られたイテレータと一致したタイミングでループを抜けられます。

□ std::vector<> を並び替える

std::vector<> の配列を並び替えたい場合には <algorithm> に定義されているソート関数を使用します。

std::sort(vector.begin(), vector.end());

このようにすることで、引数に渡した std::vector<> の要素が昇順に並べ替えられます。

並び替えの判定には、要素間で < 演算子を使って判断されるようでした。また、この関数を使った場合は、値が一致した場合の並び順がどうなるかは決まっていないそうです。

単なる数値のように値が決まるような場合は、値が一致した場合の並び順は考えなくていいですけど、クラスのインスタンスのようにその他の情報も入ったオブジェクトとしてみた場合には、不都合になる場合があります。

値が一致したときに、それらの順番は元のものを維持したい場合は std::stable_sort 関数を使います。

std::stable_sort(vector.begin(), vector.end());

これにより、値が一致した場合の並び順が、元の順番と同じになります。

こちらも、並び替えの際には要素間で < 演算子を使って判断されます。

ちなみに、std::sort でも std::stable_sort でも、並び替えの処理中に、要素のコピーコンストラクタが呼ばれたり、代入演算子が実行されたりするようでした。

コピーの負荷が気になる場合は、push_back のときと同じように、扱うクラスにムーブコンストラクタを実装することで、負荷を最低限に抑えることができます。ムーブコンストラクタについては 右辺値参照とムーブコンストラクタの使い方 に詳しくまとめてあります。

扱う要素がクラスのポインタの場合には、要素の順番は変わっても破棄されることはないので、ポインタが指すインスタンスの確保や管理の心配は必要ありません。

□ std::vector<> を右辺値参照で移譲する

C++11 では、一時変数から保存用の変数に std::vector<> を移すようなときに、不必要なコピー処理を行わなくて済むようにするための右辺値参照という仕組みが規定されました。

それについては 右辺値参照とムーブコンストラクタの使い方 で詳しく紹介してありますが、std::vector<> も右辺値参照を引数に取る代入演算子とムーブコンストラクタが用意されているので、簡単に委譲することができます。

std::vecotr<CMyClass> newVector = std::move(oldVector);

このように、右辺を std::move 関数を使って明示的に右辺値参照とすることで、今回の例では oldVector に格納されている要素をそのまま newVector に移動させることができます。

このとき、右辺に指定した oldVector の内容は破壊されるので、これ以降は使えなくなります。

実際にこれを行ってみると、oldVector が持っている要素をひとつも破棄することなく、newVector に持たせる要素をひとつも新規生成することなく、std::vector<> の値を oldValue から newValue へ移行することができました。

特に std::vector<> でクラスを扱っている場合はコピーのコストが大きくなりがちなので、可能なところは積極的に使って行くのが良さそうです。

ちなみに、関数の戻り値で受け取ったクラスを変数に受けるときは、戻り値は自動的に右辺値参照として扱われるため、明示的に std::move 関数を呼び出さなくて大丈夫です。