• Class / Function / Type

      std::
    • Header file

      <>
    • Other / All

    最終更新日時(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 配列の先頭へのポインタを取得する
    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>特殊化

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

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

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

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

    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;                              // ビットの反転
    }
    

    ハッシュサポート

    名前 説明 対応バージョン
    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>::referenceboolとして出力するための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)

    不完全型を要素型に出来るようになった事で、階層構造や多分木などの再帰的データ構造を実装することが容易になる。
    他にも、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の要件を満たさない。 ただし、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());
    }
    

    出力

    参照