ViVi Home > 技術文書
> さくさく理解する C/C++ コンソールアプリ入門
>
手を動かしてさくさく理解する C++ 動的配列イテレータ std::vector::iterator 入門
本章では、vector オブジェクトの宣言・初期化方法について説明する。
vector オブジェクトを宣言するには、空vectorを宣言する、サイズを指定して宣言する、サイズと全てのデータを指定して宣言する、 元データを指定して宣言する、他のオブジェクトを元にして宣言する、のようにいくつもの方法がある。 本章ではそれらの方法を順次解説する。
ローカル変数またはグローバル変数として vector オブジェクトを宣言すると、オブジェクトが生成され利用可能になる。
これらはスコープを外れると自動的に破棄される。
通常のクラスなので new で生成し、delete で破棄することも可能だ。
宣言方法を具体的に説明する前に、vector を使うための準備について説明する。
vector は C++標準のライブラリであり、「#include <vector>」を記述することで利用可能になる。
名前空間は「std」なので、使用の度に「std::」を前置するか、または「using namespace std;」を記述しておく。
#include <vector> // ヘッダファイルインクルード
int main()
{
std::vector<int> v; // ローカル変数として、v を生成
.....
}
#include <vector> // ヘッダファイルインクルード
using namespace std; // 名前空間指定
int main()
{
vector<int> v; // ローカル変数として、v を生成
.....
}
std::vector オブジェクトを生成するには「std::vector<型> オブジェクト名;」 と記述する。
オブジェクト名とは、宣言する動的配列を識別するための名前のことだ。変数名と言ってもよい。 vector
はクラスなので、それを実体化したものはオブジェクトまたはインスタンスと呼ばれる。
下記は、int 型の動的配列 data を宣言している例だ。
std::vector<int> data; // int 型の動的配列 data の宣言
当然、型の部分はどんな型でも構わない。char や double や、自分で定義した構造体、クラスでもOKだ。
※ ただし、初期化時にデフォルトコンストラクタ、バッファ拡張時にコピーコンストラクタが呼ばれことがあるので、
それらがちゃんと定義されている必要がある。
また、vector などのコンテナクラスを指定することも出来る（参照：2次元配列）。
通常の配列宣言の「型 配列名[要素数];」とはちょっと順序が違うが、似たような感じだ。
「std::vector<型>
オブジェクト名;」には要素数の指定が無いじゃないかと気づいた人は観察力がある。要素数の指定方法は次節で説明する。
このようにして宣言したオブジェクトの要素数は0だ。データを追加するには次の章で説明する push_back() などを使う。
< > は何だ？と思う人もいるかもしれない。これはC++のテンプレートという機能を使うための記法だ。
テンプレートを完全に理解するのは難易度が高いので、深く理解しようとすると先に進めなくなる。
深入りはせず、現在のところはこういう書き方をすると覚えてほしい。
動的配列は後でサイズを増減させることが出来るが、データ領域の確保・破棄とデータのコピー処理を伴う場合があり、若干の処理時間を要する。
なので、最初の要素数が分かっている場合は、要素数を指定してオブジェクトを作るようにした方がよい。
構文は「std::vector<型> オブジェクト名(要素数);」だ。
std::vector<int> data(123); // int 型で、初期要素数 123 の動的配列 data の宣言
配列では要素数を「[要素数]」で指定するが、vector では「(要素数)」で指定する。実はこれ、コンストラクタの引数なのである。
要素数を指定するだけでなく、全要素の値を指定して初期化することも可能だ。
「std::vector<型> オブジェクト名(要素数,
値);」と記述すると、指定された数の要素を確保し、全ての要素を指定された値で初期化する。
std::vector<int> data(10, 5); // 要素数10、全ての要素の値5 で初期化
上記の方法では、値が全て同じ場合でないと初期化できない。
「std::vector<型> オブジェクト名(型* first, 型* last);」と記述すると、first から last
が指す先までのデータで動的配列を初期化する。 厳密に言うと、last は最後の元データの次を指す。[first, last)
の範囲を元に、動的配列を初期化する。
通常配列でデータを指定し、それを元に動的配列を構築し初期化出来る。
int org_data[] = {4, 6, 5}; // 元データ
std::vector<int> data(org_data, org_data + 3); // 元データから動的配列を生成
配列末尾へのポインタは org_data + 3 と記述しているが、データ配列サイズが変わった時に、修正しなくてはならないので、危険だ。
C++0x（VS2010以上）で std::end(配列名) という関数が追加され、配列末尾へのポインタを返してくれるようになった。
これを使えば、上記は下記のように記述することが出来る。
int org_data[] = {4, 6, 5}; // 元データ
std::vector<int> data(org_data, std::end(org_data)); // 元データから動的配列を生成
実は上記の記述方法は古い書き方で、C++11（VS2013以上）から vector の初期化で初期値を直接指定可能になった。
「std::vector<型> オブジェクト名{値0, 値1, 値2, ... 値N-1};」と記述できる。
std::vector<int> data{4, 6, 5}; // データ列を指定して動的配列を生成
こちらの方法の方が直感的で分かりやすく、行数も短い。C++11 が利用可能であれば、この記法を使うことを強く薦める。
※ ちなみに、「std::vector<型> オブジェクト名 = {値0, 値1, 値2, ... 値N-1};」と書いてもよい。
コピーコンストラクタとは、同じ型のオブジェクトを渡され、それと同じ内容のオブジェクトを生成するコンストラクタのことである。
「std::vector<型> オブジェクト名(コピー元オブジェクト名);」と記述する。
当然ながら、コピー元オブジェクトと生成するオブジェクトは通常同じ型である。
※ 暗黙の型変換が可能な型であれば、コピー元オブジェクトとして指定可能ではある。
std::vector<int> org{1, 2, 3};
std::vector<int> x(org); // コピーコンストラクタ
上記のコードは org をコピーするので {1, 2, 3} という値をもつ動的配列 x を生成する。
「std::vector<std::vector<型>> オブジェクト名;」の様に、vector を入れ子にすることで、2次元以上の配列を宣言できる。
2次元配列は、C++11 であれば、以下の様に通常配列と同じ様に初期化することが可能。
std::vector<std::vector<int>> vv{{1, 2, 3}, {4, 5, 6}};
※ 「>>」は右シフト演算子なので、C++11未満では「> >」と、間に空白を入れる必要があった。 Visual Studio では VS2010 から「>>」をサポートしている。
このようにして生成した2次元配列は、vv[x][y] の様に、普通の多次元配列と同様にアクセスできる。
もっと入れ子を深くすれば、３次元や４次元も可能である。
演習問題：解答例
[] 演算子（operator[](int)） を使って、普通の配列と同じように、配列要素値の参照・代入が可能。
operator[](int)
と聞くと身構える人がいるかもしれないが、「data[10]」の様に、普通の配列の要素にアクセスする時と同じ記述だ。 恐れることは何も無い。
下記は、配列要素値の参照と代入例。普通の配列要素の参照・代入とまったく同じでしょ。
std::vector<int> data{3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
for (int i = 0; i < 10; ++i)
std::cout << data[i]; // data の i 番目の要素を表示
const int SZ = 10; // 要素数
std::vector<int>v(SZ); // 指定要素数で、vector を生成
for(int i = 0; i < SZ; ++i)
v[i] = i; // 要素を 0, 1, 2, 3, ... 9 に設定
VC++ の場合、動的配列の範囲外のデータをアクセスすると、デバッグモードであればアサーション例外が発生する。
リリースモードでは通常配列と同じように範囲外の部分を何事も無かったかのようにアクセスする。
C/C++ の配列は高速性を優先するために、添字の範囲チェックを行わない。
それが元で原因不明のバグに悩まされることもままある。
vector を使い、デバッグモードでテストをするようにすれば、そのようなバグはたちどころに発見することができるぞ。
普通の配列同様、「int *ptr = &v[0];」の様に記述することで要素へのポインタを取得することが出来、
ポインタ経由で要素を参照・修正することが出来る。
これは、vector の要素は連続する領域に格納されていることが保証されているからだ。
後で説明する v.data() でデータ領域先頭アドレスを取得することもできる。&v[0] と書くのと等価だ。
演習問題：解答例
データを末尾に追加するには push_back(d); を使う。
std::vector<int> v; // 空の動的配列を生成
v.push_back(123); // 末尾に 123 を追加
処理時間は O(1) で高速。O(式) は処理時間を表す数学的な記法。「ビッグ・オー記法」と呼ばれる。 O(1)
は配列要素数に依らず常に一定時間で処理出来るという意味で、高速なのだ。
通常、データの追加はこのメンバ関数のみを使用する。
※ 細かいことを言うと、push_back(値) が呼ばれたとき、既に確保したメモリに空きがない場合は、
メモリを再アロケート、データをコピー、以前のメモリを破棄、という処理が行われる。 これはデータ数が多い場合は結構重い処理なのだが、配列サイズが
0 から N になるまで push_back() を繰り返しても、 log N / log 2 回（または log N / log
1.5回）しか行われない。 なので厳密には O(1) ではないのだが、実質的には O(1) と理解しておいてよい。
なにがなんでも任意の場所にデータを挿入したい場合は insert(iterator, 値) を使う。
insert(iterator, 値) は、第1引数に挿入する場所へのイテレータを、第2引数に挿入するデータを指定する。
イテレータとは抽象化されたポインタのこと。ちゃんとした説明は長くなるし、初級者には理解が大変なのでここでは省略する。
i 番目に挿入したい場合は「オブジェクト名.begin() + i」と書くと覚えて欲しい。
std::vector<int> v(10, 3); // 値が３，個数10個
v.insert(v.begin() + 4, 7); // [4] の位置に 7 を挿入
// 結果は {3, 3, 3, 3, 7, 3, 3, 3, 3, 3, 3} となる
※ 個人的には insert(size_t index, 値) というメンバ関数があってもよいと考えるが、何故無いのだろう？
insert() の処理時間は O(N) 。O(N) とは配列要素数に比例して処理時間を要するという意味。
データ数が100倍になると、処理時間も100倍になる。
データをずらす処理を行う必要があるので、その分処理時間を食うというわけだ。
それに対して push_back() は O(1) なので、データ数がいくら増えても常に一定時間で処理が終わる。
データ列の途中に頻繁に挿入・削除を行うのであれば std::list や、ギャップベクターなど他のコンテナクラスの使用を検討すべき。
データ列の先頭にのみ頻繁に挿入・削除を行うのであれば std::deque がお薦め （実際、ス
ネークゲームでは、胴体座標の管理に std::deque を使用している）である。
ただし、データ数が少ない（数10個程度）場合であれば、vector は十分高速なので、処理時間は問題にはならない。
そんな場合は vector を使用すべきである。
演習問題：解答例
最後の要素を削除したい場合は pop_back() を用いる。
std::vector<int> v{3, 1, 4, 1, 5};
v.pop_back(); // 末尾データ（この場合は 5）を削除
pop_back() も push_back() 同様、処理時間は O(1) と高速である。
空の vector に対して、pop_back() を実行するとデバッグモードでは例外が発生する。
リリースモードでは内容が不正になるようだ（VS2013）。
次の章で説明する empty() または size() で vector が空でないことを確認するようにした方がよい。
pop_back() は何故か void 型で、削除した値を返さない。 なので、最後の要素の値を取り出して削除したい場合は、後で説明する back() を使用する。
任意の位置の要素を削除したい場合は erase(iterator) を使用する。
std::vector<int> v{3, 1, 9, 4};
v.erase(v.begin() + 2); // 3番目の要素（9）を削除
erase() で途中の要素を削除すると、サイズが一つ減り、削除された要素以降のデータがひとつずつ前に移動される。
イテレータは前節で言及したように、削除する要素位置を示すもので、i 番目の要素は「オブジェクト名.begin() + i」で指定する。 本稿ではイテレータに関する詳しい説明は行わない。
演習問題：解答例
ここまで、動的配列の宣言、値の参照・代入・追加・削除方法について説明した。 それらを使えば通常配列を動的配列に置き換えることができるはずだ。
実は動的配列には上記以外にも便利な機能がメンバ関数としていくつも用意されている。
配列が空かどうかをチェックしたり、要素数を調べたり、サイズを変更することもできる。
これらは通常配列に対する明らかなアドバンテージである。
「bool empty()」は動的配列が空かどうかを判定する関数。
次に出てくる size() を使って、size() == 0 と判定するのと同等だ。 が、コンテナクラスによっては size() 計算よりも
empty() の方が高速な場合がある。 なので、vector などのコンテナクラスに対しては empty() を使うことが推奨されている。
「size_t size()」は、要素数を返す関数。
通常配列だと「sizeof(data)/sizeof(data[0])」のように記述しないと、要素数を取得できないが、 vector
であれば「data.size()」と簡潔かつ分かりやすく書ける。
※ size_t はサイズを表す型で、符号なし整数の組み込み型である。ちなみに、sizeof() も size_t 型を返す。
「size_t capacity()」は、動的配列が確保しているメモリに入る要素数、すなわち現在のデータ領域容量を返す関数。
vector は実際の要素数より若干大目にメモリを確保している。これは要素が増えた時、常にメモリを再確保するのではなく、
余裕を持たせておくことで、頻繁なメモリ確保とデータのコピーを避けるためだ （参照：動
的配列クラス 演習問題の図）。
「front()」は先頭要素を返す関数。「オブジェクト名[0]」と記述するのと同等。
「back()」は末尾要素を返す関数。「オブジェクト名[オブジェクト名.size() - 1]」と記述するのと同等。
front() はあまりありがたみが無いが、back() はタイプ数が大幅に減るし、分かりやすいので存在価値が高いぞ。
「data()」は配列データ先頭アドレスを返す関数。「&オブジェクト名[0]」と記述するのと同等。
vector は通常配列と同じようにデータ領域が連続したアドレスだということが保証されている。
なので、データアドレスを他の関数に渡して処理することも可能だ。
「clear()」は動的配列を空にする関数。
サイズを0にするだけ。メモリが解放されるわけではない。 メモリを解放したい場合は後で説明する shrink_to_fit() または
swap() イディオムを使用する。
「resize(size_t sz)」は要素数を指定サイズに設定する関数。
sz が現在のキャパシティを超えていれば、メモリがアロケートされ,データがコピーされる。
サイズが増えた部分の値を指定したい場合は、「resize(size_t sz, 値)」と、第2引数で値を指定する。
サイズが減っても、その分のメモリが解放されるわけではない。 不要になったメモリを解放したい場合は後で説明する shrink_to_fit()
または swap() イディオムを使用する。
「reserve(size_t sz)」はキャパシティを指定する関数。
データを大量に追加する場合、メモリのアロケートとデータコピーが多く呼ばれる場合がある。
そうなるとパフォーマンスが低下する場合があるので、追加するデータの数が予めわかっていれば、reserve()
でメモリを確保する方がパフォーマンス的に好ましい。
std::vector<int> v;
v.reserve(10000); // 予め1万個分の領域を確保しておいた方が高速
for(int i = 0; i < 10000; ++i)
v.push_back(i);
「swap(オブジェクト名)」は引数で指定されたオブジェクトと内容を入れ替える関数。
std::vector<int> v, z;
v, z にデータを追加
v.swap(z); // v と z の内容を入れ替える
先に書いたように、clear() を行ってもメモリは解放されないので、C++11以前では以下のようなコードが使用されていた。
std::vector<int> v;
v にデータを追加;
std::vector<int>().swap(v); // 空のテンポラリオブジェクトを生成し、中身を入れ替える
「shrink_to_fit()」は、C++11 で追加された関数で、キャパシティを現在のサイズの値にし、余分なメモリを解放する関数。
C++11以前では、shrink_to_fit() がなかったので以下のようなイディオムが使用されていた。
std::vector<int> v;
v にデータを追加;
std::vector<int>(v).swap(v); // v をコピーしたテンポラリオブジェクトを生成し、中身を入れ替える
演習問題：解答例
vector はクラスなので、vector オブジェクトを引数として関数に渡すことが可能です。
例えば、下記の様に vector<int> を引数とし、要素の最大値を返す関数を定義することが出来ます。
int max(std::vector<int> v)
{
int maxVal = INT_MIN; // 整数最小値
for(int i = 0; i < (int)v.size(); ++i) {
if( v[i] > maxVal )
maxVal = v[i];
}
return maxVal;
}
int main()
{
std::vector<int> v;
v に要素を追加;
int mx = max(v);
.....
}
上記関数は正しく動作するのですが、引数の型が実体になっているので、関数コール時にコピーコンストラクタが呼ばれて、
コピーされたオブジェクトが関数に渡されます。
要素数が多い場合、コピーコンストラクタの処理はそれなりに重くなります。
なので、コピーする必然性がなければ、実体ではなく参照渡しにするのが普通です。
int max(std::vector<int> &v)
{
..... // 中身はいっしょ
}
こうしておけば、関数に渡されるのはオブジェクトのアドレスなので、処理時間を要することはありません。
さらに言えば、この場合は、関数の中で配列要素を修正しないので、const std::vector<int> &v
とした方がよいです。
当然ながら、関数内で要素を修正する場合は、const を付けないようにします。
このように、std::vector は簡潔な表記で、関数の引数としてオブジェクトを渡すことが可能です。
それに比べ通常配列だと、サイズ情報を保持していないので、引数に要素数または最後のアドレスを指定する必要があります。
この点も std::vector が優れているところです。
実は C++ には結構便利なアルゴリズムがいくつも用意されている。
参照：http://www.cplusplus.com/reference/algorithm/
ここでは、vector に対して特によく使うであろうアルゴリズムを3つだけ簡単に説明する
「accumulate(オブジェクト名.begin(), オブジェクト名.end(),
init)」は、動的配列の最初から最後まで、要素を積算（全加算）するものだ。 最後の引数は初期値で、通常は0を指定する。
なお、accumulate を利用するには「#include <numeric>」が必要。
#include <numeric>
.....
std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::cout << std::accumulate(v.begin(), v.end(), 0) << "\n";
一部を積算したい場合は、「accumulate(v.begin() + i, v.begin() + k,
0)」の様にイテレータで範囲を指定する。
「accumulate(&v[i], &v[k], 0)」のように、要素へのポインタで指定することも可能。
「sort(オブジェクト名.begin(), オブジェクト名.end())」は、動的配列の要素を昇順にソートしてくれる関数だ。
なお、accumulate を利用するには「#include <algorithm>」が必要。
#include <algorithm>
.....
std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
std::sort(v.begin(), v.end());
一部をソートしたい場合は、「sort(v.begin() + i, v.begin() + k)」の様にイテレータで範囲を指定する。
「sort(&v[i], &v[k])」のように、要素へのポインタで指定することも可能。
「reverse(オブジェクト名.begin(), オブジェクト名.end())」は、動的配列の要素を逆順にする関数だ。
演習問題：解答例
通常、std::vector はテンプレートライブラリになっており、ソースが公開されている。
ソースを探しだして、読んでみると勉強になるかもしれない。
ただし、かなりレベルが高いコードなので、ちゃんと理解するのはそれなりの能力と知識と経験が必要だ。
上級者でないと無理だ。ちょっと見て理解不能と思ったら、すぐに勇気ある撤退をしよう。
型固定の動的配列 Vector を実装する演習問題も用意してい
る。
これをやり遂げれば、vector の中身がどうなっているか、ある程度想像がつくようになるので、ぜひ挑戦してみて欲しい。
std::vector<char> str;
std::vector<double> pos(3);
std::vector<char> a(10, 'a');
std::vector<double> d{1.1, 2.2, 3.3, 4.4};
std::vector<int> org{1, 2, 3};
std::vector<int> x(org); // コピーコンストラクタ
std::vector<int> v(100);
for(int i = 0; i < 100; ++i)
v[i] = rand() % 100;
for(int i = 0; i < 100; ++i)
std::cout << v[i] << "\n";
std::vector<int> v(10);
std::cout << v[20] << "\n";
std::vector<int> v;
for(int i = 1; i <= 10; ++i)
v.push_back(i);
std::vector<int> v(10, 0);
v.insert(v.begin() + 5, 7);
std::vector<int> v{3, 1, 4, 1};
v.pop_back();
std::vector<int> v;
cout << v.empty() << "\n";
cout << v.size() << "\n";
cout << v.capacity() << "\n";
std::vector<int> v{3, 1, 4};
cout << v.empty() << "\n";
cout << v.size() << "\n";
cout << v.capacity() << "\n";
std::vector<int> v{3, 1, 4};
cout << v.front() << "\n";
cout << v.back() << "\n";
cout << v.capacity() << "\n";
std::vector<int> v{3, 1, 4};
int *ptr = v.data();
std::vector<int> v{3, 1, 4};
v.clear();
cout << v.empty() << "\n";
cout << v.size() << "\n";
cout << v.capacity() << "\n";
std::vector<int> v{3, 1, 4};
v.resize(8);
cout << v.empty() << "\n";
cout << v.size() << "\n";
cout << v.capacity() << "\n";
std::vector<int> v{3, 1, 4};
v.resize(1);
cout << v.empty() << "\n";
cout << v.size() << "\n";
cout << v.capacity() << "\n";
std::vector<int> v{3, 1, 4};
v.reserve(8);
cout << v.empty() << "\n";
cout << v.size() << "\n";
cout << v.capacity() << "\n";
std::vector<int> v{3, 1, 4};
v.reserve(1);
cout << v.empty() << "\n";
cout << v.size() << "\n";
cout << v.capacity() << "\n";
std::vector<int> v{3, 1, 4};
v.resize(1);
cout << v.empty() << "\n";
cout << v.size() << "\n";
cout << v.capacity() << "\n";
v.shrink_to_fit();
cout << v.empty() << "\n";
cout << v.size() << "\n";
cout << v.capacity() << "\n";
std::vector<int> v{3, 1, 4};
std::vector<int> z{8, 9};
v.swap(z);
for(int i = 0; i < (int)v.size(); ++i)
std::cout << v[i] << "\n";
for(int i = 0; i < (int)z.size(); ++i)
std::cout << z[i] << "\n";
int dd[][3] = {{1, 2, 3}, {4, 5, 6}};
std::vector<std::vector<int>> vv;
vv.push_back(std::vector<int>(dd[0], std::end(dd[0])));
vv.push_back(std::vector<int>(dd[1], std::end(dd[1])));
#include <numeric>
.....
std::vector<int> v(100);
for(int i = 0; i < (int)v.size(); ++i)
v[i] = rand() % 100;
std::cout << std::accumulate(v.begin(), v.end(), 0) << "\n";
#include <algorithm>
.....
std::vector<int> v(100);
for(int i = 0; i < (int)v.size(); ++i)
v[i] = rand() % 100;
std::sort(v.begin(), v.end());
#include <algorithm>
.....
std::vector<int> v(100);
for(int i = 0; i < (int)v.size(); ++i)
v[i] = rand() % 100;
std::sort(v.begin(), v.end());
std::reverse(v.begin(), v.end());