はじめに
前回はVisual C++ 2010（以下、VC10）に追加されたアルゴリズムを一挙に紹介しましたが、今回はコンテナを一つ。
標準C++ライブラリに新たなコンテナ「forward_list」がお目見えしました。名前から察しがつくとおり、従来からあるlistの仲間です。forward_listの内部構造はlistをほんの少し簡略化したものなのですが、その「ほんの少しの簡略化」によって、クラスが提供するメンバ関数が大きく変わっています。本稿ではforward_listの特性/特徴をlistとの対比とともに解説します。
listの構造とからくり
forward_listの解説の前にlistについて少しばかりおさらいしておきましょう。標準C++ライブラリが提供するlistは双方向リスト（doubly-linked-list）、すなわち各要素が直後の要素を指すポインタと直前の要素を指すポインタとで数珠繋ぎにすることで要素の集合（順序列）を表現しています。
list-1 : listの要素はこんなものでできている
struct dlink {
dlink* forward; // 直後のlink
dlink* backward; // 直前のlink
dlink() : forward(nullptr), backward(nullptr) {}
void set_ptr(dlink* p, dlink* n)
{ backward = p; forward = n; }
virtual ~dlink() {}
};
template<typename T>
struct list_element : dlink {
T data;
explicit list_element(const T& d) : data(d) {}
};
このとき、数珠繋ぎになった一連のlist_element<T>があり、その中の一つ、positionの直前に新たな要素targetを挿入するコードはこんな感じになりますね。
list-2 : positionの直前にtargetを挿入する
// X→position ⇒ X→target→position
// X←position ⇒ X←target←position
#include <cassert>
dlink* insert(dlink* position, dlink* target) {
assert( position );
if ( position->backward != nullptr )
position->backward->forward = target; // X→target
target->forward = position; // target→position
target->backward = position->backward; // target←X
position->backward = target; // position←target
return target;
}
同様に一連のlist_element<T>からpositionを削除するには...
list-3 : positionを削除する
// X→position→Y ⇒ X→Y
// X←position←Y ⇒ X←Y
void erase(dlink* position) {
assert( position );
// X→position→Y ⇒ X→Y
if ( position->backward != nullptr )
position->backward->forward = position->forward;
// X←position←Y ⇒ X←Y
if ( position->forward != nullptr )
position->forward->backward = position->backward;
delete position;
}
使ってみましょう。３つのlist_element<string>を数珠繋ぎにしておき、その途中に新たな要素を挿入し、削除します。
list-4 : list-1,2,3に続いて...
#include <iostream>
using namespace std;
template<typename T>
void print_all(const list_element<T>* p) {
while ( p ) {
cout << p->data << ' ';
p = static_cast<list_element<T>*>(p->forward);
}
cout << endl;
}
int main() {
typedef list_element<string> cat;
cat* zero = new cat("シュウたん");
cat* one = new cat("みずき");
cat* two = new cat("ろり");
// 各要素を繋いでおく: zero⇔one⇔two
zero->set_ptr(nullptr,one); // (null)→zero→one
one->set_ptr(zero,two); // zero→one→two
two->set_ptr(one,nullptr); // one→two→(null)
print_all(zero);
// "みずき"の直前に"マグさん"を挿入
auto hoge = insert(one, new cat("マグさん"));
print_all(zero);
// "マグさん"を削除
erase(hoge);
print_all(zero);
}
実行結果
シュウたん みずき ろり シュウたん マグさん みずき ろり シュウたん みずき ろり
listのメンバ関数についてもまったく同じ挙動を示し、insertは指定位置の直前に挿入、eraseは指定位置の要素を削除します。
list-5 : listの挙動
#include <iostream>
#include <algorithm>
#include <list>
#include <string>
using namespace std;
int main() {
list<string> cats;
cats.push_back("シュウたん");
cats.push_back("みずき");
cats.push_back("ろり");
// "みずき"の位置に
auto iter = find(cats.begin(), cats.end(), "みずき");
// "マグさん"を挿入し、
iter = cats.insert(iter, "マグさん");
for_each(cats.begin(), cats.end(),
[](const string& cat) { cout << cat << ' ';});
cout << endl;
// そして削除する
cats.erase(iter);
for_each(cats.begin(), cats.end(),
[](const string& cat) { cout << cat << ' ';});
cout << endl;
}
実行結果
シュウたん マグさん みずき ろり シュウたん みずき ろり
