std::vectorはC++標準ライブラリで提供される動的配列で、メモリ上に要素を連続的に配置します。固定長配列と異なり、実行時にサイズを柔軟に変更できるのが特徴です。

1. vectorのメモリ管理

vectorは2つの重要な状態情報を管理します：容量（capacity）と現在の要素数（size）。

• 容量：確保済みのメモリ領域の大きさ
• サイズ：実際に格納されている要素数

要素追加時に容量が不足すると、vectorは以下の処理を実行します：

1. 新しいメモリ領域を確保
2. 既存要素を新しい領域にコピー
3. 古いメモリ領域を解放

この再配置処理はパフォーマンスに影響するため、vectorは「指数関数的成長戦略」を採用しています。具体的には、必要に応じて容量を2倍に拡張することで、頻繁な再配置を回避します。

2. vectorの内部実装

vectorオブジェクト自体はスタック上に配置されますが、要素データはヒープ上に動的に確保されます。この設計により、実行時のサイズ変更が可能になります。

主要なメンバ変数：

template<typename T>
class vector {
private:
    T* start_;      // 配列の先頭
    T* finish_;     // 有効要素の末尾+1
    T* end_of_storage_; // 確保領域の末尾+1
};

3. vectorの基本操作

3.1 初期化方法

// 空のvector作成
std::vector<int> v1;

// 初期値指定
std::vector<int> v2 = {1, 2, 3};

// サイズと初期値指定
std::vector<int> v3(5, 100); // 100が5つ

3.2 要素アクセス

std::vector<int> nums = {10, 20, 30};

// インデックスアクセス
int first = nums[0];

// at()メソッド（範囲チェックあり）
int second = nums.at(1);

// 先頭/末尾要素
int front = nums.front();
int back = nums.back();

3.3 要素の追加/削除

std::vector<int> vec;

// 末尾追加
vec.push_back(1);
vec.emplace_back(2); // 効率的な構築

// 途中挿入
vec.insert(vec.begin() + 1, 99);

// 要素削除
vec.pop_back(); // 末尾削除
vec.erase(vec.begin()); // 先頭削除

3.4 イテレータの使用

std::vector<int> data = {1, 3, 5, 7};

// 通常イテレータ
for(auto it = data.begin(); it != data.end(); ++it) {
    *it *= 2;
}

// 逆順イテレータ
for(auto rit = data.rbegin(); rit != data.rend(); ++rit) {
    std::cout << *rit << " ";
}

4. 注意点

イテレータの無効化：以下の操作後は既存のイテレータが無効になります

• 要素追加による容量変更
• 要素削除

安全な削除処理の例：

std::vector<int> vals = {1, 2, 3, 4, 5};
auto it = vals.begin();

while(it != vals.end()) {
    if(*it % 2 == 0) {
        it = vals.erase(it); // eraseは次の有効位置を返す
    } else {
        ++it;
    }
}

パフォーマンス特性：

• ランダムアクセス：O(1)
• 末尾追加/削除：平均O(1)
• 途中挿入/削除：O(n)