●C++編(標準ライブラリ) 第2章 vector

'2010/9/18 「イテレータ」の説明を修正。
'2009/4/9 全面的に文章を修正・加筆。「容量に関すること」「生の配列との関連」「vector<bool>」を追加。
'2007/12/21 erase() の使い方について修正。
'2006/3/26 ソース中の誤りを修正。
'2005/5/3 「テンポラリバッファとしての利用」を追加。
'2005/4/10 シーケンスコンテナ、連想コンテナという用語を追加。
'2005/4/6 erase()の使い方について修正。

このページは移転予定です。移転先はこちらです

○vectorとは

vectorは動的配列をテンプレートクラスで表現したものです。 動的配列なので、その要素数は必要なときに自動的に変更されます。 通常の配列は、宣言時に要素数を指定しなければなりませんが、vector を使えばその必要がなくなります。

要素数が自動的に変更されると書きましたが、vector はある程度の個数分の領域を事前に一括で確保しておき、 それが足りなくなったとき(新たに要素を追加しようとして、足りなかったとき)に、領域を拡張するのです。


STL に含まれる vector や list(第3章)のように、 データを管理するテンプレートクラスをコンテナと呼びます。

コンテナのうち、vector や list のように、要素が連続的に並ぶコンテナのことをシーケンスコンテナと呼びます。 また、set(第9章)や map(第10章)のように、 要素が常にソートされた状態を保つようなコンテナを連想コンテナと呼びます。

○基本的な使い方

それでは、まずは使ってみましょう。

#include <vector>
#include <iostream>

int main()
{
	using namespace std;

	vector<int> array;  // int型の動的配列
	int i;

	// 10個の要素を追加していく
	for( i = 0; i < 10; ++i )
	{
		array.push_back( i );
	}

	// 10個の要素を出力
	for( i = 0; i < 10; ++i )
	{
		cout << array[i] << endl;
	}

	return 0;
}

vector は std という名前空間に含まれています。 vector をインスタンス化するときに、要素数を指定する必要はなく、冒頭に書いたように、必要に応じて動的に領域が拡張されます。 動的に拡張されるということは、vectorクラスの内部でメモリ確保を行っているので、 場合によっては、処理速度やメモリの断片化などの問題が起こるかも知れません。

そういったことが問題になる場合、コンストラクタに size_type型の引数を与えれば、それに従ってあらかじめ要素を確保してくれます

vector<int> array( 1000 );  // 初期状態で 1000個分のメモリ空間を持つ int型の動的配列

この場合、要素はデフォルトコンストラクタで初期化されます。 そのため、要素の型が、引数無しで呼び出せるコンストラクタを持っていない場合、この方法での事前確保は行えません。

いずれにしても、大抵の場合、目的としているのは「要素を増やす時に動的確保が発生することを防ぐ」という部分にあるので、 デフォルトコンストラクタを呼び出すのは無駄です。 その場合、代わりの手段として reserve() を使います。

vector<int> array;  // 引数なし
array.reserve( 1000 );   // ここで 1000個分の領域を確保

reserve() は指定された数の要素をただちに確保します。 ただし、指定された数の通りに確保される保証はなく、それより多めに確保される可能性があります(コンパイラ次第)。 また、既に確保済みの要素数よりも少ない値を指定した場合は、何も起こりません。 縮小してくれる訳ではないので注意して下さい。


vector に要素を追加するには、専用のメンバ関数を使用します。 これにはpush_back()insert() という2つの関数が用意されています。 push_back() は、動的配列の末尾に新しく要素を追加し、insert() は途中に追加します。 ただし、insert() はイテレータという新しい概念を理解しないと使えないので、とりあえず後に回します。

push_back() の方の使い方は簡単で、追加したい要素を引数に指定して呼び出すだけです。 要素を追加したとき、vectorクラスが内部的に持っているメモリが足りなければ、一括していくらかのメモリが確保されます。 メモリが足りている内は確保を行いません。

各要素へは []演算子を使ってアクセスできます。これは通常の配列と同じ動作です。 まだ確保していない要素を表す添字を使ってアクセスしてしまった場合の挙動も、通常の配列と同様で未定義になっています。

なお、vector が内部で確保したメモリ領域は、当然ながらデストラクタによって自動的に解放されます。

○基本操作

続いて、もう少し機能を使った例を見てみましょう。

#include <vector>
#include <iostream>

int main()
{
	using namespace std;

	vector<int> array1;  // int型の動的配列
	vector<int> array2;  // int型の動的配列
	int i;

	for( i = 0; i < 10; ++i )
	{
		array1.push_back( i );
		array2.push_back( 9 - i );
	}

	if( array1 == array2 )  // ==演算子で比較
	{
		cout << "一致しました" << endl;
	}

	array2.clear();                 // clear()で全ての要素を削除する
	cout << array1.size() << endl;  // size()で要素数取得
	if( array2.empty() )            // empty()で空かどうか調べる
	{
		cout << "array2は空です" << endl;
	}

	for( i = 0; i < 10; ++i )
	{
		array1.pop_back();          // pop_back()で末尾の要素削除
	}

	return 0;
}

まず、オーバーロードされている演算子についてですが、 ==、!=、<、<=、>、>=、=、[] の各演算子があります。 ==演算子と !=演算子は、2つの vector同士をまとめて比較します。 全ての要素が同じならば ==演算子の結果が真になります。!=演算子なら逆の結果になります。 <演算子などは、2つの vector の要素数による比較が行えます。 =演算子は、片方の vector の全要素を、もう一方の vector に代入します。 []演算子は、先程登場したように、添字によるアクセスを行ないます。

clear() は、vector に含まれている全ての要素を削除します。 1つずつ削除したいときは、pop_back()erase() を使います。 pop_back() は末尾の要素を削除します。これは戻り値として要素を返すようなことはしません。 erase() は、イテレータについて学ぶ必要があるので、後に回します。

size() は要素数を返します。 空かどうか調べる場合は string のときと同じく、empty() を使う方が効率がよくなります。

○イテレータ

コンテナ内の要素を効率的にアクセスするための仕組みとして、イテレータ(反復子)というものがあります。

イテレータ自体にも種類がありますが(詳細は第12章を参照)、 今回はイテレータの解説ではなく vector の解説が主題なので、多くは触れません。

以下は、イテレータを使って vector内の要素をアクセスするプログラムです。

#include <vector>
#include <iostream>

int main()
{
	using namespace std;

	vector<int> array;   // int型の動的配列
	int i;

	for( i = 0; i < 10; ++i )
	{
		array.push_back( i );
	}

	vector<int>::iterator it = array.begin();  // イテレータのインスタンス化
	while( it != array.end() )  // 末尾要素まで
	{
		cout << *it << endl;  // *演算子で間接参照
		++it;                 // イテレータを1つ進める
	}

	return 0;
}

上の例は、イテレータの最も基本的な使い方です。 iterator は、vector や list のようなコンテナに含まれた型の名前です。 そのため、

コンテナ名<コンテナ内のデータ型>::iterator イテレータ名;

のような形で宣言できます。 イテレータはイメージ的には、コンテナ内の要素だけに限定されたポインタです(後述するように、本当にポインタであるという保証はありません)。

まず、先ほどのサンプルプログラムのように、 コンテナに用意されているbegin() というメンバ関数を使って、先頭の要素を指すように初期化します。 begin() は、先頭要素を指すイテレータを返す関数です。
同様に end() は、末尾要素の1つ後ろを指すイテレータを返します。 1つ後ろを指す理由は、上のプログラム例のように、ループの終了条件に利用するためです。

iterator に対して ++演算子及び --演算子を使うと、そのイテレータが指しているコンテナ内を、要素1つ分だけ進めたり、戻したりできます。 また、*演算子を使うと、イテレータが現在指している要素を間接参照できます。 *演算子の動作は正にポインタそのものです。
しかし、コンテナの中の要素のアドレスを取得しようとして、

vector<int>::iterator it = vec.begin();   // vec は vector<int>型の変数
it++;
int* p = it;  // 内部要素のアドレスを取得しようとしている?

のように書くのは間違いです。 イテレータの正体が単なるポインタである場合は多いものの、それはコンパイラの実装次第であり、標準規格としては、そのような保証はありません。 正しくは、次のように書きます。

vector<int>::iterator it = vec.begin();   // vec は vector<int>型の変数
it++;
int* p = &*it;  // 内部要素のアドレスを取得しようとしている。OK

格好悪いですが、これでイテレータの指している要素を間接参照し、その結果のアドレスを得ることになるので、正しく動作します。


さて、vector には insert() と erase() というメンバ関数がありますが、これらは iterator を使います。

#include <vector>
#include <iostream>

int main()
{
	using namespace std;

	vector<int> array;   // int型の動的配列
	int i;

	for( i = 0; i < 10; ++i )
	{
		array.push_back( i );
	}

	vector<int>::iterator it = array.begin();
	++it;
	it = array.erase( it );      // itの位置の要素を削除
	array.insert( it, 999 );     // itの位置に999を挿入

	for( it = array.begin(); it != array.end(); ++it )
	{
		cout << *it << endl;
	}

	return 0;
}

insert() は、第1引数に指定した iterator が指す位置に要素を挿入します。 挿入する要素は第2引数に指定します。

erase() は、指定した iterator が指す要素を削除します。 注意が必要な点として、erase() は削除された要素および、その後続にある全ての要素を指しているイテレータを無効な状態にしてしまいます。 (なぜなら、vector の内部は通常の配列のように要素が並んでいるため、途中の要素を削除したら、後続を詰め直す必要があるからです)。

無効なイテレータというのは、正しい場所を指していない状態と考えて下さい。 無効なイテレータを使って、要素をアクセスしてはいけません。 erase() は、戻り値で有効な状態のイテレータを返すので、上のサンプルのように、必ず戻り値を受け取る必要があります

この erase() の特性は、vector の他にも、 前章の string や、第4章で紹介する deque にも当てはまります。 他のコンテナにも erase() という名前のメンバ関数がありますが、これらは特性が異なるので注意が必要です。その辺りは、改めて説明します。

○テンポラリバッファとしての利用

よく一時的な領域(テンポラリバッファ)が必要になることがあります。 固定長の配列で構わない場面ならば関係ありませんが、どれだけの領域が必要になるのかが実行時にまで判断できない場合、new演算子を使って、

char *buf = new char[size];

のような形で確保しなければなりません。 もちろん、これで正しく動作させられるのですが、new演算子を使うと、delete を忘れないようにしなくてはなりません。 例えば、

void function(int size)
{
	char *buf = new char[size];
	
	// 何か処理する
	
	delete [] buf;
}

のようになります。 最初は問題なくても、後から処理を追加し、その追加部分では何らかのエラーが発生し得るとします(ファイルを開くなどの処理)。 すると、途中で関数から強制的に return する可能性が出てきます。 あるいは例外が発生するかも知れません。

このように後から処理を追加し、その部分で関数から抜け出してしまう場合に、忘れずに delete を書くことができるでしょうか。 確実に忘れないとは言い切れないでしょう。

そこで、このような一時的な領域は、できるだけ vector を使って確保するようにします。

void function(int size)
{
	vector<char> buf( size );
	
	// 何か処理する
}

このようにします。こうすると new演算子が vector の内部に隠されるので、delete を明示的に呼び出す必要がなくなります。 また、どのような形で、この関数から抜けようとも、必ず vector のデストラクタが呼び出されます(例外が発生した場合でも同様です)。 そのため、解放に関する問題がなくなります。

なお、バッファというよりも、単体のオブジェクトが一時的に必要となる場合なら、vector の代わりに、auto_ptr を使うのが一般的でしょう。 auto_ptr については、第26章で説明します。

○容量に関すること

vector は内部に一括確保した領域を保持しています。 この領域が足りなくなるときに、新しくより広大な領域を確保し、既存の要素をそちらへコピーします。 その後、古い領域は解放されてなくなります。 (内部の具体的な実装はコンパイラ次第ですが、大体の動作はこのような感じです)。

この挙動から、「要素を追加したときには、既存の要素のアドレスが変わり得る」という重要な点に気付きます。 従って、イテレータが指し示していた先も不正な場所になってしまう可能性があります。

そのため、push_back() や insert() を呼び出したとき、それより前の時点で変数に保存しておいたアドレスやイテレータは、 すべて破棄しなければなりません


一方、要素を削除したときですが、この場合は後続の要素が前に詰められるだけであり、内部の領域が縮小することはありません。 前にも書きましたが、削除後は後続の要素を指していたポインタやイテレータは全て無効になることに注意して下さい

ところで、領域が縮小されないということは、一度確保してしまった領域は、不要になってもメモリを返却してくれないということです。 一応、次のような swap技法と呼ばれるテクニックを使えば、強制的に領域を切り詰めることは可能です。

std::vector<int>(array).swap(array);

一時オブジェクトを作り、既存の vector をコンストラクタの引数に渡します。 すると、既存の vector が持っていた要素と同じ個数を持った vector が作られます。 それを swap関数で、既存の vector と交換すると、要素の中身はそのままで、無駄な領域だけが消え去ります。

コンパイラによっては、これと同じ効果のある関数を用意しているものもありますが、 それは標準規格には存在しないものです。


vector の容量については、「現在、実際に使っている分」と「とりあえず一括で確保してある分」という2つの見方があることを理解しておくべきです。 前者は size() で、後者は capacity() で取得できます。 両者の差分が「要素を追加しても、領域の拡張が起こらない個数」ということになります。

capacity() で返される数を超えようとしたときに、内部で領域の拡張が行われます。 このとき、多くの実装では、既存の個数を2倍した個数の領域を作ります。 そのため、拡張が起こるたびに、拡張にかかる処理時間は増加していくことになります。

○生の配列との関連

領域は、C/C++ の標準の配列と同様、メモリ上に連続的に並んでいることは保証されているので、 vector で保持していた領域を、生の配列を要求する関数(もちろん、配列の先頭アドレスを要求する、が正しい表現ですが)に渡す際には、次のように書けます。

void func(int* array);
std::vector<int> v;

func( &v[0] );  // 生の配列の先頭アドレスを渡す

イテレータを使って、

func( v.begin() );

のように書いてしまいそうになりますが、これでは駄目です。前にも書きましたが、イテレータがポインタとは限りません。 これが問題なく通ってしまうコンパイラもありますが、保証されたものではありません。

○vector<bool>

vector の中でも、vector<bool> の場合だけは特別に事情が異なります。 これは、テンプレートの特殊化と呼ばれるもので、型T の部分が bool の場合の話です。 (テンプレートの特殊化は、言語解説編第37章を参照)。

vector<bool> は、ビット単位の要素を管理するために、特別にメモリ領域を切り詰めた実装がなされています。 具体的には、要素1個に対して 1ビットしか使わないようになっています。 従って、通常の実装よりもメモリ容量を 8分の1 にまで抑えることができます。

この特殊な実装のために、要素のアドレスが取れず(バイト単位になっていないため)、イテレータもうまく機能しなくなってしまいます。 また、処理効率に関しては、むしろ悪くなってしまいます。 この辺りの事実を知らない人が、通常の vector の知識だけでコードを読むと、大きな間違いを犯すことも考えられるので、 基本的に vector<bool> は使うべきではありません

もし、このようなビット単位の動的配列が必要ならば、bitset(第8章参照)という代わりのクラスが用意されていますから、 そちらを使うべきです。


C++編(標準ライブラリ)のトップページに戻る

サイトのトップページに戻る