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
はリンクリストの性質上、挿入・削除のような破壊的操作を行なってもイテレータは無効にならない。
各テンプレートパラメータの意味は次の通りである。
メンバ関数
構築/コピー/破棄
名前 | 説明 | 対応バージョン |
---|---|---|
(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;
});
}
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);
}
80
void recursive_out(const directory& dir, unsigned int depth) {
#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}
{}
//サブディレクトリ追加
出力
root
|-sub3
|-sub2
| |-sub2.2
| |-sub2.2.1
| |-sub2.1
|-sub1
バージョン
言語
- C++11
処理系
- Clang: ??
- GCC: 4.7.0 ✅
- ICC: ??
- Visual C++: ??