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クラスが使用される。

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

概念・前提知識

• コンテナとは

メンバ関数

構築・破棄

イテレータ

領域

要素アクセス

コンテナの変更

アロケータ

メンバ型

非メンバ関数

比較演算子

入れ替え

要素削除

推論補助

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から非推奨）
};

ハッシュサポート

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

例

基本的な使い方 (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が非推奨となった
• LWG Issue 814. vector<bool>::swap(reference, reference) not defined
  • C++11で、vector<bool>::reference同士を交換する静的メンバ関数swap()の効果が規定された。宣言のみで意味が規定されていなかった