O(n) 〜 O(1) のオーダーで Boost.Fusion のシーケンスの N 番目の要素の型を得る

通常、あるシーケンスの N 番目の要素の型を得るには、以下のようにする。

boost::fusion::result_of::value_at<Seq, N>::type

fusion::result_of::value_at および fusion::result_of::value_at_c は、Forward Sequence を要求する。
すなわち fusion::list や、Random Access Sequence を満たす fusion::vector に対してはこれを使うことができる。

では、同じく Forward Sequence である fusion::joint_view にこれを使えるだろうか。

typedef boost::fusion::vector<int, int> vec1_t;
typedef boost::fusion::vector<double, double> vec2_t;
typedef boost::fusion::joint_view<vec1_t, vec2_t> view_t;

typedef boost::fusion::result_of::value_at_c<view_t, 2>::type value_t; // Compilation error!!

残念ながら、このコードをコンパイルすることはできない。（VC9 + Boost 1.46.1）
なぜなら、現在（Boost 1.46.1）の実装において fusion::result_of::value_at は、
内部で fusion::extension::value_at_impl を呼ぶ。

fusion::extension::value_at_impl は、デフォルトで fusion::sequence_facade_tag に対して特殊化されている。
sequence_facade_tag とは、fusion::vector や fusion::list など標準のシーケンスの持つタグである。

ところで、fusion::joint_view の持つタグは fusion::joint_view_tag である。
fusion::extension::value_at_impl は、これのタグ対して特殊化されていない。
そのため、参照すべきメタ関数クラスが見つからずコンパイルエラーになるのだ。

さて、ここでは fusion::result_of::value_at 以外の方法でシーケンスの N 番目の要素の型を得る方法を考える。

といっても、原理は至極簡単である。
std::list などインデックスアクセスのできないコンテナの N 番目の要素を得るには、およそ以下のようにすればよい。

iterator it  = cont.begin();
std::advance(it, n);
*it;

型の世界においても、同じように考えればよい。

- sprig/fusion/linear_value_at.hpp

#ifndef SPRIG_FUSION_LINEAR_VALUE_AT_HPP
#define SPRIG_FUSION_LINEAR_VALUE_AT_HPP

#include <boost/fusion/include/begin.hpp>
#include <boost/fusion/include/advance.hpp>
#include <boost/fusion/include/value_of.hpp>

namespace sprig {
    namespace fusion {
        namespace result_of {
            //
            // linear_value_at_c
            // linear_value_at
            //
            template<typename Seq, int M>
            struct linear_value_at_c
                : public boost::fusion::result_of::value_of<
                    typename boost::fusion::result_of::advance_c<
                        typename boost::fusion::result_of::begin<Seq>::type,
                        M
                    >::type
                >
            {};
            template<typename Seq, typename N>
            struct linear_value_at
                : public linear_value_at_c<Seq, N::value>
            {};
        }   // namespace result_of
    }   // namespace fusion
}   // namespace sprig

#endif  // #ifndef SPRIG_FUSION_LINEAR_VALUE_AT_HPP

fusion::result_of::begin は、シーケンスの開始要素を指すイテレータを返す。
fusion::result_of::advance は、N 個進めたイテレータを返す。
fusion::result_of::value_of は、イテレータの指す要素の型を返す。

なお、fusion::result_of::value_of とよく似たメタ関数に、fusion::result_of::deref というものがあるが、
これは「イテレータの指す要素の参照を返す」ものであるから、意味合いが異なる。

linear_value_at および linear_value_at_c は、fusion::result_of::value_at のように、シーケンスの N 番目の要素の型を得る。
また、同様に Forward Sequence を要求するが、value_at_impl の特殊化を要求しない。

名前の "linear" は「線形」の意だが、これは操作に高々 O(n) 線形時間を要するためである。

もしイテレータが Random Access Iterator ならば result_of::advance は償却定数時間（ならし定数時間）を要し、
その場合、linear_value_at も償却定数時間を要する。

もしイテレータが Bidirectional または Forward Iterator ならば result_of::advance は線形時間を要するため、
その場合、linear_value_at には線形時間が必要となる。

さて、fusion::result_of::value_at の代わりに linear_value_at を使うことで以下のように、
ビューに対しても N 番目の要素の型を得ることができる。

typedef boost::fusion::vector<int, int> vec1_t;
typedef boost::fusion::vector<double, double> vec2_t;
typedef boost::fusion::joint_view<vec1_t, vec2_t> view_t;

typedef sprig::fusion::result_of::linear_value_at<view_t, 2>::type value_t;

更に、これを使って fusion::extension::value_at_impl の特殊化を定義することで、
「fusion::result_of::value_at を使って」 N 番目の要素の型を得られるようにもできる。

namespace boost {
    namespace fusion {
        namespace extension {
            template<>
            struct value_at_impl<boost::fusion::joint_view_tag> {
                template <typename Seq, typename N>
                struct apply
                    : public sprig::fusion::result_of::linear_value_at<Seq, N>
                {};
            };
        }
    }
}

以上を定義することで、最初のコードをコンパイルできるようになる。

typedef boost::fusion::vector<int, int> vec1_t;
typedef boost::fusion::vector<double, double> vec2_t;
typedef boost::fusion::joint_view<vec1_t, vec2_t> view_t;

typedef boost::fusion::result_of::value_at_c<view_t, 2>::type value_t; // OK!

なお、この記事の内容の方法は僕の試行錯誤によるもので、Boost.Fusion に
もっと上手くポータブルにやれる機構が用意されているかもしれないことを付けくわえておきます。

突っこみ等がありましたら、コメントお願いします。

ボレロ村上 - ENiyGmaA Code

中３女子です。