std::vectorを使いこなそう！

std::vector は C++ でプログラムを書く上でとても便利ですよね。
この記事では、std::vector でできる、実行速度やメモリの改善、実装が楽になるような技をお伝えします。

１．途中の要素削除

std::vector は erase() などを使用して途中にあるデータを削除する場合、計算量は最悪 O(N) かかってしまい、非効率です。しかし、この方法を使えば O(1) で要素を削除できます。
やり方は簡単。削除したい要素と最後尾の要素を入れ変えて pop_back() を実行するだけ。
しかし、std::vector内のデータの順番が変わってしまうので、データの並びが重要な場合は注意してください！
ここでは偶数のデータを削除するプログラムを例とします。

sample.cpp

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

int main(){
  std::vector<int> arr = {1, 2, 3, 4, 5};
  for(int i = 0; i < arr.size(); ++i){
    if(i % 2 == 0){
      std::swap(arr[i], arr.back());
      arr.pop_back();
      --i;
    }
  }

  for(const int& value : arr){
    std::cout << value << " ";
  }
  std::cout << "\n";
}

２．特定条件の要素の一括削除

順序を確保したまま特定条件の要素を一括削除したいときは、std::remove を使いましょう。計算量は O(N) です。自力で実装するよりも std::remove 使ったほうが簡単なので、ぜひ使ってみてください！

sample.cpp

#include <algorithm>

// 偶数を削除
arr.erase(std::remove_if(arr.begin(), arr.end(), [](int x){ return x % 2 == 0; }), arr.end());

３．メモリの無駄を省く

std::vector では、確保されているメモリ領域が足りなくなると、「新しいメモリ領域の確保」「全要素のコピー」「古いメモリの解放」 という非常に重い処理が走ります。あらかじめ要素数が予測できるなら、reserve() を使ってメモリを確保しておくことで、このオーバーヘッドを完全に回避できます。

sample.cpp

std::vector<int> arr;
arr.reserve(1000); // あらかじめ1000個分のメモリを確保しておく
for(int i = 0; i < 1000; ++i) {
    arr.push_back(i); // 再確保が発生しない！
}

たくさんの要素を削除した後、std::vector の容量は沖いまま残ります。メモリをシステムに返却したい場合は shrink_to_fit() を使いましょう。

sample.cpp

arr.clear(); // 中身を消す
arr.shrink_to_fit();

まとめ

今回は std::vector をより効率的に扱うための３つの方法を紹介しました。なんでも erase() やとりあえず push_back() とするのではなくて、「データの順序は大切か？」「追加する要素数は決まっているか？」を考えるだけで、プログラムの実行速度やメモリ効率を向上させることができます。

標準ライブラリの性質を理解して、よき C++ 生活を過ごしましょう！