|新しいページ|検索|ページ一覧|RSS|@ウィキご利用ガイド | 管理者にお問合せ
|ログイン|

続 無限リスト

    
※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

続 無限リスト

last update: 2012/12/08 (Sat )

前回,C++0x を用いて基本的な無限リストを作成した.とはいえ,目につく問題も残っていた.例えばリストを扱うために常に shared_ptr を経由しなければならなかったり,リストの 2 番目を参照するために ls->cdr()->car といった不自然なメソッド呼び出しをする必要があったりした.これを改善しよう.

まず,常に shared_ptr となるのを防ぐには,cons セル全体をラッパクラスで覆えばよい.例えば以下のようになる.
template<typename T>
class list
{
    struct cell
    {
        T _car;
        std::function<std::shared_ptr<cell>()> _cdr;

        cell(T const & car, std::function<std::shared_ptr<cell>()> const & cdr)
            : _car(car), _cdr(cdr)
        {}
    };

    std::shared_ptr<cell> _cell;
};
std::list と名前が衝突する? そんなことは using namespace std する奴が悪いのだ(おい)それよりも問題は,この list をどうやって構築するかである.前回は cell 構造体そのものを lambda 式を用いて直接構築した.しかし今回は cell 構造体は private なので外部からは隠蔽されている.なので nat_from で「std::shared_ptr<cell> を返す lambda 式」を直接生成できない.

そこで,ユーザ側では 「list を返す lambda 式」を定義してもらって,それを「std::shared_ptr<cell> を返す lambda 式」に変換してやる必要がある.この変換をコンストラクタとして実装してやればよい.

ついでに,C++0x らしく cell 構造体はコピー・代入禁止とし,さらに car と cdr へのアクセサを実装しておく.
template <typename T>
class list
{
    struct cell
    {
        T car;
        std::function<std::shared_ptr<cell>()> cdr;

        cell(T const & car, std::function<std::shared_ptr<cell>()> const & cdr)
            : car(car), cdr(cdr)
        {
        }

        cell(cell const &) = delete;

        cell
        operator = (cell const &) = delete;
    };

    std::shared_ptr<cell> _cell;

    public:
    list()
    {
    }

    private:
    list(std::shared_ptr<cell> const & cell)
       : _cell(cell)
    {
    }

    public:
    list(T const & car, std::function<list<T>()> const & cdr)
        : _cell(new cell(car, [cdr]() { return cdr()._cell; }))
    {
    }

    T
    car() const { return _cell->car; }

    list
    cdr() const { return list(_cell->cdr()); }
};
これを用いて nat_from を実装すると
list<int>
nat_from(int k)
{
    return list<int>(k, [k]() { return nat_from(k + 1); });
}
おおー,ずっと自然になった.

有限リスト

これで自由自在に無限リストを使えるようになったであろうか.いや,まだ気が早い.例えば nat_from(1) で 1 から始まる増加列を生成できたとして,これの先頭に 0 を加えたい場合どうすればよいだろう.すでにある list を返す promise を改めて生成し,list 構築なんてめんどくさい.というか,有限だろうが無限だろうが,生成する方法は異なっても使うときは同じように使いたいのだ.これを実現しよう.

まず,有限リスト用の cons セルを定義する.これを無限リスト用の cons セルと混ぜて使いたいから,同じ基底クラスを持つ派生クラスとして定義すればよいだろう.ここで car 部は共通だから基底クラスが持てばよい.cdr 部は有限リストなら shared_ptr<cell> を,無限リストなら function<shared_ptr<cell>()> を保持し,アクセスされたら shared_ptr<cell> を返すようなアクセサを用意する.

template <typename T>
class list
{
    class cell_base
    {
        T _car;

        public:
        cell_base(T const & car)
            : _car(car)
        {
        }

        cell_base(cell_base const &) = delete;

        virtual ~cell_base()
        {
        }

        cell_base
        operator = (cell_base const &) = delete;

        T const &
        car() const { return _car; }

        virtual std::shared_ptr<cell_base>
        cdr() const = 0;
    };

    struct cell_impl_eager
        : public cell_base
    {
        std::shared_ptr<cell_base> _cdr;

        cell_impl_eager(T const & car, std::shared_ptr<cell_base> const & cdr)
            : cell_base(car), _cdr(cdr)
        {
        }

        std::shared_ptr<cell_base>
        cdr() const { return _cdr; }
    };

    struct cell_impl_delayed
        : public cell_base
    {
        std::function<std::shared_ptr<cell_base>()> _cdr;

        cell_impl_delayed(T const & car, std::function<std::shared_ptr<cell_base>()> const & cdr)
            : cell_base(car), _cdr(cdr)
        {
        }

        std::shared_ptr<cell_base>
        cdr() const { return _cdr(); }
    };
    
    std::shared_ptr<cell_base> _cell;

    public:
    list()
    {
    }

    private:
    list(std::shared_ptr<cell_base> const & cell)
        : _cell(cell)
    {
    }

    public:
    list(T const & car, list<T> const & cdr)
        : _cell(new cell_impl_eager(car, cdr._cell))
    {
    }

    list(T const & car, std::function<list<T>()> const & cdr)
        : _cell(new cell_impl_delayed(car, [cdr]() { return cdr()._cell; }))
    {
    }

    T const &
    car() const { return _cell->car(); }

    list
    cdr() const { return list(_cell->cdr()); }
};
試してみる.
list<int> ls = nat_from(1);
ls = list<int>(0, ls);
std::cout << ls.car() << std::endl; // 0
std::cout << ls.cdr().car() << std::endl; // 1
std::cout << ls.cdr().cdr().car() << std::endl; // 2
できちまったぜ.

&trackback

参考



コメント

name
comment


関連ページ



関連ブログ

  • 「C++0x」を含むブログが見つかりません。

プロフィール


tossy_squirrel



メニュー




更新履歴


取得中です。