• Class / Function / Type

      std::
    • Header file

      <>
    • Other / All

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

    履歴 編集

    class template
    <forward_list>

    std::forward_list

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

    概要

    forward_listは、単方向リンクリストのデータ構造をもつクラスである。

    forward_listは、標準ライブラリではシーケンスコンテナの一種として定義されるが、いくつかの点でシーケンスコンテナの要件を満たさない:

    • size()メンバ関数を提供しない。

      • size()メンバ関数は全てのコンテナにO(1)計算量を要求するため、単方向リストの実装ではサイズのためのメンバ変数が必要になる。forward_listでは、サイズメンバ変数を内部に持たないことを示すためにsize()メンバ関数は提供しない。要素数が必要な場合はdistance()を使用して取得する。
    • insert()/emplace()/erase()メンバ関数を提供しない。

      • 双方向リンクリストであるlistinsert()emplace()erase()はinsert-before方式をとっておりO(1)計算量だが、単方向リストの典型的なinsert-beforeの実装ではO(N)計算量になってしまう。
      • forward_listでは、単方向リンクリストでO(1)計算量であるinsert-after方式を使用することを示すinsert_after()emplace_after()erase_after()メンバ関数を提供する。先頭に挿入するためにbefore_begin()メンバ関数を提供する。

    forward_listは、C言語で単方向リンクリストを実装する場合と比べ、空間的にもパフォーマンス的にもゼロオーバーヘッドであるよう設計されている。
    また、forward_listはリンクリストの性質上、挿入・削除のような破壊的操作を行なってもイテレータは無効にならない。

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

    • T: 格納される要素の型、C++17以降は不完全型をサポートしている
    • Allocator: メモリ確保に使用されるアロケータの型。無指定の場合は標準のallocatorクラスが使用される。

    メンバ関数

    構築/コピー/破棄

    名前 説明 対応バージョン
    (constructor) コンストラクタ C++11
    (destructor) デストラクタ C++11
    operator= 代入演算子 C++11
    assign コンテナの再代入 C++11
    assign_range Rangeの要素を再代入 C++23

    イテレータ

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

    領域

    名前 説明 対応バージョン
    empty コンテナが空かどうかを判定する C++11
    max_size 格納可能な最大の要素数を取得する C++11

    要素アクセス

    名前 説明 対応バージョン
    front 先頭要素への参照を取得する C++11

    コンテナの変更

    名前 説明 対応バージョン
    emplace_front 先頭への直接構築による要素追加 C++11
    push_front 先頭に要素を追加する C++11
    prepend_range 先頭にRangeの要素を追加する C++23
    pop_front 先頭から要素を削除 C++11
    emplace_after 任意の位置への直接構築による要素挿入 C++11
    insert_after 任意の位置への要素挿入 C++11
    insert_range_after 任意の位置へRangeの要素挿入 C++23
    erase_after 指定したイテレータの次の要素を削除する C++11
    swap コンテナの交換 C++11
    resize 要素数を変更する C++11
    clear 全要素削除 C++11

    単方向リスト操作

    名前 説明 対応バージョン
    splice_after 他のコンテナから要素を移動する C++11
    remove コンテナから指定された値の要素を削除する C++11
    remove_if コンテナから条件に合った要素を削除する C++11
    unique 重複した要素をコンテナから削除する C++11
    merge 2つのコンテナを併合する C++11
    sort コンテナを並べ替える C++11
    reverse コンテナを反転する C++11

    アロケータ

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

    メンバ型

    名前 説明 対応バージョン
    reference T& C++11
    const_reference const T& C++11
    iterator 前方向イテレータ C++11
    const_iterator 読み取り専用前方向イテレータ C++11
    size_type 符号なし整数型(通常はsize_t) C++11
    difference_type 符号付き整数型(通常はptrdiff_t) C++11
    value_type T C++11
    allocator_type Allocator C++11
    pointer allocator_traits<Allocator>::pointer C++11
    const_pointer allocator_traits<Allocator>::const_pointer C++11

    非メンバ関数

    比較演算子

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

    入れ替え

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

    要素削除

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

    推論補助

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

    基本的な使い方

    #include <iostream>
    #include <forward_list>
    #include <algorithm>
    
    int main()
    {
      std::forward_list<int> ls;
    
      ls.push_front(3);               // 先頭に3を追加
      ls.insert_after(ls.begin(), 1); // 先頭の後ろに1を追加
    
      // イテレータを介して全要素に対して操作を行う
      std::for_each(ls.cbegin(), ls.cend(), [](int x) {
        std::cout << x << std::endl;
      });
    }
    

    出力

    3
    1
    

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

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

    #include <iostream>
    #include <forward_list>
    #include <string>
    
    //簡易なディレクトリ構造表現クラス
    //forward_listの特性上出力が逆順になる
    class directory {
    
      //不完全型(クラス定義内ではそのクラス自身は不完全)を要素型に指定
      std::forward_list<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_front(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
    |-sub3
    |-sub2
    | |-sub2.2
    |   |-sub2.2.1
    | |-sub2.1
    |-sub1
    

    バージョン

    言語

    • C++11

    処理系

    参照