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

履歴 編集

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

    • 双方向リンクリストである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

イテレータ

名前 説明 対応バージョン
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
pop_front 先頭から要素を削除 C++11
emplace_after 任意の位置への直接構築による要素挿入 C++11
insert_after 任意の位置への要素挿入 C++11
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

処理系

参照