最終更新日時: 2026年07月22日 16時08分23秒 (JST)
rotarymars が更新

履歴 編集

class template
<vector>

# std::vector

    namespace std {
      template <class T, class Allocator = allocator<T>>
      class vector;

      namespace pmr {
        template <class T>
          using vector = std::vector<T, polymorphic_allocator<T>>;  // C++17から
      }
    }

`vector`はシーケンスコンテナの一種で、各要素は線形に、順序を保ったまま格納される。

`vector`コンテナは可変長配列として実装される。通常の(`new []`で確保した)配列と同じように、`vector`の各要素は連続して配置されるため、イテレータだけでなく添字による要素のランダムアクセスも高速である。

配列と違い、ストレージは`vector`自体が管理するため、自動的に領域の拡張が行われる。

`vector`は次の点で優れている。

- 各要素への添字アクセス(定数時間)
- 全要素の両方向の走査(線形時間)
- 末尾への要素の追加・削除(償却定数時間)

これらの挙動は配列と同じパフォーマンス特性を示し、加えてストレージサイズの変更が非常に簡単である。ただし、`vector`は実際の要素数より少し余分にメモリを確保する(これは拡張に備え、パフォーマンス特性を満足するための仕様である)。

他の標準シーケンスコンテナと比べ、`vector`は要素アクセスと(末尾に対する)追加・削除において一般的に最高の性能を誇る。末尾以外に対する挿入・削除は`deque`や`list`に劣り、イテレータや要素への参照の安定性(無効になる操作の数)では`list`に劣る。

内部的には、`vector`は(他のすべてのコンテナと同じように)サイズ用のメンバ変数を持ち、格納されている要素数を管理している。しかし`vector`の場合は、さらに確保済みのメモリサイズを管理するキャパシティ用のメンバ変数を持ち、これは常に`size()`と同じか大きい値となる。確保済みの領域の余計な部分は、要素数の増加に備えて確保しているものである。この動作のおかげで、要素を追加するたびにメモリを再確保する必要が無くなり、単に確保済みの領域を初期化するだけでよくなる(再確保は要素数の対数の頻度で発生する)。

領域の再確保が発生すると、全ての要素が新しい領域にコピーされるため非常にコストがかかる。このため、最終的な要素数が大きくなると解っている場合はあらかじめ`reserve()`メンバ関数でキャパシティを増加させておくことが望ましい。

各テンプレートパラメータの意味は次の通りである。

- `T`: 格納される要素の型、C++17以降は不完全型をサポートしている
- `Allocator`: メモリ確保に使用されるアロケータの型。デフォルトでは標準の`allocator`クラスが使用される。

リファレンス中では、これらの名前をテンプレートパラメータとして扱う。

## メンバ関数

### 構築・破棄

名前 | 説明 | 対応バージョン
--- | --- | ---
`(constructor)` | コンストラクタ |
`(destructor)` | デストラクタ |
`operator=` | 代入演算子 |

### イテレータ

名前 | 説明 | 対応バージョン
--- | --- | ---
`begin` | 先頭の要素を指すイテレータを取得する |
`end` | 末尾の次を指すイテレータを取得する |
`cbegin` | 先頭の要素を指す読み取り専用イテレータを取得する | C++11
`cend` | 末尾の次を指す読み取り専用イテレータを取得する | C++11
`rbegin` | 末尾を指す逆イテレータを取得する |
`rend` | 先頭の前を指す逆イテレータを取得する |
`crbegin` | 末尾を指す読み取り専用逆イテレータを取得する | C++11
`crend` | 先頭の前を指す読み取り専用逆イテレータを取得する | C++11

### 領域

名前 | 説明 | 対応バージョン
--- | --- | ---
`size` | 要素数を取得する |
`max_size` | 格納可能な最大の要素数を取得する |
`resize` | 要素数を変更する |
`capacity` | メモリを再確保せずに格納できる最大の要素数を取得する |
`empty` | コンテナが空かどうかを判定する |
`reserve` | capacityを変更する |
`shrink_to_fit` | capacityをsizeまで縮小する | C++11

### 要素アクセス

名前 | 説明 | 対応バージョン
--- | --- | ---
`operator[]` | 要素アクセス |
`at` | 要素アクセス |
`data` | 配列の先頭へのポインタを取得する |
`front` | 先頭要素への参照を取得する |
`back` | 末尾要素への参照を取得する |

### コンテナの変更

名前 | 説明 | 対応バージョン
--- | --- | ---
`assign` | コンテナの再代入 |
`assign_range` | Rangeの要素を再代入 | C++23
`push_back` | 末尾へ要素追加 |
`emplace_back` | 末尾へ直接構築 | C++11
`append_range` | Rangeの要素を末尾へ追加 | C++23
`pop_back` | 末尾から要素削除 |
`insert` | 要素の挿入 |
`emplace` | 要素の直接構築による挿入 | C++11
`insert_range` | Rangeの要素を挿入 | C++23
`erase` | 要素の削除 |
`swap` | コンテナの交換 |
`clear` | 全要素削除 |

### アロケータ

名前 | 説明 | 対応バージョン
--- | --- | ---
`get_allocator` | アロケータオブジェクトの取得 |

## メンバ型

名前 | 説明 | 対応バージョン
--- | --- | ---
`reference` | `T&` |
`const_reference` | `const T&` |
`iterator` | ランダムアクセスイテレータ |
`const_iterator` | 読み取り専用ランダムアクセスイテレータ |
`size_type` | 符号なし整数型 (通常は`size_t`) |
`difference_type` | 符号付き整数型 (通常は`ptrdiff_t`) |
`value_type` | 要素型 `T` |
`allocator_type` | アロケータの型 `Allocator` |
`pointer` | `Allocator::pointer` |
`const_pointer` | `Allocator::const_pointer` |
`reverse_iterator` | `reverse_iterator<iterator>` |
`const_reverse_iterator` | `reverse_iterator<const_iterator>` |

## 非メンバ関数

### 比較演算子

名前 | 説明 | 対応バージョン
--- | --- | ---
`operator==` | 等値比較 |
`operator!=` | 非等値比較 |
`operator<=>` | 三方比較 | C++20
`operator<` | 左辺が右辺より小さいかの判定を行う |
`operator<=` | 左辺が右辺以下かの判定を行う |
`operator>` | 左辺が右辺より大きいかの判定を行う |
`operator>=` | 左辺が右辺以上かの判定を行う |

### 入れ替え

名前 | 説明 | 対応バージョン
--- | --- | ---
`swap` | 2つの`vector`オブジェクトを入れ替える |

### 要素削除

名前 | 説明 | 対応バージョン
--- | --- | ---
`erase` | 指定した値をもつ要素とその分の領域を、コンテナから削除する | C++20
`erase_if` | 指定した条件に合致する要素とその分の領域を、コンテナから削除する | C++20

## 推論補助

名前 | 説明 | 対応バージョン
--- | --- | ---
`(deduction_guide)` | クラステンプレートの推論補助 | C++17

## `vector<bool>`特殊化

`vector`は`bool`型に対して特殊化されている。

この特殊化はメモリ領域を最小化するために提供されていて、各要素は1bitの領域のみを必要とする。

`vector<bool>::reference`は`bool`への参照ではなく、領域内の1bitを指す型であり、以下のようなインタフェースである (`noexcept`はC++11から、`constexpr`はC++20から付加される)。

C++23には`vector<bool>::iterator`が出力イテレータとなるために、`vector<bool>::reference`が`const`修飾を持つ`bool`からの代入演算子が追加され、`indirectly_writable<vector<bool>::iterator, bool>`がモデルを満たすようになった。

C++26では、ADLで見つかる非メンバ`swap`関数が追加され、`bitset<N>::reference`とインタフェースが統一された。これにあわせて、従来の`static`メンバ関数版の`swap`は非推奨となった。

    class vector<bool>::reference {
      friend class vector;
      constexpr reference();                                       // コンストラクタは非公開
    public:
      constexpr reference(const reference&) = default;             // コピーコンストラクタ（C++17）
      constexpr ~reference();
      constexpr operator bool() const noexcept;                    // boolへの暗黙変換
      constexpr reference& operator=(const bool x) noexcept;       // boolからの代入
      constexpr reference& operator=(const reference& x) noexcept; // vector<bool>のビットからの代入
      constexpr const reference& operator=(bool x) const noexcept; // *thisがconst時のboolからの代入（C++23）
      constexpr void flip() noexcept;                              // ビットの反転

      friend constexpr void swap(reference x, reference y) noexcept; // 2つのビットの交換（C++26）
      friend constexpr void swap(reference x, bool& y) noexcept;     // ビットとboolの交換（C++26）
      friend constexpr void swap(bool& x, reference y) noexcept;     // boolとビットの交換（C++26）

      static constexpr void swap(reference x, reference y) noexcept; // ビットの交換（C++26から非推奨）
    };

### ハッシュサポート

名前 | 説明 | 対応バージョン
--- | --- | ---
`template <class T> struct hash;` | `hash`クラスの先行宣言 | C++11
`template <class Allocator> struct hash<vector<bool, Allocator>>;` | `hash`クラスの`vector<bool>`に対する特殊化 | C++11

### 文字列フォーマットサポート

名前 | 説明 | 対応バージョン
--- | --- | ---
`template <class T, class charT> requires is-vector-bool-reference<T>` `struct formatter<T, charT>;` | `vector<bool>::reference`を`bool`として出力するための`formatter`の特殊化 | C++23

## 例

### 基本的な使い方 (C++11)

    #include <iostream>
    #include <cassert>
    #include <vector>

    int main()
    {
      // int型を要素とする可変長配列の変数を定義し、
      // 初期状態の要素を設定
      std::vector<int> v = {1, 99, 4};

      v[1] = 3;                    // 1番目の要素を参照し、書き換える
      v.push_back(5);              // 末尾に値5を追加
      v.insert(v.begin() + 1, 2);  // 1番目に値2を挿入

      int* p = v.data();           // 内部表現のポインタを取得
      std::size_t size = v.size(); // 要素数を取得
      assert(p[0] == 1);
      assert(size == 5u);

      // 各要素に対して操作を行う
      for (int x : v) {
        std::cout << x << std::endl;
      }
    }

#### 出力

    1
    2
    3
    4
    5

### 不完全型を要素にする例 (C++17)

不完全型を要素型に出来るようになった事で、階層構造や多分木などの再帰的データ構造を実装することが容易になる。
他にも、`list`と`forward_list`が不完全型をサポートしている。

    #include <iostream>
    #include <vector>
    #include <string>
    #include <utility>

    //簡易なディレクトリ構造表現クラス
    class directory {

      //不完全型（クラス定義内ではそのクラス自身は不完全）を要素型に指定
      std::vector<directory> m_subdir{};
      std::string m_name{};

    public:

      directory(const char* name) : m_name{name}
      {}

      //サブディレクトリ追加
      template<typename Dir>
      void add(Dir&& dir) {
        m_subdir.emplace_back(std::forward<Dir>(dir));
      }

      //ディレクトリ名取得
      auto get() const -> const std::string& {
        return m_name;
      }

      auto begin() const {
        return m_subdir.begin();
      }

      auto end() const {
        return m_subdir.end();
      }
    };

    //ルートより下のディレクトリについて整形して出力
    void recursive_out(const directory& dir, unsigned int depth) {

      if (1 < depth) std::cout << "| ";
      for (auto i = depth; 2 < i; --i) {
        std::cout << " ";
      }
      if (2 < depth) std::cout << " ";

      std::cout << "|-" << dir.get() << std::endl;

      for (auto& subdir : dir) {
        recursive_out(subdir, depth + 1);
      }
    }

    //ディレクトリ構造を出力する
    void out_directorytree(const directory& dir) {
      std::cout << dir.get() << std::endl;

      for (auto& subdir : dir) {
        recursive_out(subdir, 1);
      }
    }

    int main() {
      directory dir{"root"};
      dir.add("sub1");

      directory sub2{"sub2"};
      sub2.add("sub2.1");

      directory sub22{"sub2.2"};
      sub22.add("sub2.2.1");

      sub2.add(std::move(sub22));

      dir.add(std::move(sub2));
      dir.add("sub3");

      out_directorytree(dir);
    }

#### 出力

    root
    |-sub1
    |-sub2
    | |-sub2.1
    | |-sub2.2
    |   |-sub2.2.1
    |-sub3

### `vector<bool>`の基本操作

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

    int main()
    {
      std::vector<bool> v(8, false);
      v[5] = true; // ビットを立てる
      v[7].flip(); // ビット反転(1だったら0、0だったら1にする)

    //bool& x = v[3]; // エラー！プロキシオブジェクトのため、bool&には変換できない
      bool x = v[3]; // OK : コピーはできる
      std::cout << "v[3] : " << x << std::endl;

      // イテレータ操作は可能
      std::for_each(v.begin(), v.end(), [](bool x) {
        std::cout << x << std::endl;
      });
    }

### 出力

    v[3] : 0
    0
    0
    0
    0
    0
    1
    0
    1

`vector<bool>`の要素は参照するとプロキシオブジェクトのコピーが返ってくるため、RandomAccessIteratorの要件を満たさない。 ただし、C++20以降のランダムアクセスイテレータの定義である`random_access_iterator`のモデルは満たす。

### 定数式内でvectorを使用する (C++20)

    #include <cassert>
    #include <vector>

    constexpr bool f()
    {
      std::vector<int> v = {1, 2, 3};
      v.push_back(4);

      auto* p = v.data();
      assert(p);

      int sum = 0;
      for (auto x : v) {
        sum += x;
      }
      return sum != 0;
    }

    int main()
    {
      static_assert(f());
    }

#### 出力

## 参照

- `vector`のメモリ効率について
  - ２倍だけじゃない - Derive Your Dreams
  - それでも２倍だ - Derive Your Dreams
- LWG Issue 69. Must elements of a `vector` be contiguous?
  - C++03から、`vector`の要素のメモリが連続していることが保証された。
- N1211 - `vector<bool>`: More Problems, Better Solutions
- ビット配列に関しては、`bitset`(ビットを格納する固定長コンテナ)も参照。
- 可変長のビット配列の実装としては、Boost C++ Librariesの`dynamic_bitset`がある。
- N2669 Thread-Safety in the Standard Library (Rev 2)
- N4510 Minimal incomplete type support for standard containers, revision 4
- P2286R8 Formatting Ranges
  - C++23から、Range・コンテナ、`pair`、`tuple`のフォーマット出力、および文字・文字列のデバッグ指定 (`"?"`) が追加された
- P3612R1 Harmonize proxy-reference operations (LWG 3638 and 4187)
  - C++26で、`vector<bool>::reference`にADLで見つかる非メンバ`swap`関数が追加され、従来の`static`メンバ関数版`swap`が非推奨となった