非型テンプレートパラメータの有用性は，コンパイル時整数演算を可能にする． 例えば，以下のテンプレートはその引数の階乗を計算する:

template< unsigned n >
struct factorial
{
    static const unsigned value = n * factorial<n-1>::value;
};

template<>
struct factorial<0>
{
    static const unsigned value = 1;
};

上のようなプログラムの断片化はmetafunctionと呼ばれ，実行時に評価されるように設計された関数との 関係を見て取るのは容易である: 「metafunction 引数」はテンプレートパラメータとして渡され， 「返り値」はネストした静的定数(static constant)として定義される． C++でのコンパイル時式と実行時計算の間の大きな隔たり(?)のため， メタプログラミングはそれと対応する実行時計算とは異なって見える． このように，Schemeと同じくC++メタプログラマは通常のプログラムと同一の言語でコードを書くことができるが， その際，完全なC++言語のサブセットが使えるに過ぎない: それらはコンパイル時に評価されることが可能な式である． 上のコードを直接，実行時の階乗関数の定義と比べれば:

unsigned factorial(unsigned N)
{
    return N == 0 ? 1 : N * factorial(N - 1);
}

2つの再帰定義の間のアナロジーを見て取るのは容易だが， 再帰は通常，実行時C++よりもC++メタプログラミングにとって，より重要である． 再帰が言語独特であるLispのような言語と比べ，C++プログラマは通常，出来る限り再帰を避ける． これは効率という理由だけでなく，「文化的要因」も大きい: 再帰プログラムは単純に(C++プログラマにとって) 考えるのが難しい．しかし純粋なLispの様に，C++テンプレート機構は関数的プログラム言語である: ループ変数を維持するために必要なデータ操作を使うことはしないのである．

実行時とコンパイル時の階乗関数の主要な違いは，終了条件式である: メタ階乗はNがゼロの時のビヘイビアを記述するために， パターンマッチング機構の一種としてテンプレート特殊化を使っている． 実行時世界との構文的類似物は，同じ関数の2つの別の定義を要求する． この場合，2番目の定義のインパクトは最小であるが， 大きなメタプログラムでは，終了定義を維持し理解するコストは重要になる．

C++ metafunction の返り値は名前付けされていなければならないことに注意． ここで選ばれた名前，value はMPLで全ての数値的な返り値に使われているものと同じである． これから見るように，metafunctionの返り値にとって，一定の名前付けの習慣を確立することは， ライブラリの力に対して決定的である．

factorial metafunctionをどうやって応用すればよいのだろうか．例えば， 異なる型の実体の全ての順列を保持するのに適した大きさの配列型を作りたいとする．

// permutation_holder<T>::type は配列型．これは与えられたTの全ての順列を含むことができる．

// スカラのための非特殊化版テンプレート
template< typename T >
struct permutation_holder
{
    typedef T type[1][1];
};

// 配列型のための特殊化版
template< typename T, unsigned N >
struct permutation_holder<T[N]>
{
    typedef T type[factorial<N>::value][N];
};

ここで型計算という概念を導入した．上のfactorialの様に， permutatioin_holderテンプレートは metafunctionである．しかし， factorialが符号なし整数値を扱うのに対し，permutatioin_holderは (ネストしたtypedef typeとして)型を受け取り，「返す」． C++ 型システムは非型テンプレート引数(例えば整数)として使う式より遙かに豊富な式集合を提供するので， C++メタプログラミングは，ほとんど型計算の合成となる傾向がある．

プログラムが型集合を扱う能力は興味深いC++メタプログラミングの中でも中核に位置する． この能力は，MPLによりよくサポートされているので，ここでは基本的なことを少しだけ紹介しておく． 後に，MPLを使ってどのように実装できるかを示すために，下の例をもう一度扱うだろう．

まず，集合を表現する方法が必要である．ひとつのアイデアは，構造体に型を保持する，というものだ．

struct types
{
    int t1;
    long t2;
    std::vector<double> t3;
};

不幸なことに，このやり方は，C++が提供するコンパイル時型チェックの力を損なう: メンバの名前が何であるか見つける方法はないし，たとえ既に述べたような習慣に倣って名前付けしていると仮定しても， そこにどれくらい多くのメンバがあるのか知る方法はない． この問題をとくための鍵は，表現の同一性を増やすことである． もしどんなシーケンスであっても最初の型を得ることができて，さらにシーケンスの残りを得ることができるような， 一定の方法があれば，簡単に全てのメンバにアクセスできる:

template< typename First, typename Rest >
struct cons
{
    typedef First first;
    typedef Rest rest;
};

struct nil {};

typedef
      cons<int
    , cons<long
    , cons<std::vector<double>
    , nil
    > > > my_types;

上のtypesで記述された構造体は単一リンクリストのコンパイル時類似物である． それはCzarneckiとEiseneckerによって，初めて導入された[CE98]． 今や，構造体を調整したので，C++テンプレート機構はそれを「加工する」ことができる． それを行う単純なメタ関数を試してみよう． ユーザは任意の型集合から，最も大きなものを見つけたいとする． ここで，すでに親しんでいる再帰的 metafunction 形式を応用できる:

// 2つの型のうち大きい方を選ぶ
template<
      typename T1
    , typename T2
    , bool choose1 = (sizeof(T1) > sizeof(T2)) // 渡す!
    >
struct choose_larger
{
    typedef T1 type;
};

// sizeof(T2) >= sizeof(T1) の場合の特殊化版
template< typename T1, typename T2 >
struct choose_larger< T1,T2,false >
{
    typedef T2 type;
};

// コンスリストから最大のものを得る
template< typename T > struct largest;

// コンスリストから引きはがすための特殊化版
template< typename First, typename Rest >
struct largest< cons<First,Rest> >
    : choose_larger< First, typename largest<Rest>::type >
{
    // baseを継承した型
};

// ループ終了のための特殊化版
template< typename First >
struct largest< cons<First,nil> >
{
    typedef First type;
};

int main()
{
    // my_typesのうち最も大きなものを出力
    std::cout
        << typeid(largest<my_types>::type).name()
        << std::endl
        ;
}

このコードについて書いておく価値のあることがいくつかある．

これらのテクニックは勿論，多くの優れたC++メタプログラマの蓄積の価値ある一部であるが， これらを使うと，プログラムは，読みづらく書きづらい，異常なスタイルで書かれることになる． 広く使われる構造をカプセル化し，ループ終了を内的に扱うことで，MPLはトリッキーなハックと テンプレート特殊化の両方の必要を軽減している．

C++ テンプレートインスタンス化機構が機能する方法により、型選択プリミティブ(if_) の応用可能性には、同等の選択コードを手書きするのに比べて多少の制限が加わる。 例えば、生ポインタ(U*)か、std::auto_ptr<U>か、 あるいはBoostのスマートポインタ[SPL]、 例えばboost::scoped_ptr<U> のいずれかであるTに対してインスタンス化され、ポインタ型(U)を返す、 pointed_type<T>::typeのような、 pointed_type特性テンプレートを実装することを考えてみよう。

BOOST_MPL_ASSERT_IS_SAME(pointed_type<my*>::type, my);
BOOST_MPL_ASSERT_IS_SAME(pointed_type< std::auto_ptr<my> >::type, my);
BOOST_MPL_ASSERT_IS_SAME(pointed_type< boost::scoped_ptr<my> >::type, my);

不幸なことに、この問題に対してif_を単純に応用してもうまくいかない: ¹

template< typename T >
struct pointed_type
    : mpl::if_<
          boost::is_pointer<T>
        , typename boost::remove_pointer<T>::type
        , typename T::element_type // #1
        >
{
};

// 次のコードは#1の行でコンパイルエラーを起こす:
// ::に続く名前は、クラス名か名前空間名でなければならない
typedef pointed_type<char*>::type result;

明らかに、typename T::element_typeという式は、T == char*の場合、 有効ではない。コンパイラはそれを指摘しているのである。 選択コードの実装を手書きすれば、この問題を解決することが出来る:

namespace aux {
// 一般的な場合
template< typename T, bool is_pointer = false >
struct select_pointed_type
{
    typedef typename T::element_type type;
};

// 生ポインタのための特殊化
template< typename  T >
struct select_pointed_type<T,true>
{
    typedef typename boost::remove_pointer<T>::type type;
};
}

template< typename T >
struct pointed_type
   : aux::select_pointed_type<
          T, boost::is_pointer<T>::value
        >
{
};

しかしこれは、もし繰り返し行うことが必要ならすぐにひどいことになる。 そして、部分特殊化が使えない場合にはもっと悪化する。 次のように、この問題を扱えるようにすることが出来る:

namespace aux {
template< typename T >
struct element_type
{
     typedef typename T::element_type type;
};
}

template< typename T >
struct pointed_type
{
    typedef typename mpl::if_<
          boost::is_pointer<T>
        , typename boost::remove_pointer<T>::type
        , typename aux::element_type<T>::type
        >::type type;
};

しかし、これもまたうまくいかない。aux::element_type<T>のネストした typeメンバへのアクセスにより、コンパイラが element_type<T>をT == char* でインスタンス化しなければならないなら、 このインスタンス化は当然、無効である。 また、先ほどの場合ならばコンパイルエラーにはならないが、 boost::remove_pointer<T>テンプレートは常に同じように、 同じ理由(ネストしたtypeメンバ)でインスタンス化される。 テンプレートの「重さ」(どれほどのインスタンス化がコンパイラに課せられるか) に依存するが、致命的でない、不要なインスタンス化は問題になるかもしれないし、ならないかもしれない。 しかし、一般的な大雑把なやり方で、そのようなコードを避けることが出来る。

先ほどのエラーに戻れば、上のコードをコンパイルするために、 if_の呼び出しの外で、aux::element_type<T>に対し、 そのネストしたtypeを「問い合わせる」振る舞いという要素が必要である。 boost::remove_pointer<T>特性テンプレートと、 aux::element_type<T>の両方が、結果型のために、習慣化された同じ名前を使っている、 という事実により、リファクタリングはより簡単になる:

template< typename T >
struct pointed_type
{
 private:
    typedef typename mpl::if_<
          boost::is_pointer<T>
        , boost::remove_pointer<T>
        , aux::element_type<T>
        >::type func_;

 public:
    typedef typename func_::type type;
};

これで、コンパイラがboost::remove_pointer<T>、 aux::element_type<T>の両方のインスタンス化が起こらないことが保証される。 たとえ、if_テンプレートのパラメータとして実際に使われてでも、である。 これにより、func_として最終的に選ばれない限り、 aux::element_type<char*>から逃れることが出来る。

上の技はテンプレートメタプログラムでは広く使われている。if_と高水準の等価性をもつ ものを導入することで、ネストしたtypeメンバの選択を可能にするのである。 呼び出しの一部としてfunc_::type操作([nullary]メタ関数クラス適用と呼ばれる) を行うものである。MPLはそのようなテンプレートを提供し、apply_ifと呼ばれている。 これを使えば、上のコードを次のようにシンプルに書き直すことが出来る:

template< typename T >
struct pointed_type
{
    typedef typename mpl::apply_if<
          boost::is_pointer<T>
        , boost::remove_pointer<T>
        , aux::element_type<T>
        >::type type;
};

この技を完全にレビューするために、多少難しい例を考えてみよう。 boost::remove_pointer特性テンプレート[TTL] の高水準ラッパー定義したいとする。これはポインタ修飾を条件付ではがすものである。 これを、remove_pointer_ifと呼ぼう:

template<
      typename Condition
    , typename T
    >
struct remove_pointer_if
{
    typedef typename mpl::if_<
          Condition
        , typename boost::remove_pointer<T>::type
        , T
        >::type type;
};

上のコードは最初はうまく行くが、先に述べた問題に直面することになる。 boost::remove_pointer<T>は、その結果が使われることがなくても インスタンス化される。メタプログラミングの世界では、コンパイル時間は重要な資源であり [Abr01]、それは不要なテンプレートインスタンス化により浪費される。 if_の両方の引数がnullaryメタ関数クラス適用の結果である時に、 この問題をどう対処するかについては、ちょうど今見てきた。 しかしこの例では、引数のひとつ(T)はただの単純な型であり、 リファクタリングは不可能のように思われる。

この状況を脱する最も簡単な方法は、if_に、 Tの代わりに本当のnullaryメタ関数を渡すことである。 これは、呼び出しによりTを返すものである。 MPLはそのために単純な方法を提供する。 Tとif_の代わりに、identity<T>と apply_ifを使えばいいのである。

template<
      typename Condition
    , typename T
    >
struct remove_pointer_if
{
    typedef typename mpl::apply_if<
          Condition
        , boost::remove_pointer<T>
        , mpl::identity<T>
        >::type type;
};

これで、望みどおりのものを手にすることが出来る。

C++では，パラメータ付きコンパイル時計算を可能にする基本的な言語構築は， クラステンプレート ([ISO98]，14.5.1 [temp.class]節)である． 単純なクラステンプレートは，メタ関数のために選択可能な最も単純なモデルである: 実際のテンプレートパラメータとして型と/または非型の引数を受け取り，インスタンス化は新しい型を「返す」． 例えば，次のコードはその引数から派生した型を作る:

template< typename T1, typename T2 >
struct derive : T1, T2
{
};

しかし，このモデルは制限が多すぎる:メタ関数の結果をクラス型に制限するだけでなく， 与えられたクラステンプレートの実体化に制限するのである． 全て呑めた関数呼び出しが，余計な水準のテンプレートネストを必要とするという事実については何も言っていないのに． 特定のメタ関数に対しては，これでいいのかもしれないが， 例えばintを「返す」ようなことができなくなってしまうモデルでは， 明らかに十分汎用的とは言えない． この基本的な要求を満たすために，返り値を提供するためのネストした型に頼らなければならない．

template< typename T1, typename T2 >
struct derive
{
    struct type : N1, N2 {};
};

// 馬鹿げた特殊化，しかしint を"返す"
template<>
struct derive<void,void>
{
    typedef int type;
};

Veldhuizen [Vel95a] は「コンパイル時関数」としてのこの形式の クラステンプレートについて最初に語った．そして， Czarneckiと Eisenecker [CE00] は同様の述語(彼らは，我々同様「メタ関数」という単純な言葉も使った)として 「テンプレートメタ関数」を導入した． Czarneckiと Eiseneckerはまた，単純なメタ関数表現の限界を認識し，我々が項2.2.3 で議論する形式を提案した．

構文的に単純だが，単純なテンプレートメタ関数形式はCxx;の他の部分と必ずしも最適にやりとりできるわけではない． 特に，単純なメタ関数形式は，その定義を不必要に見苦しく，退屈にし，高次のメタ関数 (他のメタ関数を操作するメタ関数)と共に機能するしかない． 単純なメタ関数を他のテンプレートに渡すために，テンプレートテンプレートパラメータを使う必要がある．

// F(T1,F(T2,T3)) を返す
template<
      template<typename> class F
    , typename T1
    , typename T2
    , typename T3
    >
struct apply_twice
{
  typedef typename F<
        T1
      , typename F<T2,T3>::type
      >::type type;
};

// T1,T2,T3から派生した型を返す新しいメタ関数
template<
      typename T1
    , typename T2
    , typename T3
    >
struct derive3
    : apply_twice<derive,T1,T2,T3>
{
};

これは異なるように見えるが，機能する． ² しかし，メタ関数からメタ関数を「返す」時に初めて，これが壊れているということに気づくのである．

//  G s.t. G(T1,T2,T3) == F(T1,F(T2,T3)) を返す．
template< template<typename> class F >
struct compose_self
{
    template<
          typename T1
        , typename T2
        , typename T3
        > 
    struct type
        : apply_twice<F,T1,T2,T3>
    {
    };
};

第一の，そして最も明らかな問題は，compose_selfの適用結果がそれ自体，型でなくテンプレートである， ということで，このため通常の方法で他のメタ関数に渡すことができない． 更に些細な問題だが，しかし，「返される」メタ関数は実際には我々が望むものではない． apply_twiceの様に振る舞うが，ひとつの重要な点で異なっている: それは同一性だ． C++型機構では，compose_self<F>::template type<T,U,V>は， apply_twice<F,T,U,V>と同義ではない．そして，メタ関数を比較するメタプログラムならば， この事実を発見するだろう．

C++ は型とクラステンプレートテンプレートパラメータとの間に厳格な線引きを行うので， 単純なメタ関数に頼れば，メタ関数とメタデータとの間に「壁」が作られて， メタ関数は第2のクラス群の状態へと格下げされる． 例えば，型シーケンスの紹介を思い出せば，メタ関数のconsリストをつくる方法はないのである．

typedef cons<derive, cons<derive3, nil> > derive_functions; // error!

consセルの再定義を考えるかもしれないので，先頭要素としてderiveを渡すことができる:

template <
      template< template<typename T, typename U> class F
    , typename Tail
    >
struct cons;

しかし，別の問題が出てくる: C++テンプレートは型引数という点で多相であるが， テンプレートテンプレートパラメータという点では多相ではない． テンプレートテンプレートパラメータのアリティ(パラメータの数)は厳格に強制されるので， derive3をconsリストに埋め込むことはまだできない． さらに，型とメタ関数の間の多相はサポートされていない(コンパイラはどちらかであることを期待する)， そして，既に見たように，「返される」メタ関数の構文と意味は返される型のそれとは異なるのである． 単純なテンプレートメタ関数形式で全てをやろうとすれば，高次のメタ関数の応用性をひどく制限し， また実装上の明白性，単純性，ライブラリの大きさといった，あらゆるところに悪い効果を起こすことになる．

幸運にも，「ソフトウェアには別の水準の間接化によって解決できない問題はない」 という自明の理がここで使える．メタ関数を一級オブジェクトの状態に昇進させるために， MPLは「メタ関数クラス」の概念を導入する．

// deriveのメタ関数クラス形式
struct derive
{
    template< typename N1, typename N2 >
    struct apply
    {
        struct type : N1, N2 {};
    };
};

この形式は，STLの関数オブジェクトとして知られているので，解りやすいだろう． ネストしたapplyテンプレートは実行時の関数呼び出し操作と同じ役割を持つ． 実際，コンパイル時メタ関数クラスとメタ関数の関係は，実行時関数オブジェクトと関数の関係と同じである．

// addの関数形式
template< typename T > T add(T x, T y) { return x + y; }

// addの関数オブジェクト形式
struct add
{
    template< typename T >
    T operator()(T x, T y) { return x + y; }
};

メタ関数クラス形式は前に述べた通常の添付レースメタ関数の全ての問題を解決する: これは通常のクラスなので，コンパイル時メタデータシーケンスに置くことも可能だし， 別の関数から，別のメタデータと同じプロトコルで使うことも可能だ． だから，通常のメタデータとメタ関数に対して，それぞれ個別のアリティをサポートして演算を行う ライブラリコンポーネントを別々に提供するようなコードの重複は必要なくなる．

しかし，メタ関数クラスを，コンパイル時関数実体の代理として考えることは， 同様にコード重複の危険にさらされるだろう:もしライブラリ自身のプリミティブ，アルゴリズム，その他諸々が クラステンプレートとして表されているなら，より高次の関数のコンテキストではこれらのアルゴリズムを再利用できないか， 或いは，全てのアルゴリズムを第2の形式で書き直さなければならない．例えば， 2つの異なるfindがある:

// ユーザフレンドリな形式
template<
      typename Sequence
    , typename T
    >
struct find
{
    typedef /* ... */ type;
};

// "メタ関数クラス"形式
struct find_func
{
    template< typename Sequence, typename T >
    struct apply
    {
        typedef /* ... */ type;
    };
};

勿論，3番目の選択肢は，「ユーザフレンドリ」形式を完全になくして，次のように書くことである:

typedef mpl::find::apply<list,long>::type iter;
// 或いはもしこちらの方が好きならば，
// typedef mpl::apply< mpl::find,list,long >::type iter;

次のように書く代わりに:

typedef mpl::find<list,long>::type iter;

このユーザビリティはひどすぎる．ライブラリのアルゴリズムを直接呼び出すことは， 別のアルゴリズムやメタ関数に引数としてアルゴリズムを渡すことよりもずっと多いからだ．

このジレンマに対するMPLのとった答えはラムダ式である． ラムダはライブラリがカリー化メタ関数を使いそれらをメタ関数クラスに変換することを可能にする仕組みである． これにより，findアルゴリズムをより告示のメタ関数に引数として渡したければ， 次のように書けばよいのだ:

using namespace mpl::placeholder;
typedef mpl::apply< my_f, mpl::find<_1,_2> >::type result;

_1と_2はメタ関数クラスを生成する第1，第2引数のプレースホルダである． これは下のように，ユーザがfindをコードで直接使いたい時に直感的な構文を維持する:

typedef mpl::find<list,long>::type iter;

ラムダの能力は項3でより詳細に述べる．

(型)シーケンスに対するコンパイル時反復は，テンプレートメタプログラミングの基本的概念のひとつである． 演算されるオブジェクト型の違いは，同じだが同一ではないコード/設計の可変性の最も共通する点である． そしてそのような設計が，メタプログラミングの直接の狙いになることもある． テンプレートははじめは，この実際的な問題(例えばstd::vector)を解決するために設計された． しかし，(スタンドアロンの型ではなく)型シーケンスに対する操作，反復にとって，既に定義された抽象化，構築なしに， また，現在の言語の能力を使ってこれらの構築をエミュレートする既知の技術を使わずには， 高次のメタプログラミングを手助けする効果は，制限されるだろう．

Czarnecki と Eisenecker [CE98], [CE00] が最初に，コンパイル時型シーケンスとそれらにたいするいくつかのアルゴリズムを導入した． 木，リストなどの共通データ構造をクラステンプレートの合成を利用してコンパイル時に表現するアイデアは， 既に存在していたが(例えば，式テンプレートライブラリの多くは，式の"パース"プロセスの一部として， そのような木を構築している[Vel95b])． Alexandrescu [Ale01] は型リストとそれらに対するいくつかのアルゴリズムを， 多くのデザインパターンを実装するために利用した; その時のコードはLokiライブラリとして知られている [Loki]

Boost Metaprogramming Libraryの多くのアルゴリズムはシーケンスを操作する．例えば，リストから型を検索するのは次のような感じだ:

typedef mpl::list<char,short,int,long,float,double> types;
typedef mpl::find<types,long>::type iter;

ここでは，findは2つのパラメータを受け取る - 検索する(型)シーケンスと， 探し出したい型(long) - そして，イテレータ iterを返す． これは，シーケンスのうち， iter::type がlongと同一である最初の要素を指している． もしそのような要素が存在しなければ，iterはend<types>::typeと同一である． 基本的に，これは，std::listやstd::vectorの中からある値を検索する方法と同じだが， mpl::findがシーケンスをひとつのパラメータとして受け取る点が異なる． std::findは2つのイテレータを受け取るからだ． 他はほとんど同じだろう - 名前も同じだし，セマンティクスはかなり近い，イテレータがあり， また，加賀だけでなく，述語を使っても探すことができる．

typedef mpl::find_if< types,boost::is_float<_> >::type iter;

STLとの概念的/構文的類似は偶然ではない．STLの概念的枠組みをコンパイル時世界に再利用することで， シーケンスデータ構造を扱う際に，よく知った，健全なアプローチを利用できるようになる． プログラマがSTLによって既に知っているアルゴリズムとイディオムはコンパイル時にも再利用できる． これは，MPLの大きな強みのひとつだと思う．テンプレートメタプログラミングライブラリを構築しようとした， 初期のものとは異なるのだ．

上のfindの例では，mpl::listテンプレートを使って作られたシーケンスの中から型を探した; しかしライブラリが提供するシーケンスはlistだけではない． mpl::findも，ハードコーディングされた他のアルゴリズムでも， listシーケンスだけしか扱えないわけではない． listはMPLの順シーケンスコンセプトのひとつのモデルに過ぎない． そしてfindはこのコンセプトの要求を満たすものならなんでも大丈夫だ． MPLにおけるシーケンスコンセプトの階層構造は極めてシンプルである - シーケンスはbegin<>と end<>によって，その要素の範囲へのイテレータが生成されるコンパイル時のあらゆる実体である; 順シーケンスはそのイテレータが順イテレータ の要求を満たすシーケンスである; 双方向シーケンスはそのイテレータが双方向イテレータ の要求を満たす順シーケンスである; 最後に，ランダムアクセスシーケンスは，そのイテレータが ランダムアクセスイテレータの要求を満たす双方向シーケンスである． ³

特定のシーケンスの実装から(イテレータによって)アルゴリズムを切り離すことで， メタプログラマは自分自身のシーケンス型を作成し，ライブラリの他の部分を自由に使うことができる． 例えば，次のように，3つの型のシーケンスを扱うtiny_listを定義することができる:

template< typename TinyList, long Pos >
struct tiny_list_item;

template< typename TinyList, long Pos >
struct tiny_list_iterator
{
    typedef typename tiny_list_item<TinyList,Pos>::type type;
    typedef tiny_list_iterator<TinyList, Pos-1> prior;
    typedef tiny_list_iterator<TinyList, Pos+1> next;
};

template< typename T0, typename T1, typename T2 >
struct tiny_list
{
    typedef tiny_list_iterator<tiny_list, 0> begin;
    typedef tiny_list_iterator<tiny_list, 3> end;
    typedef T0 type0;
    typedef T1 type1;
    typedef T2 type2;
};

template< typename TinyList >
struct tiny_list_item<TinyList,0>
{
    typedef typename TinyList::type0 type;
};

template< typename TinyList >
struct tiny_list_item<TinyList,1>
{
    typedef typename TinyList::type1 type;
};

template< typename TinyList >
struct tiny_list_item<TinyList,2>
{
    typedef typename TinyList::type2 type;
};

これは，mpl::list同様にライブラリのアルゴリズムで使うことができる:

typedef tiny_list< char,short,int > types;
typedef mpl::transform<
      types
    , boost::add_pointer<_1>
    >::type pointers;

tiny_listは双方向シーケンスのモデルである． advanceとdistanceメンバをtiny_list_iteratorに追加すれば， ランダムアクセスシーケンスになる:

template< typename TinyList, long Pos >
struct tiny_list_iterator
{
    static long const position = Pos;

    typedef typename tiny_list_item<TinyList,Pos>::type type;
    typedef tiny_list_iterator<TinyList, Pos-1> prior;
    typedef tiny_list_iterator<TinyList, Pos+1> next;

    template< typename N > struct advance
    {
        typedef tiny_list_iterator<
              TinyList
            , Pos + N::value
            > type;
    };

    template< typename Other > struct distance
    {
        typedef mpl::integral_c<
              long
            , Other::position - position
            > type;
    };
};

tiny_list自身は興味の対象ではない(結局それは3つの要素を保持できる)が， もし上のテクニックが自動化され，(5,10,20,...の要素の)それほど小さくないシーケンスを定義できるなら， 価値あることだろう． ⁴

外部コード生成はひとつの選択肢だが，言語内での解決も存在する． しかしそれはテンプレートメタプログラミングではなく，プリプロセッサメタプログラミングである． 実際，MPLのvector - ランダムアクセスイテレータを提供する固定サイズ型シーケンス - は上のtiny_listによく似た実装が行われている． そこでは，Boost Preprocessor ライブラリ[PRE]が使われている．

このように，ライブラリはユーザに，STLフレームワークとほとんど完全に対応するコンパイル時フレームワークを提供する． これは，メタプログラミングのタスクを解決するのに役立つのだろうか? 以前の最大の例に戻って， MPLが提供するものを利用したよりよいやり方で書き直せるか見てみよう． 実際，見るべきものはそう多くない，なぜならMPLの実装はワンライナーだから (それをここでは再適応性のために展開してるだけのことだ) ⁵ :

template< typename Sequence >
struct largest
{
    typedef typename mpl::max_element<
          Sequence
          mpl::less<
              mpl::sizeof_<_1>
            , mpl::sizeof_<_2>
            >
        >::type iter;

    typedef typename iter::type type;
};

トリッキーなパターンマッチングによる終了条件はもうないし，部分特殊化ももうない; そして，より重要なことだが，上のコードが， オリジナルのものについては誰も言えなかった何かしていることは明らかなのだ - 例え，全てがテンプレートであっても．

ライブラリの内部構造をもう少し調べるために，上の例でのmax_elementがどう実装されているのか見てみよう． 今度こそはあのひどい部分特殊化，深遠なパターンマッチングなどが全部現れると思われるかもしれない． では，見てみよう:

template<
      typename Sequence
    , typename Predicate
    >
struct max_element
{
    typedef typename mpl::iter_fold<    
          Sequence
        , typename mpl::begin<Sequence>::type
        , if_< less< deref<_1>,deref<_2> >, _2, _1 >
        >::type type;
};

ここで注意すべきことはまず，このアルゴリズムは別のもので実装されている，ということだ．つまりそれは， iter_fold． 実際，これはおそらく，この例の最も重要な点である．なぜなら， ライブラリにあるほとんど全ての汎用シーケンスアルゴリズムは，iter_foldを使って実装されているからだ． もしユーザが自分用のシーケンスアルゴリズムを必要とするなら，まず間違いなくこのプリミティブを使うことができる． これは，頑張って反復を作ったり，ループ終了のために特殊な場合のパターンマッチングをしたり， 部分特殊化がないために代替手段を作ったり，といったことが必要ない，ということを意味する． そしてまた，そのアルゴリズムは自動的にライブラリが実装した最適化の恩恵を受けることができるし (例えば再帰の展開)，順シーケンスのモデルならばどんなシーケンスでも扱える，ということも意味する． なぜならiter_foldはそのシーケンス以上なにも要求しないからだ．

iter_foldアルゴリズムは基本的に，多くの関数的プログラミング言語で基本的な， よく知られたプリミティブを構成するfoldやreduce関数の，コンパイル時の対応物である． C++プログラマにとってより解りやすいアナロジーは C++標準ライブラリ([ISO98], 26.4.1項 [lib.accumulate]) のstd::accumulateアルゴリズムである． しかし，iter_foldは再帰巡回の自然な性質の利益を受けるように設計されている: これは，2つのメタ関数クラス引数を受け取り，その最初のものは "入りの"状態に適用され，二番目のものは"出の"状態に適用される．

MPLで定義されるiter_foldのインタフェースは以下の通り:

template<
      typename Sequence
    , typename InitialState
    , typename ForwardOp
    , typename BackwardOp = _1
    >
struct iter_fold
{
    typedef /*unspecified*/ type;
};

アルゴリズムは2項ForwardOpとBackwardOp操作の2方向の連続した適用結果を「返す」． これらの操作は[begin<Sequence>::type, end<Sequence>::type) の範囲のイテレータと，演算の前回の結果に対して行われる; InitialStateは論理的にシーケンスの前に置かれ， 順巡回に含まれる．結果型は，もしシーケンスがemptyなら，InitialStateと同一である．

ライブラリはまた，iter_fold_backward,fold,fold_backwardアルゴリズムを提供する． これらはiter_foldのラッパであり，よく使われるパターンのために存在する．

今まで見てきたものは，型シーケンス(及び型シーケンスのアルゴリズム)である． 同じように，ライブラリを使ってコンパイル時値を操作することは可能だし簡単だ． 覚えておくべき唯一のことは，C++では，クラステンプレートの非型テンプレートパラメータは 非多相的な振る舞いのもう一つの例である，ということだ．言い換えれば， もしメタ関数を非型テンプレートパラメータ(例えばlong)を受け取るように定義したら， コンパイル時汎整数定数以外の何も，それには渡すことはできない．

template< long N1, long N2 >
struct equal_to
{
    static bool const value = (N1 == N2);
};

equal_to<5,5>::value; // ok
equal_to<int,int>::value; // error!

もちろん次のものも機能しない

typedef mpl::list<1,2,3,4,5> numbers; // error!

これは明らかな制限だが，ライブラリの設計にとって別のジレンマを課してくる: 一方で，ユーザに対して型操作だけに制限したくない． 他方，整数演算を完全にサポートするには，少なくともほとんどのライブラリの機能を二度書きしなければならなくなる． ⁶ - メタ関数を通常のクラステンプレートで表現するかどうか，という状況とおなじである． この問題に対する解決は，同様である: 整数値を型でラップするのだ ⁷ ．例えば，数値リストを作るのには次のように書ける:

typedef mpl::list<
      mpl::int_c<1>
    , mpl::int_c<2>
    , mpl::int_c<3>
    , mpl::int_c<4>
    , mpl::int_c<5>
    > numbers;

汎整数定数値を型にラップすることで第一クラス群にすることは，メタプログラミングの内側では非常に重要である． しかし，もし使っているメタ関数が， 型，整数値，他のメタ関数，或いは他の何か，例えば固定小数点，有理数(mpl::fixed_cと mpl::rational_c)に対する演算だとしても，多くの場合それを知らない(そして気付きもしない)．

しかし，ユーザにとってみれば，上の例は短くて不当なものより遙かに冗長だ． このように，利便性のために，ライブラリはユーザに非型テンプレートパラメータを受け取るテンプレートを与えてはいるが， より簡潔な記述も提供している:

typedef mpl::list_c<long,1,2,3,4,5> numbers;

同様に，vectorもある:

typedef mpl::vector_c<long,1,2,3,4,5> numbers;

C++に汎用的なメタプログラミング機構を提供するというこれまでの努力は，常に コンス-スタイルの型リストと，size，atの様な， 特定のシーケンス実装と結びついた，いくつかのコアとなるアルゴリズムに向けられてきた． そのようなシステムは，純粋関数指向Lispの機能性を思い起こさせるエレガントな単純性を持っている． 実行時ライブラリ(特にSTL)に対応するものによって提供された，シーケンスアルゴリズムの基本セットでさえ， 実装には大変時間がかかったが，もしSTLから何も学んでいなかったら， これらのアルゴリズムの実装を特定のシーケンスの実装に結びつけることは，間違った努力だったに違いない!

真実は，ひとつの「最良の」型シーケンスの実装などない，ということだ． その理由は，ひとつの「最良の」実行時シーケンスの実装が決して存在しないことの理由と同じである． さらに，すでにかなりの数の型リスト実装が現在使われている; また，STLアルゴリズムがSTLコンテナ以外のシーケンスを操作できるように， MPLアルゴリズムも異なる型シーケンスで機能するように設計されている．

型リストだけが役に立つコンパイル時シーケンスではない，という事実に驚く人もいるだろう． 再び，C++標準ライブラリにリスト，ベクタ，デキュー，セットなどがあるのと同じ理由で， 様々なコンパイル時コンテナが必要なのだ - 異なるコンテナは異なる機能と動作特性を持ち， 特定のアルゴリズムでの応用可能性や効率だけでなく，それらを使うコードの表現性や冗長性も決定する． 実行時のパフォーマンスはC++メタプログラミングにとって問題ではないが， コンパイル時間は最先端のC++ソフトウェア開発では重要なボトルネックになる[Abr01]．

MPLは5種類の組み込みシーケンスを提供している: list, list_c (これは値ラッパのlist), 最大サイズ固定のランダムアクセスシーケンスであるvector， vector_c，そして，連続する整数値のランダムアクセスシーケンスであるrange_cである． しかし，より重要なことは，任意のシーケンス型に適応する能力である． シーケンスがライブラリアルゴリズムで使われるために提供しなければならない唯一のコアの操作は， begin<>とend<>メタ関数である．これは， シーケンスのイテレータを"返す"． STLの様に，ライブラリが提供する汎目的シーケンスアルゴリズムのほとんどを実装するために使われるものは， イテレータである．同じくSTLの様に，アルゴリズムの特殊化が特定のシーケンスについての実装の知識を利用するために 使われる: back<>, front<>, size<> at<>の様な，"基本"シーケンス操作はシーケンス型に対し特殊化することで， 完全な汎用版よりも効率的な実装を提供している．

ほとんど偶然の一致だが，ループ展開はコンパイル時反復アルゴリズムにとって，実行時アルゴリズム同様重要である． その理由を知るには，C++メタプログラミングでの全ての"ループ"が，実際， 再帰によって実装されていて，テンプレートインスタンス化深度はコンパイラの実装の価値ある資源なのだ， ということを覚えておかなければならない． 事実，C++標準 Annex B([ISO98], annex B [limits])では， 最小でも17回の再帰的にネストしたテンプレートインスタンス化を推奨している; しかし，気合いの入った多くのメタプログラムにとって，これではあまりにも少なすぎる． そのいくつかでは，優れたコンパイラの，頑張っているインスタンス化制限をも簡単に突破してしまう． これがどう振る舞うかを見るために，アルゴリズムの状態とシーケンスのそれぞれの要素を組み合わせる foldメタ関数の単純な実装を調べてみよう．

namespace aux {

// 非特殊化版は内部状態と最初の要素を組み合わせ，残りの処理を再帰呼び出しする
template<
      typename Start
    , typename Finish
    , typename State
    , typename BinaryFunction
    >
struct fold_impl
  : fold_impl<
        typename Start::next
      , Finish
      , typename apply<
              BinaryFunction
            , State
            , typename Start::type
            >::type
      , BinaryFunction
      >
{
};

// ループ終了のための特殊化版
template<
      typename Finish
    , typename State
    , typename BinaryFunction
    >
struct fold_impl<Finish,Finish,State,BinaryFunction>
{
    typedef State type;
};

} // namespace aux

// public interface
template<
      typename Sequence
    , typename State
    , typename ForwardOp
    >
struct fold
    : aux::fold_impl<
        , typename begin<Sequence>::type
        , typename end<Sequence>::type
        , State
        , typename lambda<ForwardOp>::type
        >
{
};

シンプルでエレガントだけど，この実装は常に，少なくとも入力シーケンスの数と同じレベルの 再帰的テンプレートインスタンス化を必要とする． ⁸ ライブラリは再帰の明示的"展開"によって，この問題を対処している． foldの例にこのテクニックを使うために，アルゴリズムの1段階を洗い直すことから始める． fold_impl_stepメタ関数は2つの結果を持つ: type (次の状態)と，iterator(次のシーケンス位置)である．

template<
      typename BinaryFunction
    , typename State
    , typename Start
    , typename Finish
    >
struct fold_impl_step
{
    typedef typename apply<
          BinaryFunction
        , State
        , typename Start::type
        >::type type;

    typedef typename Start::next iterator;
};

主要なアルゴリズムの実装のように，ループ終了条件を特殊化しているので， そのステップはno-opになる．

template<
      typename BinaryFunction
    , typename State
    , typename Finish
    >
struct fold_impl_step<BinaryFunction,State,Finish,Finish>
{
    typedef State type;
    typedef Finish iterator;
};

ここでは， 単純にN回のfold_impl_stepの呼び出しを挿入することで， あらゆる定数要因Nによるfoldのインスタンス化深度を減らしている．

template<
      typename Start
    , typename Finish
    , typename State
    , typename BinaryFunction
    >
struct fold_impl
{
 private:
    typedef fold_impl_step<
        BinaryFunction
      , State
      , Start
      , Finish
      > next1;
    
    typedef fold_impl_step<
        BinaryFunction
      , typename next1::type
      , typename next1::iterator
      , Finish
      > next2;
    
    typedef fold_impl_step<
        BinaryFunction
      , typename next2::type
      , typename next2::iterator
      , Finish
      > next3;
    
    typedef fold_impl_step<
        BinaryFunction
      , typename next3::type
      , typename next3::iterator
      , Finish
      > next4;
    
    typedef fold_impl_step<
          typename next4::iterator
        , Finish
        , typename next4::type
        , BinaryFunction
        > recursion;

 public:
    typedef typename recursion::type type;
};

MPLでは，展開の要因を，使われているC++の実装の要求に合わせて，また， ユーザが値を書き換えることが可能な選択しと共に， この展開テクニックを全てのアルゴリズムで使っている． ⁹ この事実により，ユーザは，通常はもっと単純なアルゴリズムの実装にあたり出会うような， メタプログラミングの限界を超えることができる． 経験によれば，いくつかのコンパイラではループ展開を使えば， メタプログラムインスタンス化の速度は僅かだが遅くなった(多くても10%程度だろう)．