最終更新日時(UTC): 2025年08月26日 09時12分52秒
Raclamusi が更新

履歴 編集

class template
<forward_list>

# std::forward_list(C++11)

    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()`メンバ関数を提供しない。

  - 双方向リンクリストである`list`の`insert()`／`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)

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

    #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

### 処理系

- Clang: ??
- GCC: 4.7.0 ✅
- ICC: ??
- Visual C++: ??

## 参照

- N2543 STL singly linked lists (revision 3) [概要の日本語訳]
- N4510 Minimal incomplete type support for standard containers, revision 4