C++編【標準ライブラリ】 第5章 vector

先頭へ戻る

この章と同じ(または似た)情報を扱うページが、Modern C++編 (C++11/14/17 対応) の以下の章にあります。

この章の概要

この章の概要です。


vector

vector は、STLコンテナの一種で、実行時に動的に要素数を変更できる動的配列です。これを使うには、<vector> という名前の標準ヘッダをインクルードする必要があります。

vector は、STLコンテナの中でも特に利用価値・利用頻度が高いので、確実に理解して、活用できるようになってください。動的に配列を確保する必要がある場面では、vector を使うことを検討してください。vector を使うことの利点については、「一時バッファとしての利用」の項で詳説します。

C++11 の場合、静的な生配列の代わりに、std::array を使うことを検討すると良いです。std::array は、テンプレート仮引数で要素数を指定できる固定配列クラステンプレートです。

vector は、次のように定義されています。

namespace std {
    template <typename T, typename Allocator = allocator<T> >
    class vector {
    };
}

この定義の理解には、少なくともクラステンプレートの基礎的な知識が必要です。【言語解説】第20章を先に学習しておいてください。本章の以降の解説は、この知識がある前提で行います。

vector はクラステンプレートなので、使用時にはテンプレート実引数の指定が必要です。テンプレート仮引数 T は、動的配列の要素の型です。例えば、int型の要素を扱いたいのであれば、以下のようになります。

std::vector<int> intVec;

もう1つのテンプレート仮引数 Allocator は、メモリ確保の方法を定義するアロケータと呼ばれるオブジェクトの指定です。テンプレート仮引数 Allocator はデフォルトテンプレート実引数を持っているので省略できます。多くの場合、省略しても vector は活用できるので、本章では解説しません。アロケータについては、第32章であらためて取り上げます。


サイズと容量

string でもそうでしたが、vector でもサイズと容量の違いを意識してください。

vector は、内部に動的な生配列を保持しています。つまり、以下のようなメンバ変数を持っているということです。

template <typename T, typename Allocator = allocator<T> >
class vector {
private:
    T*  mData;  // 動的な生配列。実際に確保されている要素数が「容量」
};

標準ライブラリ全般に言えることですが、当サイトで示す内部実装コードは例に過ぎないことに注意してください。標準規格の文面にあるルールに沿っていれば、具体的な実装方法は、ライブラリ提供者に任されていますから、当サイトで示すコードとはまったく違う方法を使っている可能性があります(当サイトのコードは、説明用にかなり単純化しています)。

この動的配列は、必要に応じて自動的に拡張されます。このときにメモリ確保を行う方法は、デフォルトでは new[] になりますが、これを変更したければ、テンプレート仮引数 Allocator を利用します(冒頭で書いたように、この件については第30章までは触れません)。

実際に確保されている動的配列の要素数が、vector においての「容量」です。容量は、capacityメンバ関数で取得できます。

一方「サイズ」は、動的配列内に実際に存在している(使用されている)要素数です。サイズは、sizeメンバ関数で取得できます。string と違い、length というメンバ関数はありません。

また、サイズが 0 かどうかを知りたいときは、emptyメンバ関数を使用できます。

string のときにも触れましたが、サイズが 0 かどうかを判定する場合は、「v.size() == 0」を使うこともできますが、emptyメンバ関数を使うのが一番間違いが無いです。これは、C++03時代の list (第6章) は sizeメンバ関数を使うと非効率である可能性があるためです。

capacityメンバ関数や、sizeメンバ関数の戻り値は std::vector::size_type型です。これは、符号無しの整数型の typedef になっています。

サイズの最大値は max_sizeメンバ関数で取得できます。これは std::vector::size_type型で表現できる最大値になっている環境が多いですが、システムの都合でより小さい値になっている可能性もあります。

ここまでに登場したメンバ関数の使用例を挙げます。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v;

    for (int i = 0; i < 5; ++i) {
        v.push_back(i);
    }

    std::cout << v.max_size() << "\n"
              << v.size() << "\n"
              << v.capacity() << std::endl;
}

実行結果

1073741823
5
6

vector のコンストラクタについては、「生成と初期化」のところで取り上げますが、引数無しならば、サイズと容量が 0 の vector が作られます。

また、push_backメンバ関数は「追加・挿入」のところで取り上げますが、引数に指定した値を、内部の動的配列の(使用されている要素の次へ)コピーするものです。後ろへ後ろへと要素を追加していく場合は、このメンバ関数が便利です。

vector の容量の拡張は、要素が追加登録されるときに、現在の容量では不足してしまう場合に自動的に行われます。例えば、先ほどのサンプルプログラムで登場した push_backメンバ関数は、このような処理を行っています。

容量の拡張時には、

  1. 新しい容量分のメモリを新たに確保する。
  2. 以前のデータを、新たなメモリ領域へコピーする。
  3. 以前のデータがあったメモリ領域を解放する。

という処理が行われますから、それなりに時間が掛かります。このとき、新たな容量がどれだけになるかは、ライブラリの実装次第であり、明確に定められてはいません。

容量の拡張によるパフォーマンスの低下を避けるために、reserveメンバ関数を使って、事前にまとまった領域を確保させることができます。

reserveメンバ関数は、string にもあり、基本的には同等のことを行いますが、vector の場合は、容量を小さくはできません。もし、現在の容量よりも小さい値を指定した場合には、何も起こりません

vector で容量を減らすには、以下のような技法を使います。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v;
    v.reserve(10000);  // 10000以上の容量を確保する
    v.push_back(0);    // 要素を1つ追加(サイズが 1 増える)

    std::cout << v.capacity() << std::endl;

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

    std::cout << v.capacity() << std::endl;
}

実行結果

10000
1

std::vector(v).swap(v); という文によって、v の元のサイズに応じた容量にまで縮小できます。「std::vector(v)」の部分は、一部オブジェクト(【言語解説】第17章)を作っています。

swapメンバ関数は、引数に指定した vector との間で、内部データを交換するものですが、このとき、新しいサイズに応じて、内部配列を確保し直すため、自分自身と交換することで、結果的に容量の削減に利用できます。

この例の場合、サイズが 1 なので、実行結果のように最終的な容量は 1 になりますが、本当にすべての内部データを削除して、容量を 0 にしたければ、次のように書けばいいです。

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

一時オブジェクトを作る際に引数を与えなければ、サイズ 0 の vector が作られるので、これと交換することで、容量を 0 にできます。

C++11(shrink_to_fitメンバ関数)

C++11 では、容量を現在のサイズにまで縮小するために、shrink_to_fitメンバ関数が追加されています。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v;
    v.reserve(10000);  // 10000以上の容量を確保する
    v.push_back(0);    // 要素を1つ追加(サイズが 1 増える)

    std::cout << v.capacity() << std::endl;

    v.shrink_to_fit();

    std::cout << v.capacity() << std::endl;
}

実行結果

10000
1

生成と初期化

vector には、複数のコンストラクタが定義されているので、さまざまな方法でインスタンス化できます。

int main()
{
    const int a[] = {0, 1, 2, 3, 4};

    std::vector<int> v1;           // 空
    std::vector<int> v2(10);       // サイズ10 (要素はデフォルトコンストラクタで生成)
    std::vector<int> v3(10, 3);    // サイズ10 (要素はコピーコンストラクタで生成)
    std::vector<int> v4(v2);       // 他の vector からコピー
    std::vector<int> v5(a, a + 5); // イテレータで指定された範囲からコピー
}

また、v1、v3、v5 の使い方の場合は、それぞれの引数の末尾にデフォルト実引数が隠されていて、ここでアロケータを指定できます。

v5 のところのコメントに書いてあるイテレータについては、後で取り上げます。このタイプのコンストラクタを使うと、既存の配列の要素を vector に取り込めます。

v2 のような方法を使った場合、引数で指定している数が「サイズ」であることに注意してください。指定した数だけ、オブジェクトが実際に生成されているので、それなりに処理時間が掛かります。もし、vector内部の動的配列を事前に確保したいという目的なのであれば、このような方法を使うのではなく、reserveメンバ関数を使うのが適切です。

std::vector<int> v(10);   // サイズが 10 (要素を作るため、10回のコンストラクタ呼び出しがある)

std::vector<int> v;
v.reserve(10);            // 容量が 10(以上) (要素は作られないので、コンストラクタの呼び出しは無い)

C++11 (生成と初期化)

C++11 で、コンストラクタ周りは強化されています。まず、std::initializer_list を使用できるようになりました。

int main()
{
    std::vector<int> v6 {0, 1, 2};       // std::initializer_list
}

また、ムーブコンストラクタが追加されています。

int main()
{
    std::vector<int> v7(std::move(v6));  // ムーブコンストラクタ
}

なお、ここまでに取り上げた方法のうち、v2 の形を除いたすべてで、引数の末尾でアロケータを指定できます。

破棄

デストラクタでは、vector が内部で確保した配列が破棄されます。

仮想デストラクタ(【言語解説】第27章)ではないので、vector を継承して使用することは不適切であることに注意してください

要素のアクセス

vector には、operator[] が用意されており、普通の配列のように [] を使った添字アクセスが可能です。

v[3] = 10;
int a = v[3];

添字に 0未満の数や、現在の「サイズ」以上の数を指定した場合、範囲外アクセスになってしまいます。これは普通の配列の場合と同じで、何が起こるか分からない危険な操作です。

vector は自動で容量を拡張するというイメージがあると間違いやすいですが、添字アクセス時には、容量の拡張は行われません。また、有効な添字の上限値が「容量 - 1」ではなく「サイズ - 1」であることに注意してください。事前に reserveメンバ関数を使って容量を拡張していたとしても、そこに要素が充填されていなければ、やはり範囲外アクセスとみなされます。

範囲外アクセスへの備えが欲しければ、atメンバ関数を使用します。atメンバ関数は、添字を引数に取り、その位置にある要素の参照を返します。[] を使う場合と違うのは、範囲外アクセスになったときに std::out_of_range例外を送出する点です

例外については、【言語解説】第32章で、std::out_of_range については第17章で解説するとして、ここでは使用例だけ挙げておきます。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v(10);

    try {
        v.at(3) = 10;
        int a = v.at(3);
        std::cout << a << std::endl;

        v.at(50) = 10;  // 範囲外アクセス

        // 実行されない
        std::cout << "!!!!!" << std::endl;
    }
    catch (const std::out_of_range& ex) {
        std::cerr << ex.what() << std::endl;
    }
}

実行結果

10
invalid vector<T> subscript

実行結果の2行目は、VisualStudio 2015/2017 の場合です。この部分は、環境によって異なるはずです。

また、vector の先頭要素(の参照)を frontメンバ関数で、末尾の要素(の参照)を backメンバ関数で取得できます。これらのメンバ関数は、vector が空の場合には未定義の動作になることに注意してください

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v(10);

    const std::vector<int>::size_type size = v.size();
    for (int i = 0; i < static_cast<int>(size); ++i) {
        v[i] = i;
    }

    std::cout << v.front() << std::endl;
    std::cout << v.back() << std::endl;
}

実行結果

0
9

C++11(dataメンバ関数)

C++11 では、vector内部で管理されている生配列の先頭メモリアドレスを返す dataメンバ関数が追加されました。

#include <iostream>
#include <vector>

void PrintArray(const int* array, std::size_t size)
{
    for (std::size_t i = 0; i < size; ++i) {
        std::cout << array[i] << std::endl;
    }
}

int main()
{
    std::vector<int> v(10);

    const std::vector<int>::size_type size = v.size();
    for (int i = 0; i < static_cast<int>(size); ++i) {
        v[i] = i;
    }

    PrintArray(v.data(), v.size());
}

実行結果

0
1
2
3
4
5
6
7
8
9

vector内部にある配列は、その要素がメモリ上に並んでいることが保証されているので、このサンプルプログラムのように、普通の配列の先頭メモリアドレスが返されたと考えて使用できます。通常の配列を使った旧式の API との連携が取りやすくなりました。

なお、dataメンバ関数が返したメモリアドレスを p とすると、p ~ p[v.size()-1] の範囲しか安全なアクセスは保証されません。また、vector が空の場合の結果は未定義です

代入

vector は、テンプレート実引数が同一であれば、代入演算子を使ってコピーできます。

また、assignメンバ関数を使うこともできます。

#include <iostream>
#include <vector>

typedef std::vector<int> IntVector;

void PrintVector(const IntVector& v)
{
    const IntVector::size_type size = v.size();
    for (IntVector::size_type i = 0; i < size; ++i) {
        std::cout << v[i] << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntVector v;

    v.assign(5, 3);  // 5個の 3 を代入
    PrintVector(v);

    const int a[10] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90};
    v.assign(a, a + 10);  // 範囲内の要素を代入
    PrintVector(v);
}

実行結果

3
3
3
3
3

0
10
20
30
40
50
60
70
80
90

assignメンバ関数の1つ目の使い方は、第2引数に指定した要素のコピーを、第1引数に指定した個数だけ代入します。

2つ目の方は、イテレータを使って範囲を指定し、その範囲内にある要素のコピーを代入します。

C++11 (代入)

C++11 の代入演算子および assignメンバ関数では、std::initializer_list を使えるようになりました。

#include <iostream>
#include <vector>

typedef std::vector<int> IntVector;

void PrintVector(const IntVector& v)
{
    const IntVector::size_type size = v.size();
    for (IntVector::size_type i = 0; i < size; ++i) {
        std::cout << v[i] << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntVector v;

    v = { 0, 1, 2 };
    PrintVector(v);

    v.assign({ 0, 10, 20 });
    PrintVector(v);
}

実行結果

0
1
2

0
10
20

また、代入演算子にはムーブ代入演算子が追加されています。

#include <iostream>
#include <vector>

typedef std::vector<int> IntVector;

void PrintVector(const IntVector& v)
{
    const IntVector::size_type size = v.size();
    for (IntVector::size_type i = 0; i < size; ++i) {
        std::cout << v[i] << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntVector v1(5, 3);
    IntVector v2;

    v2 = std::move(v1);
    PrintVector(v1);
    PrintVector(v2);
}

実行結果


3
3
3
3
3

追加・挿入

vector へ要素を追加する際、使用頻度が高いのが push_backメンバ関数です。これは、vector が管理する配列の末尾へ、引数に指定した要素のコピーを追加します。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v;

    for (int i = 0; i < 5; ++i) {
        v.push_back(i);
    }

    const std::vector<int>::size_type size = v.size();
    for (std::size_t i = 0; i < size; ++i) {
        std::cout << i << std::endl;
    }
}

実行結果

0
1
2
3
4

要素を任意の位置へ挿入するには、insertメンバ関数を使います。

#include <iostream>
#include <vector>

typedef std::vector<int> IntVector;

void PrintVector(const IntVector& v)
{
    const IntVector::size_type size = v.size();
    for (IntVector::size_type i = 0; i < size; ++i) {
        std::cout << v[i] << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntVector v(5, 3);

    IntVector::iterator it;

    it = v.insert(v.end() - 1, 0); // 末尾に 0 を挿入
    PrintVector(v);

    v.insert(it, 3, 99);           // 0 の手前に 99 を 3個挿入
    PrintVector(v);

    const int a[] = {10, 11, 12};
    v.insert(v.begin(), a, a + 3); // ある範囲から先頭へ挿入
    PrintVector(v);
}

実行結果

3
3
3
3
0
3

3
3
3
3
99
99
99
0
3

10
11
12
3
3
3
3
99
99
99
0
3

使い方が3通りありますが、どれでも第1引数が挿入位置を表しています。挿入位置は、イテレータを使って指定し、そのイテレータが指している位置へ挿入されます。例えば、「v.begin()」で取得したイテレータを指定すれば、先頭要素になるように挿入できます。

1つ目の使い方では、第2引数に挿入する値を指定します。この形式の場合は、戻り値で、挿入された値を指すイテレータが返されます。

2つ目の使い方では、同じ値を複数個まとめて挿入できます。第2引数が個数、第3引数が挿入する値です。

3つ目の使い方では、第2第3の引数で指定した範囲内にある要素を挿入します。これは、別のコンテナや配列からコピーしたい場合に使います。

push_backメンバ関数、insertメンバ関数によって要素を挿入する際、容量が不足している場合には、自動的に容量の拡張が行われます。この辺りは、「サイズと容量」の項で説明しています。

また、insertメンバ関数の場合、要素が途中に割り込んでくることになりますから、後続の要素のメモリアドレスが変化します。そのため、挿入位置より後ろの要素を指していたイテレータやポインタは、不適切な位置を指してしまうので、そのまま使用してはいけません。あらためて、取得し直す必要があります。

C++11(移動による挿入)

C++11 では、移動による挿入ができるようになっています。まず、push_backメンバ関数が対応しています。

v.push_back(std::move(value));

insertメンバ関数の場合は、挿入する要素が1つだけになる形式のみ対応します。

v.insert(it, std::move(value));

C++11(emplace_back、emplace)

push_back関数や insert関数は、vector の外で挿入するオブジェクトを作り、それをコピー(または移動)する必要があります。これは、少なくとも一時オブジェクトを生成するコストが掛かるため(コピーの場合は、さらにコピーのコスト)、使い方によっては非効率さがあります。

C++11 では、要素のコンストラクタに渡す引数だけを指定し、メンバ関数内でオブジェクトを作らせるという方法が使えるようになりました。push_backメンバ関数なら emplace_backメンバ関数が、insertメンバ関数なら emplaceメンバ関数が対応します。

std::vector<MyClass> v;

v.push_back(MyClass(10, "abc"));   // 一時オブジェクトを作ってコピー
v.emplace_back(10, "abc");         // コンストラクタの引数だけ指定し、関数内で生成

v.insert(it, MyClass(10, "abc"));  // 一時オブジェクトを作ってコピー
v.emplace(it, 10, "abc");          // コンストラクタの引数だけ指定し、関数内で生成

insertメンバ関数はオーバーロードされていますが、emplaceメンバ関数は1つだけです。もちろん、emplace_backメンバ関数、emplaceメンバ関数の場合も、容量が不足していれば自動的に拡張されます。

C++11(insert の std::initializer_list対応)

C++11 では、insertメンバ関数が std::initializer_list に対応しています。

v.insert(it, {10, 20, 30});

C++11(insert のイテレータの const化)

C++03 までの insertメンバ関数は、要素の挿入位置を指定する第1引数の型が、std::vector::<T>::iterator型になっていました。そのため、この引数の意味は、挿入位置を示すことだけなので constイテレータで問題ないはずなのに、constイテレータを渡すことができません。

C++11 では、第1引数の型が std::vector::<T>::const_iterator型に改められています。

削除

要素を削除する方法はいくつかありますが、その前に「削除」の意味を確認しておきます。

vector に限らず、コンテナから要素を削除するということは、コンテナ内部の管理領域から要素を取り除くということです。特に重要な点として、外部で new によって作られたオブジェクトをコンテナに管理させている場合に、要素をコンテナから「削除」しても、delete される訳ではないということです。delete する責任はプログラマ側にあるので、コンテナから「削除する」前に、delete を実行しておかなければなりません

要素を削除する方法の1つ目は、pop_backメンバ関数です。これは、push_backメンバ関数の逆操作で、末尾にある要素を削除するものです。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int*> v;

    v.push_back(new int(10));

    delete v.back();
    v.pop_back();
}

実行結果




最初に説明したように、要素が new で確保されたものであるならば、delete が必要です。

デストラクタで delete するような補助クラスを利用し、要素をラップした方が安全です。いわゆるスマートポインタが利用できる場面ですが、std::auto_ptr(第16章)は STLコンテナの要素にすべきではない点に注意してください。C++11以降であれば、std::unique_ptr 等を使うのがいいでしょう。C++03以前の場合は、自分でクラスを用意しましょう。

要素を削除するには、eraseメンバ関数を使うこともできます。こちらはより汎用的です。

#include <iostream>
#include <vector>

typedef std::vector<int> IntVector;

void PrintVector(const IntVector& v)
{
    const IntVector::size_type size = v.size();
    for (IntVector::size_type i = 0; i < size; ++i) {
        std::cout << v[i] << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntVector v;

    for (int i = 0; i < 5; ++i) {
        v.push_back(i);
    }

    v.erase(v.begin());  // 先頭要素を削除
    PrintVector(v);

    v.erase(v.begin() + 1, v.end());  // 先頭の次から末尾まで削除
    PrintVector(v);
}

実行結果

1
2
3
4

1

eraseメンバ関数の使い方は2通りで、イテレータを1つ渡すか、2つ渡すかの違いです。前者の場合はイテレータが指す要素を削除し、後者の場合は2つのイテレータで作られる範囲内の要素が削除されます。

要素が削除されることによって、その位置より後方にあった要素のメモリアドレスが変わり得るため、それらの要素を指していたポインタ、参照、イテレータが無効になることに注意してください。

なお、要素が減ったからといって、容量が減る訳ではありません。実際に容量を減らしたければ、「サイズと容量」の項で説明している方法を使わなければなりません。

eraseメンバ関数は、削除された要素の次の有効な要素を指すイテレータが返されます。vector をループを使って走査し、条件に合う要素だけを削除する場合、次のように書けます。

#include <iostream>
#include <vector>

typedef std::vector<int> IntVector;

void PrintVector(const IntVector& v)
{
    const IntVector::size_type size = v.size();
    for (IntVector::size_type i = 0; i < size; ++i) {
        std::cout << v[i] << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    const int a[] = {0, 3, 2, 3, 3};
    IntVector v(a, a + 5);

    // 値が 3 の要素をすべて削除する
    for (IntVector::iterator it = v.begin(); it != v.end(); /* ここでインクリメントしないこと */) {
        if (*it == 3) {
            it = v.erase(it);  // 次の要素を指すイテレータを受け取る
        }
        else {
            ++it;
        }
    }

    PrintVector(v);
}

実行結果

0
2

インクリメントをする位置に注意してください。eraseメンバ関数の戻り値を受け取ってイテレータを更新する場合は、そのイテレータが既に「次の要素」を指しているので、さらなるインクリメントをしないようにします。

また、ループの終了条件を確認するため、endメンバ関数の戻り値を毎回取得し直すことにも注意が必要です。 人によっては、

const IntVector::iterator itEnd = v.end();
for (IntVector::iterator it = v.begin(); it != itEnd; ) {
}

こういう形でループを書きたいと思うかもしれませんが、これだと要素が削除された瞬間に、endメンバ関数が返したイテレータが無効になるので、正しく動作しません。

このような方法で vector から要素を削除するには、かなり気を使って実装しなければなりません。より安全に書くためには、こういった処理は自前で書かずに、STLアルゴリズム第18章)を使うべきです。STLアルゴリズムの remove関数第22章)を使えば、同じ処理を次のように書けます。

#include <iostream>
#include <vector>
#include <algorithm>

typedef std::vector<int> IntVector;

void PrintVector(const IntVector& v)
{
    const IntVector::size_type size = v.size();
    for (IntVector::size_type i = 0; i < size; ++i) {
        std::cout << v[i] << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    const int a[] = {0, 3, 2, 3, 3};
    IntVector v(a, a + 5);

    // 値が 3 の要素をすべて削除する
    v.erase(std::remove(v.begin(), v.end(), 3), v.end());

    PrintVector(v);
}

実行結果

0
2

数ある STLアルゴリズムを覚えたり、調べたりするのは大変ですし面倒かもしれませんが、圧倒的に安全ですし、実は効率的でもあります。

最後に、要素をすべて削除する場合ですが、これは clearメンバ関数を使うだけです。

#include <iostream>
#include <vector>
#include <cassert>

int main()
{
    std::vector<int> v;

    for (int i = 0; i < 5; ++i) {
        v.push_back(i);
    }

    v.clear();
    assert(v.empty());
}

実行結果




この場合も「容量」は減らないことに注意してください。

C++11(erase のイテレータの const化)

C++03 までの eraseメンバ関数は、要素の位置を指定するイテレータが、std::vector::<T>::iterator型になっていました。そのため、この引数の意味は、位置を示すことだけなので constイテレータで問題ないはずなのに、constイテレータを渡すことができません。

C++11 では、イテレータの型が std::vector::<T>::const_iterator型に改められています。

イテレータ

イテレータについては、string のところでも取り上げました。また、STL全般に関わるテーマなので、第14章であらためて取り上げます。

vector の先頭要素を指すイテレータを beginメンバ関数で、末尾要素の次を指すイテレータを endメンバ関数で取得できます。また、逆方向に走査するための逆イテレータの場合に最初の要素を指すイテレータを rbeginメンバ関数で、最後の要素の次を rendメンバ関数で取得できます。

#include <iostream>
#include <vector>

int main()
{
    typedef std::vector<int> IntVector;

    IntVector v;

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

    IntVector::const_iterator itEnd = v.end();
    for (IntVector::const_iterator it = v.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;

    IntVector::const_reverse_iterator ritEnd = v.rend();
    for (IntVector::const_reverse_iterator rit = v.rbegin(); rit != ritEnd; ++rit) {
        std::cout << *rit << "\n";
    }
    std::cout << std::endl;
}

実行結果

0
1
2
3
4
5
6
7
8
9

9
8
7
6
5
4
3
2
1
0

beginメンバ関数や endメンバ関数で取得できるイテレータの型は、std::vector<T>::iterator型、あるいはその const版である std::vector<T>::const_iterator型です。後者の場合は、イテレータを通して要素を書き換えることができません。

また、rbeginメンバ関数、rendメンバ関数の場合は、std::vector<T>::reverse_iterator型、あるいはその const版である std::vector<T>::const_reverse_iterator型になります。

これらイテレータの型は、vector内部で typedef されているものですが、その正体(typedef の元になる型) が何であるかは実装依存です。vector の場合は、テンプレート仮引数T に合わせた単なるポインタ (T*型) であることが多いですが、そうでないこともあり得ます。そのため、次のようなコードには移植性がありません。

int* p = v.begin();

C++11(const版のイテレータ取得関数)

C++11 には、必ず constイテレータを返す cbegin、cend、crbegin、crend の各メンバ関数が追加されています。

もともと、begin、end、rbegin、rend の各メンバ関数は、非constイテレータを返すものと constイテレータを返すものとでオーバーロードされており、constイテレータ型の変数で受け取れば、const版を使えました。

新たにこれらのメンバ関数が追加された意義はいくつかあると思いますが、例えば、C++11 で追加された auto(【言語解説】第7章)を使いやすくすることが考えられます。

std::vector<int> v;
auto it = v.begin();   // こう書くと std::vector<int>::iterator型
auto it = v.cbegin();  // こう書くと std::vector<int>::const_iterator型

生配列との連携

vector の内部にある要素を、通常の配列のように扱えると便利なことがあります。例えば、vector の要素を配列へコピーしたいとき、memcpy関数のようなコピー関数が使えれば簡単です。

vector の内部にある動的配列のメモリアドレスは、次のようにすれば取得できます。

std::vector<int> v(10);

int* p = &v[0];

要素が連続的に並んでいるので、こうして取得したメモリアドレスを使って memcpy関数などの関数を使用できます。ただし、v が空の状態で「v[0]」をすると未定義な動作になってしまうので注意が必要です。また、後述する vector<bool> の場合には、このような方法が使えないことに注意してください。

C++11(dataメンバ関数の利用)

C++11 ならば dataメンバ関数があるので、これを使いましょう。


ところで、beginメンバ関数を使って、先頭要素のイテレータを取得する方法では代用できないことに注意してください。イテレータ(std::vector<T>::iterator型) の正体は、ポインタではない可能性があるからです。もし、イテレータを使いたいのなら、次のように書く必要があります。

int* p = &*v.begin();  // *演算子で間接参照後、メモリアドレスを取得

一時バッファとしての利用

要素数が事前に分からないとき、new[] を使って配列を確保しようとすることがあります。

void func(int size)
{
    int* array = new int[size];

    // 何か処理する

    delete [] array;
}

new[] を呼び出した場合、確実に delete[] を呼び出す必要があります。func関数の処理内容が後から増えるたび、注意深く delete[] の呼び出し抜けが無いことを確認しなければなりません。例えば、if文が増えて途中で return する経路ができるかもしれませんし、例外の送出によって関数を抜け出すことがあるかもしれません。このような可能性を常に考えに入れながらプログラムを書くことは、大変な労力になります。そこで、vector を使用します。

void func(int size)
{
    std::vector<int> v(size);

    // 何か処理する
}

vector が破棄されるときに、デストラクタが動的な配列を解放してくれるので、どのような方法で func関数を抜け出すとしても問題ありません。

new[] を使うことはできるだけ避けて、vector を使うようにしましょう。

配列でなく単体のオブジェクトのために new を使う場合は、std::auto_ptr(第16章)のようなスマートポインタを使いましょう。

vector<bool>

vector のテンプレート仮引数 T に bool を指定した場合、ここまでに取り上げた vector とは異なる特別バージョンになります。これは、テンプレートの特殊化(【言語解説】第26章)という機能を使っているためです。

std::vector<bool> は、要素として bool型(【言語解説】第7章)を使う vector な訳ですが、bool型の動的な配列を作るのではなく、1つの bool値に対して 1ビットだけを使うようにサイズを圧縮しています。実際にどの程度、サイズを削減できるかは実装によりますが、普通の整数型がどんなに小さくとも 1バイトの大きさを持つことから、少なくとも 8分の1 には圧縮されるはずです(1バイト=8ビットを想定)。

std::vector<bool> は、通常の vector が持っている機能を使える他、追加のメンバ関数もあります。flipメンバ関数を使うと、要素を反転 (true なら false に、flase なら true に)できます。

#include <iostream>
#include <vector>

int main()
{
    typedef std::vector<bool> boolVector;

    boolVector v(10);

    v[3] = true;
    v.flip();

    for (boolVector::size_type i = 0; i < v.size(); ++i) {
        std::cout << std::boolalpha << v[i] << std::endl;
    }
}

実行結果

true
true
true
false
true
true
true
true
true
true

std::vector<bool> の要素の初期値は false になります。flipメンバ関数を呼び出すと、すべての要素が反転します。

また、添字演算子が返す参照から、flip関数を呼び出せます。

#include <iostream>
#include <vector>

int main()
{
    typedef std::vector<bool> boolVector;

    boolVector v(10);

    v[3].flip();

    for (boolVector::size_type i = 0; i < v.size(); ++i) {
        std::cout << std::boolalpha << v[i] << std::endl;
    }
}

実行結果

false
false
false
true
false
false
false
false
false
false

こんなことができるのは、添字演算子が bool型のような組み込み型への参照を返しておらず、内部にある補助クラスオブジェクトへの参照を返しているからです。詳しい内容は割愛しますが、この例で呼び出している flip関数を持っているのは、この補助クラスの方です。

このような補助クラスはプロキシ(代理)と呼ばれます。デザインパターンでいうところの Proxyパターンです。有用なテクニックなので、Proxyパターンについて調べてみるか、実際に std::vector<bool> の実装を覗いてみると良いでしょう。

このように、std::vector<bool> は特殊な実装であるため、STLコンテナとしての要件を満たしていません。例えば、次のコードがコンパイルできません。

std::vector<bool> v;
bool* p = &v[0];

また、次の assert も失敗してしまいます。

std::vector<bool> v;
assert(&v[0] + 1 == &v[1]);  // 失敗

こういった問題があると、STLコンテナとは言えません。もし、std::vector<T> を扱う関数を作ったとして、その関数の内容によっては、T が bool のときにだけコンパイルできなかったり、おかしな動作を起こしたりするかもしれません。

std::vector<bool> が STLコンテナではないという点、またその理由を理解しているのならば、使っていけないということはありませんが、基本的には使わずに済むのなら使わない方がいいと言われています

もし、必要なビット数が静的に決まるのであれば、代わりに std::bitset(第13章)を使ってください。動的でなければならない場合で、サイズの削減が目的でないのなら(単に bool型のコレクションが欲しいだけ)、std::deque(第7章) を使うのが無難です。動的でなければならない場合で、かつ本当にサイズの削減が必要ならば、注意して std::vector<bool> を使うか、別のクラスを用意することになります。

この手の汎用的なクラスは、既に誰かが作っているでしょう。有名どころでは、boost の dynamic_bitset があります。


練習問題

問題① あなたの使っているコンパイラにおいて、空の vector はどれだけのサイズと容量を持つか調べてみてください。

問題② 次のプログラムには、vector の使い方に関するいくつかの問題が潜んでいます。指摘してください。

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v;

    v[3] = 3;

    v.resize(100);

    int* p = &v[10];

    v.insert(v.begin(), 200);

    *p = 10;
}

問題③ この章のサンプルプログラム内で何度か登場した PrintVector関数を、イテレータを使った方法で書き直してください。


解答ページはこちら

参考リンク



更新履歴

'2018/4/5 VisualStudio 2013 の対応終了。

'2018/4/2 「VisualC++」という表現を「VisualStudio」に統一。

'2018/2/22 「サイズ」という表記について表現を統一。 型のサイズ(バイト数)を表しているところは「大きさ」、要素数を表しているところは「要素数」。

'2018/1/5 コンパイラの対応状況について、対応している場合は明記しない方針にした。

'2017/7/30 clang 3.7 (Xcode 7.3) を、Xcode 8.3.3 に置き換え。

≪さらに古い更新履歴を展開する≫



前の章へ (第4章 STLコンテナ)

次の章へ (第6章 list)

C++編のトップページへ

Programming Place Plus のトップページへ


はてなブックマーク Pocket に保存 Twitter でツイート Twitter をフォロー
Facebook でシェア Google+ で共有 LINE で送る rss1.0 取得ボタン RSS
管理者情報 プライバシーポリシー