C++の基礎 - STL(vector)

概要

C++ STLでは、vectorクラス(以下、vectorと呼ぶ)が存在する。
ここでは、vectorの基本的な使い方や利点について記載する。

vectorの利点

• size()で配列要素数を参照できるため、関数に渡しやすい。(アドレス渡し、参照渡しが可能)
• size()でインデックスの上限を指定すると境界エラーが起きない。
• resize(要素数)で要素数を変更できる。
• push_back(データ)で1つずつ要素を追加できる。
• =(代入演算子)でvecorクラスがコピーできる。
• 関数の戻り値に指定できる。
• STLのalgorithmでソートできる。
• erase(インデックス)で指定要素のみ削除できる。
• 1行でstring型にargvを格納できる。

vectorを使用する前に

vectorを使用するためには、以下ののヘッダファイルをインクルードする必要がある。

 #include <vector>

宣言と初期化

1次元配列

1次元配列のvectorの宣言は以下の通りである。
intやdouble等の基本的な型のみならず、任意で作成したクラスも使用できる。
ここで、Tはデータ型、Nは要素数、dは初期化する値を表すものとする。

 vector<T> v;
 vector<T> v();
 vector<T> v(N);
 vector<T> v(N, d);

2次元配列

2次元配列のvectorの宣言は以下の通りである。
ここで、Mは要素数を表すものとする。

 vector<vector<T>> vv;
 vector<vector<T>> vv();
 vector<vector<T>> vv(N);
 vector<vector<T>> vv(N, vector<T>(M));
 vector<vector<T>> vv(N, vector<T>(M, d));

要素へのアクセス

vectorでは、通常の配列と同様の記述で要素へアクセスすることができる。

1次元配列

v[]のi番目にdを代入して、それを出力する場合は以下となる。

 v[i] = d;
 cout << v[i] << endl;

2次元配列

v[][]のi番目およびj番目にdを代入して、それを出力する場合は以下となる。

 v[i][j] = d;
 cout << v[i][j] << endl;

要素数の変更

vectorでは、配列の要素数を変更することができる。

1次元配列

v[]の要素数をN個に変更する場合は以下の通りである。

 v.resize(N);

2次元配列

vv[][]の要素数をN * Nに変更する場合は以下の通りである。

 // 方法 1
 vv.resize(N);
 for(int i = 0; i < N; i++)
 {
    vv[i].resize(N);
 }
 
 // 方法 2
 vv.resize(N, vector<T>(N));

末尾に要素を追加

1次元配列

v[]の末尾にデータを追加する場合は以下の通りである。

 v.push_back(d);

2次元配列

vv[][]のi番目の末尾にデータを追加する場合は以下の通りである。

 vv[i].push_back(d);

サイズの確認

空かどうかを確認

std::vectorクラスが空かどうかを確認する場合、いくつかの方法が存在する。

• emptyメソッドを使用する。(推奨)

  コードの意図が明確である。

  多くの実装では、O(1)の時間複雑度で動作する。

  他のSTLコンテナでも同様に使用できる。

 std::vector<int> vec;
 
 if (vec.empty()) {
    std::cout << "Vector is empty" << std::endl;
 }
 else {
    std::cout << "Vector is not empty" << std::endl;
 }

• sizeメソッドを使用する。

  ただし、emptyメソッドの方がベクトルが空かどうかを確認する意図をより明確に表現することができる。

 std::vector<int> vec;
 
 if (vec.size() == 0) {
    std::cout << "Vector is empty" << std::endl;
 }
 else {
    std::cout << "Vector is not empty" << std::endl;
 }

• ベクトルの開始と終了イテレータを比較する。

 std::vector<int> vec;
 
 if (vec.begin() == vec.end()) {
    std::cout << "Vector is empty" << std::endl;
 }
 else {
    std::cout << "Vector is not empty" << std::endl;
 }

• std::ranges::emptyメソッドを使用する。(C++20以降)

  この方法は、std::vectorクラスだけでなく、他の範囲 (range) に対しても同様に使用できるため、より汎用的である。

 #include <ranges>
 
 std::vector<int> vec;
 
 if (std::ranges::empty(vec)) {
    std::cout << "Vector is empty" << std::endl;
 }
 else {
    std::cout << "Vector is not empty" << std::endl;
 }

vectorのコピー

vectorをコピーする方法は複数存在する。
ここでは、v1[]をv2[]にコピーする方法を記述する。

 // 方法 1
 v2 = v1
 
 // 方法 2
 v2.resize(v1.size());
 for(int i = 0; i < v1.size(); i++)
 {
    v2[i] = v1[i];
 }
 
 // 方法 3
 copy(v1.begin(), v1.end(), v2.begin());

vectorの全要素を末尾に追加

v1[]をv2[]の末尾に追加する方法は以下の通りである。(方法3が最も簡潔)

 // 方法 1
 int size = v2.size();
 v2.resize(size + v1.size());
 for(int i = 0; i < v1.size(); i++)
 {
    v2[i + size] = v1[i];
 }
 
 // 方法 2
 for(int i = 0; i < v1.size(); i++)
 {
    v2.push_back(v1[i]);
 }
 
 // 方法 3
 copy(v1.begin(), v1.end(), back_inserter(v2));

指定範囲をコピー

v1[]のa番目からb番目をv2[]にコピーする方法は以下の通りである。(方法2が簡潔)

 // 方法 1
 v2.resize(b - a);
 for(int i = 0; i < v2.size(); i++)
 {
    v2[i] = v1[a + i];
 }
 
 // 方法 2
 copy(v1.begin() + a, v1.begin() + b, v2.begin());

vectorを関数の引数にする

vectorは、関数の引数にすることができる。
また、vectorのメンバ関数から要素数を参照することができるため、関数内で簡単にループ数を指定できる。
ここでは、総和を求めるプログラムとvectorの全要素を表示するプログラムを例として挙げる。
ただし、処理時間などの理由から参照渡しを使用して、vectorの内容を変更しない場合はconstを付加する。

 // 配列の総和を求めるプログラム
 T SumVector(const vector<T> &v)
 {
    T sum = 0;
 
    for(int i = 0; i < v.size(); i++)
    {
       sum += v[i];
    }
 
    return sum;
 }
 
 // vectorの全要素を表示するプログラム
 // 一次元vectorの場合
 void view(const vector<T> &v)
 {
    for(int i = 0; i < v.size(); i++)
    {
       cout << v[i] << " ";
    }
    cout << endl;
 }
 
 // 二次元vectorの場合
 void view(const vector<vector<T>> &vv)
 {
    for(int i = 0; i < vv.size(); i++)
    {
       for(int j = 0; j < vv[i].size(); j++)
       {
          cout << vv[i][j] << " ";
       }
       cout << endl;
    }
 }

関数の戻り値にする

vectorは、戻り値にも使用できる。
しかし、戻り値にするとvectorをコピーするために時間が掛かるので、引数として参照渡しする方がよい
以下のサンプルコードでは、ventorの全要素をscale倍している。

 vector<int> ScalarVen(const vector<int> &v, int scale)
 {
    vector<int> mul(v.size());
    for(int i = 0; i < mul.size(); i++)
    {
       mul[i] = v[i] * scale;
    }
 
    return mul;
 }

ソート

vectorでは、sort関数を使用することで昇順ソートおよび降順ソートを行うことができる。

 // 昇順ソート
 sort(v.begin(), v.end());
 
 // 降順ソート
 sort(v.begin(), v.end(), greater<int>());

指定要素の削除

vectorでは、erase関数を使用することで任意の要素を削除することができる。

 // 先頭の要素を削除する
 v.erase(v.begin());
 
 // 末尾を削除する
 v.erase(v.end());
 
 // 先頭からi番目の要素を削除する
 v.erase(v.begin() + i);

コマンドライン引数(argv)をvectorに格納する

コマンドライン引数(int argcとchar *argv[])を取得する。
vector<string>を使用すると良い。

 #include <vector>
 #include <string>
 
 int main(int argc, char *argv[])
 {
    vector<string> args(argv, argv + argc);
 
    return 0;
 }

要素の反転

std::reverseアルゴリズムは、STLアルゴリズムの一部であり、任意の範囲の要素の順序を逆にすることができる。
最初と最後のペアから始まる2つの要素を内部的に交換する。また、指定された範囲のイテレータを表す2つの引数を取る。

以下の例では、文字をvectorとして生成して、std::reverseアルゴリズムを使用して反転している。

 #include <iostream>
 #include <iterator>
 #include <iomanip>
 #include <vector>
 
 int main()
 {
    std::vector<char> arr = {'h', 'o', 'g', 'e'};
 
    //size_t width = 4;
    //arr.reserve(width);
 
    std::cout << std::left << std::setw(10) << "arr: ";
    copy(arr.begin(), arr.end(), std::ostream_iterator<int>(std::cout,"; "));
    std::cout << std::endl;
 
    std::reverse(arr.begin(), arr.end());
 
    std::cout << std::left << std::setw(10) << "arr: ";
    copy(arr.begin(), arr.end(), std::ostream_iterator<int>(cout,"; "));
    std::cout << std::endl;
 
    return EXIT_SUCCESS;
 }

// 出力例
arr:      h; o; g; e;
arr:      e; g; o; h;

要素の回転

std::rotateは、要素を左にシフトして、ベクトル境界の外側に移動された要素をラップする。
std::rotateはForwardItイテレータの3つの引数を取り、第2引数が指す要素が、新しく生成されたリストの最初の位置に移動するように回転する。

 #include <iostream>
 #include <iterator>
 #include <iomanip>
 #include <vector>
 
 int main()
 {
    std::vector<int> arr = {1, 2, 3, 4, 5, 6};
 
    std::cout << std::left << std::setw(10) << "arr: ";
    copy(arr.begin(), arr.end(), std::ostream_iterator<int>(std::cout, "; "));
    std::cout << std::endl;
 
    std::rotate(arr.begin(), arr.begin() + (arr.size() / 2), arr.begin() + arr.size());
 
    std::cout << std::left << std::setw(10) << "arr: ";
    copy(arr.begin(), arr.end(), std::ostream_iterator<int>(std::cout, "; "));
    std::cout << std::endl;
 
    return EXIT_SUCCESS;
 }

// 出力例
arr:      1; 2; 3; 4; 5; 6;
arr:      4; 5; 6; 1; 2; 3;

要素の並べ替え(ランダム)

std::shuffleを使用して、要素の各順列が等しい確率を持つように、範囲内の要素をランダムに並べ替えることができる。

この関数は、範囲の開始イテレータと終了イテレータの少なくとも2つの引数が必要である。
また、乱数ジェネレータ関数を表す第3引数を指定することもできる。

以下の例では、第3引数において、randomヘッダファイルにあるmersenne_twister_engineを使用している。

 #include <iostream>
 #include <iterator>
 #include <iomanip>
 #include <random>
 #include <vector>
 
 int main()
 {
    std::vector<int> arr = {1, 2, 3, 4, 5, 6};
 
    std::cout << std::left << std::setw(10) << "arr: ";
    copy(arr.begin(), arr.end(), std::ostream_iterator<int>(std::cout,"; "));
    std::cout << std::endl;
 
    // vecotorの要素をランダムに並べ替える
    std::shuffle(arr.begin(), arr.end(), std::mt19937(std::random_device()()));

    std::cout << std::left << std::setw(10) << "arr: ";
    copy(arr.begin(), arr.end(), std::ostream_iterator<int>(std::cout,"; "));
    std::cout << std::endl;
 
    return EXIT_SUCCESS;
 }

// 出力例
arr:      1; 2; 3; 4; 5; 6;
arr:      5; 1; 4; 6; 2; 3;

Range Based Loop

vectorに対するループ文は、インデックスを使用するよりもRange Based Loopを使用した方が良い。
以下のサンプルコードに、Range Based Loopを使用したループ文を記述する。

 // 1次元vectorの場合
 void view(const vector<T> &v)
 {
    for(const auto &element : v)
    {
       cout << e << " ";
    }
 
    cout << endl;
 }
 
 // 2次元vectorの場合
 void view(const vector<vector<T>> &vv)
 {
    for(const auto &v : vv)
    {
       for(const auto &element : v)
       {
          cout << element << " ";
       }
 
       cout << endl;
    }
 }

要素の検索

algorithmのfindメソッドを使用して、要素を検索をすることができる。

 #include <algorithm>
 
 vector<string> vec = {"hoge", "piyo", "fuga", "foo", "bar"};
 
 if (find(vec.begin(), vec.end(), "fuga") != vec.end()) std::cout << "検索成功" << std::endl;
 else                                                   std::cout << "検索失敗" << std::endl;

全要素の入れ替え

swapメソッドを使用して、2つのvecorクラスの全要素を入れ替えることができる。

 vector<int> vec1 = {10, 20, 30, 40, 50};
 vector<int> vec2 = {100, 200, 300};
 
 // 全要素の入れ替え
 vec1.swap(vec2);  // または、vec1.swap(vec1, vec2);

vectorの解放 (Swap技法)

関数内にて宣言して使用するvectorは、その関数を抜ければ自動でメモリの解放を行うが、
クラスのメンバ変数としてvectorを使用する場合は、クラスのデストラクタが実行されるまでメモリの解放を行わない。

例えば、vectorのclear()関数を実行した場合、要素数は変化するがメモリは解放されない。
特に、サイズの大きい構造体などが解放されないと問題になる時がある。

そこで使用されるのがSwap技法と呼ばれる手法である。
これは、vectorのswap()関数を使用して一時オブジェクトと交換することで、vectorのデストラクタを強制的に実行させる。

 // クラス内に要素数100のvectorを宣言
 std::vector<int> m_vec(100);
 
 // Swap技法によるメモリの解放
 std::vector<int>().swap(m_vec);