標準ライブラリの双方向リストである std::list は、使い勝手はいいが使用メモリや処理速度の点でオーバーヘッドが大きい。
実際には双方向リストとしてのメリットが必要になるケースは少なく単方向リストで十分な場合が多い。
(多くの標準ライブラリの実装でも slist を用意している)
そこで、C++0x では単方向リストである std::forward_list を追加する
【設計方針】
・特に変更する理由がない限り forward_list は list の設計に合わせる
・設計上の選択肢が複数ある場合、パフォーマンス(速度/サイズ)を最優先する
(Cの構造体で実装する場合と比べて、ゼロ・オーバーヘッドにする)
【Insert-before vs Insert-after】
・単方向リストの典型的な実装では、std::list と同じ仕様(ノードの前に挿入/削除)の insert と erase の計算量は O(N) になってしまう (std::list では O(1) )
・std::list と同様の計算量のためには、「ノードの後ろに挿入/削除(insert-after)」になってしまう
・O(1) の計算量で、insert-before を実装することも可能(反復子が対象のノードを直接ポイントするのではなく、ひとつ前をポイントするようにする)だが、実装が複雑になり、サイズやパフォーマンスの点で不利
以上の議論を踏まえ
・ゼロ・オーバーヘッドを目指すという設計方針により、本提案では「insert-after」方式を採用する
・関数名は、バグの原因となることを回避するため insert/erase の代わりに insert_after/erase_after とする
・std::list に比べてパフォーマンスが低いため、従来通りの insert/erase は用意しない
【サイズ】
コンテナに含まれるノードを数える処理のために、既存の STL コンテナは size メンバ関数を実装している。
forward_list クラスでは、以下の3つの選択肢を検討し、3番目の「size 関数を用意しない」を採用する。
1. その都度、全てのノードをたどって数える。計算量は O(N)。
size 関数を用意すると、ユーザーは気軽にそれを使うようになるため、O(N) の計算量はインパクトがある。
std::distance(begin(), end()) で同じことができるので、メンバ関数として用意するメリットは小さい。
2.ノード数を保持するメンバ変数を用意する。計算量は O(1)。
C 言語での実装と比較して、ゼロ・オーバーヘッドを目指すため、メンバ変数のための領域が無駄になる。
メンバ変数として用意しなくても、必要に応じて外付けすることは可能。
3.size 関数は用意しない。
size 関数を用意しない場合、STL コンテナの要件を満たさないことになるが
unordered 連想コンテナのように、すでに要件を満たしていないコンテナが存在する
【ノード・ベースのアルゴリズム】
std::list と同様に、STL アルゴリズムに対応するメンバ関数(remove, unique, sort etc...)を実装する。
反復子を使用するノード・ベースのアルゴリズムを実装する方がよりジェネリックプログラミングらしいが
既存のクラスを変更することになること、ノード・ベースのアルゴリズムそのものがまだ実験段階であること
の2つの理由から、本提案には含めない。
N2543 STL singly linked lists (revision 3)
