導入
C++の std::vector は、動的に要素を追加できる非常に便利なコンテナですが、その背後では「メモリの再確保」というコストの高い処理が隠れています。特に大規模なデータを扱う際、デフォルトの挙動のまま要素を追加し続けると、何度もメモリの再割り当てと既存要素のコピーが発生し、パフォーマンスが著しく低下します。本記事では、この課題を解決するための std::vector::reserve() の正しい知識と活用法を解説します。
基礎知識
std::vector は連続したメモリ領域を保持します。要素の追加時に現在のキャパシティ（容量）を超えると、vector は自動的に新しい広いメモリ領域を確保し、そこへ全要素をコピー（または移動）し、古いメモリを解放します。この一連の動作を「再確保（Reallocation）」と呼びます。再確保は O(N) の計算量を要するため、ループ内で頻繁に発生するとプログラム全体のボトルネックとなります。
実装/解決策
解決策はシンプルです。要素数が事前に予測できる場合、あるいは最大値がわかっている場合は、std::vector::reserve() を使用して、あらかじめ必要なメモリを確保しておきます。これにより、vector は追加のたびにメモリを再確保する必要がなくなり、単なるメモリへの書き込み操作のみで済むため、処理速度が大幅に向上します。
サンプルプログラム
以下のコードは、reserve を使わない場合と使った場合の比較をイメージした実装例です。
include
include
include
int main() {
const int count = 1000000;
// パターン1: reserveなし 現場で活用する際の注意点は以下の通りです。 1. reserve() はサイズを変えない: reserve() はキャパシティ（容量）を増やしますが、size（実際に存在する要素数）は変更しません。reserve(100) をした直後に vec[0] にアクセスすると、要素がまだ作成されていないため未定義動作になる可能性があります。あくまで push_back 等で要素を追加する前提で使用してください。 適切に reserve() を活用することで、C++ プログラムの実行効率は劇的に改善します。ぜひ日々の実装に取り入れてみてください。
// 追加のたびに内部で頻繁に再確保とコピーが発生し、低速になる
std::vector
auto start1 = std::chrono::high_resolution_clock::now();
for (int i = 0; i < count; ++i) {
vec_slow.push_back(i);
}
auto end1 = std::chrono::high_resolution_clock::now();
// パターン2: reserveあり
// 最初に必要な分だけメモリを確保するため、再確保が発生しない
std::vector
vec_fast.reserve(count); // 事前に100万要素分のメモリを確保
auto start2 = std::chrono::high_resolution_clock::now();
for (int i = 0; i < count; ++i) {
vec_fast.push_back(i);
}
auto end2 = std::chrono::high_resolution_clock::now();
std::cout << "Reserveなしの時間: "
<< std::chrono::duration_cast応用・注意点
2. 過度な確保を避ける: 必要なサイズが明確でない場合、あまりに巨大な値を reserve() すると、メモリを無駄に消費し、OSからのメモリ確保自体に失敗するリスクがあります。
3. resize() との混同に注意: resize() は要素を構築してサイズを変更しますが、reserve() はメモリ確保のみを行います。目的によって使い分けましょう。
コメント