最終更新日時:
が更新

履歴 編集

class template
<forward_list>

std::forward_list(C++11)

namespace std {
  template <class T, class Allocator = allocator<T>>
  class forward_list;
}

概要

<forward_list>ヘッダでは、単方向リンクリストの実装である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: 格納される要素の型
  • 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++11
operator<= 左辺が右辺以下かの判定を行う C++11
operator> 左辺が右辺より大きいかの判定を行う C++11
operator>= 左辺が右辺以上かの判定を行う C++11
swap 2つのforward_listオブジェクトを入れ替える C++11

#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++11

処理系

参照