【C++】std::vectorの基本的な使い方

動的配列vectorについて使い方のメモ． 適宜追記していく．

初期化

1次元

#include <vector>

using namespace std;

void initialize() {
  // 空のvectorとして初期化
  vector<int> vec1;

  // 要素数(10)を指定して初期化
  vector<int> vec2(10);

  // 要素数(10)と初期値(0)を指定して初期化
  vector<int> vec3(10, 0);

  // データ列を指定して初期化
  vector<int> vec4{1, 2, 3, 4};  
}

多次元

#include <vector>

using namespace std;

void initialize() {
  // 
  vector<vector<int>> m_vec1(10, vector<int>(5, 0));

  // 
  vector<vector<int>> m_vec2 = {
    {0, 1, 2, 3},
    {4, 5, 6, 7},
    {8, 9, 10, 11},
  };
}

要素の参照

#include <vector>

using namespace std;

void ref() {
  vector<int> vec(10);
  for (int i = 0; i < 10; i++) {
    vec[i] = 1;  // vec.at(i)でもOK
  }

  vector<vector<int>> m_vec(10, vector<int>(5, 0));
  for (int i = 0; i < 10; i++) {
    for (int j =0; j < 5; j++) {
      m_vec.at(i).at(j) = i * j;  // 多次元ベクトルへのアクセスはat(index)を複数回使う
    }
  }
}

イテレータ

  • イテレータは抽象化されたポインタ
  • *演算子で要素の参照・変更ができる
  • イテレータのインクリメント・デクリメントで前後の要素へ移動できる
vector<int> v{1, 2, 3, 4};
auto iter = v.begin();  // vector<int>::iterator iter = v.begin(); でもOKだが，記述が面倒なので型推論のautoを通常使う
cout << *iter << endl;  // 1と表示
iter++;
cout << *iter << endl;  // 2と表示
*iter = 9;  // 2番目の要素を9に変更
cout << *iter << endl;  // 9と表示

イテレータを使ったLoop

vector<int> v{1, 2, 3, 4};

for (auto iter = v.begin(); iter != v.end(); ++iter) {
  cout << *iter << endl;
}

アルゴリズム

count：値が一致する要素のカウント

vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

int n = count(v.begin(), v.end(), 5);  // 5に一致する要素数を返す

int i = 2, j = 7;
int n_ranged = count(v.begin() + i, v.begin() + j, 5);  // 3(= 2+1) ~ 8(= 7+1)の範囲で5に一致する要素数を返す

sort：要素のソート

vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
sort(v.begin(), v.end());  // {1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9}のように昇順にソートされる

reverse：順序の反転

vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
reverse(v.begin(), v.end());  // {5, 3, 5, 6, 2, 9, 5, 1, 4, 1, 3}のように逆順にソートされる

// 降順にソート = 昇順ソート + 反転
vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
sort(v.begin(), v.end());
reverse(v.begin(), v.end());

find：値が動的配列に含まれるかのチェック

  • find(v.begin(), v.end(), value)はvを最初から最後まで走査し，valueに一致する初めての要素のイテレータを返す
  • どの要素とも一致しなかった場合は，v.end()を返す
vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
auto iter = find(v.begin(), v.end(), 5);

if (iter != v.end()) {
  // 見つかった場合の処理
}

要素数が多い場合

  • 要素が変わらず，かつ要素が含まれるかの探索を何度も行う場合は2分探索の方が効率が良い
    • sortはO(N*logN)なので毎回sortが必要になるとかえって遅くなる
    • sortが1度で済む(=要素が不変な場合)は効率が良い
  • findはO(N)，2分探索はO(logN)

max(min)_element：最大値・最小値とその要素を見つける

#include <vector>
#include <numeric>

int main() {
  vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
  // *_element は，イテレーターを返すので '*' で値を取得する
  vector<int>::iterator min_iter = min_element(v.begin(), v.end());
  vector<int>::iterator max_iter = max_element(v.begin(), v.end());
  cout << "min: " << *min << ", " << "max: " << *max << endl;

  // distance で vec の先頭イテレーターと minIt, maxIt との距離を取得する．
  // インデックスを取得したいときは，vec の先頭イテレーターを指定する必要がある．
  // 例えば，vec.begin() + 1 とか指定すると答えは変わる．
  size_t minIndex = std::distance(vec.begin(), min_iter);
  size_t maxIndex = std::distance(vec.begin(), max_iter);

  return 0;
}


### accumulate：要素の積算

include

include

int accumulate() { vector v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}; int sum = accumulate(v.begin(), v.end()); return sum; }

##  参考
- [http://vivi.dyndns.org/tech/cpp/vector.html:title]
- [https://cpprefjp.github.io/reference/vector/vector.html:title]
- [https://atcoder.jp/contests/APG4b/tasks/APG4b_t?lang=ja:title]