最終更新日時(UTC):
が更新

履歴 編集

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は要素アクセスと(末尾に対する)追加・削除において一般的に最高の性能を誇る。末尾以外に対する挿入・削除はdequelistに劣り、イテレータや要素への参照の安定性(無効になる操作の数)では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 配列の先頭へのポインタを取得する C++11
front 先頭要素への参照を取得する
back 末尾要素への参照を取得する

コンテナの変更

名前 説明 対応バージョン
assign コンテナの再代入
push_back 末尾へ要素追加
emplace_back 末尾へ直接構築 C++11
pop_back 末尾から要素削除
insert 要素の挿入
emplace 要素の直接構築による挿入 C++11
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< 左辺が右辺より小さいかの判定を行う
operator<= 左辺が右辺以下かの判定を行う
operator> 左辺が右辺より大きいかの判定を行う
operator>= 左辺が右辺以上かの判定を行う

入れ替え

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

要素削除

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

推論補助

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

vector<bool>特殊化

vectorbool型に対して特殊化されている。

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

vector<bool>::referenceboolへの参照ではなく、領域内の1bitを指す型であり、以下のようなインタフェースである。

class vector<bool>::reference {
  friend class vector;
  reference();                              // コンストラクタは非公開
public:
  ~reference();
  operator bool() const;                    // boolへの暗黙変換
  reference& operator=(const bool x);       // boolからの代入
  reference& operator=(const reference& x); // vector<bool>のビットからの代入
  void flip();                              // ビットの反転
}

ハッシュサポート

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

基本的な使い方 (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)

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

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

//簡易なディレクトリ構造表現クラス
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の要件を満たさない。

参照