Visual C++ 2010に追加されたSTLコンテナ「forward_list」

listを簡略化したコンテナ「forward_list」

対してforward_listでは...

　一方、今回VC10に新たに加わったforward_listは単方向リスト（singly-linked-list）であり、各要素を数珠繋ぎにするのは直後の要素を指すポインタ一つだけです。

list-6 : forward_listの要素はこんなものでできている

struct slink {
  slink* forward; // 直後のlink
  slink() : forward(nullptr) {}
  void set_ptr(dlink* n)
    { forward = n; }
  virtual ~slink() {}
};

template<typename T>
struct forward_list_element : slink {
  T data;
  explicit forward_list_element(const T& d) : data(d) {}
};

　直前の要素を指す（後向きの）ポインタがありませんから、listに比べてメモリを食わないのが最大の利点です。各要素だけでなく、コンテナそのもののサイズも小さくなっています。sizeof(list<int>)が12であるのに対し、sizeof(forward_list<int>)は8でした（32bitの場合。64bitではそれぞれ24、16でした）。

　挿入/削除に必要なポインタの繋ぎ替えがlistより単純なだけ高速ではありますが、数十万回繰り返しても数ms程度の差でしかありませんでした。

　さて、ここで再度双方向リストの挿入/削除コード（list-2、3）を眺めてもらいたいのですが、いずれも挿入/削除位置の直前（backward）を参照しています。一方単方向リストの要素は直前要素を指すポインタを持ち合わせていません。したがってlistにある挿入/削除メンバ関数insert/eraseはforward_listでは実現できないことになります。forward_listの挿入/削除メンバ関数は:

• iterator insert_after(iterator position, const T& value);

  positionの直後にvalueを挿入

• void erase_after(iterator position);

  positionの直後要素を削除

となります。listとforward_listの主要メンバ関数をtable-1に示します。

table-1　listとforward_listの主要メンバ関数の比較

	list	forward_list
代入	assign
イテレータ	begin / cbegin	before_begin / cbefore_begin
	end / cend
	rbegin / crbegin
	rend / crend
空集合の判定	empty
サイズ	size
サイズ変更	resize
全消去	clear
先頭操作	front / push_front / pop_front
末尾操作	back / push_back / pop_back
挿入	insert	insert_after
削除	erase	erase_after
条件削除	remove / remove_if
一括移動	splice	splice_after
重複要素の削除	unique
交換	swap
併合	merge
ソート	sort
反転	reverse

　insert_afterによって、要素はイテレータが指定した位置の直後に挿入されます。言い換えれば、挿入位置の直前要素を指すイテレータを与えなければなりません。

　……あれ？ それではforward_listの先頭には挿入できないことになりますね。先頭にはその直前要素が存在しませんから。

　ご安心を。そんなこともあろうかと（仮想的に用意された）先頭要素の直前を指すイテレータを返すbefore_begin()が用意されています。

　そんなわけで、数列0,1,...9をlist<int>, forward_list<int>にセットするコードは次のようになります。forward_listではpush_backが使えないので少しだけ面倒です。

list-7 : 数列のセット

#include <iostream>
#include <list>
#include <forward_list>
#include <algorithm>

using namespace std;

int main() {
  // listの場合
  list<int> li;
  for ( int i = 0; i < 10; ++i ) {
    li.push_back(i);
  }
  for_each(li.begin(), li.end(),
           [](int x) { cout << x << ' '; });
  cout << endl;

  // forward_listの場合（ちょっと面倒)
  forward_list<int> fli;
  auto iter = fli.before_begin();
  for ( int i = 0; i < 10; ++i ) {
    iter = fli.insert_after(iter,i);
  }
  for_each(fli.begin(), fli.end(),
           [](int x) { cout << x << ' '; });
  cout << endl;
}