Immutable な片方向リスト

C++

書いてみました。GCC 4.5.2 以降 (-std=c++0x) 専用です。
https://gist.github.com/891955
標準の sequence container に似せてありますが、次の点で大きく異なります。

  • 要素は変更できない
  • insert, erase, clear などの操作を行うと、リスト自身は変更されずに操作後のリストが返される

例を示します。(oven::identities はリストの中身を表示するために使用しています)

#include <iostream>
#include <iterator>
#include <pstade/oven/identities.hpp>
#include <pstade/oven/io.hpp>
#include "./slist.hpp"

namespace oven = pstade::oven;

int main()
{
    vitro::slist<int> const ns{0, 2, 3};

    std::cout << (ns | oven::identities) << '\n';

    std::cout <<
        (ns.insert(std::next(ns.begin()), 1) | oven::identities) << '\n';

    std::cout << (ns | oven::identities) << '\n';
}

実行結果

{0,2,3}
{0,1,2,3}
{0,2,3}

リストが変更されていないことがわかると思います。
リストを操作する、すなわち新しいリストを生成するとき、古い版と新しい版とで構造はできる限り共有されます。したがって、リストの先頭への操作は非常に安価に行えます。
この性質を利用して、関数型言語のような処理を書くことができます。以下は filter を実装する例です。

#include <iostream>
#include <boost/lambda/lambda.hpp>
#include <pstade/oven/identities.hpp>
#include <pstade/oven/io.hpp>
#include "./slist.hpp"

using namespace boost::lambda;
namespace oven = pstade::oven;

template <class Predicate, class T, class Allocator>
vitro::slist<T, Allocator>
filter(Predicate p, vitro::slist<T, Allocator> const &xs)
{
    return
    xs.empty() ?
        xs :
        !p(xs.front()) ?
            filter(p, xs.pop_front()) :
            filter(p, xs.pop_front()).push_front(xs.front());
}

int main()
{
    vitro::slist<int> const xs{0, 1, 2, 3, 4, 5, 6, 7};

    std::cout << (filter((_1 % 2) == 0, xs) | oven::identities);

    // {0,2,4,6}
}

私自身は使い方がよくわかっていませんが、こういうコンテナがあると面白いと思います。