Home > プログラミング > テンプレートでリストとか

テンプレートでリストとか

八王子からの帰り,C++のテンプレートでコンパイル時にリストを使った計算をさせようとテンプレートでリストを表現する方法を考えていた.結論としては,値を直接使わずに,全てを型の上で処理してしまえばいい.ためしにリストを作って表示,foldr, map を書いてみた.まあ,int 限定にしているけど.一般化は容易でしょう.

#include <iostream>
using namespace std;
 
#define cons(x, y)      Cons< Int< x >, y >
#define nil             Nil
 
// nil  or []
struct Nil {};
 
// cons h t  or h:t
template <typename H, typename T>
struct Cons {
    typedef H head;
    typedef T tail;
};
 
// element of lists
template<int n>
struct Int{
    enum {val = n};
    static void print() { cout << n; }
};
 
// printer
template <typename L>
struct ListPrinter {
    static void print(){
        cout << '[';
        L::head::print();
        ListPrinter<typename L::tail>::print2();
        cout << ']';
    }
    static void print2(){
        cout << ',';
        L::head::print();
        ListPrinter<typename L::tail>::print2();
    }
};
template <>
struct ListPrinter<Nil> {
    static void print(){
        cout << '[' << ']';
    }
    static void print2(){
    }
};
 
// foldr function
// foldr f e [] = e
// foldr f e (h:t) = f h (foldr f e t)
// cons case:
template<template<typename,typename> class F, typename E, typename L >
struct Foldr{
    typedef typename F<typename L::head, typename  Foldr<F,E,typename L::tail>::val >::val val;
};
// nil case:
template<template<typename,typename> class F, typename E>
struct Foldr<F,E,Nil>{
    typedef E val;
};
 
// map function
// map f [] = []
// map f (h:t) = f h:(map f t)
// cons case:
template<template<typename> class F, typename L >
struct Map{
    typedef Cons< typename F<typename L::head>::val , typename Map<F, typename L::tail>::val> val;
};
// nil case:
template<template<typename> class F>
struct Map<F,Nil>{
    typedef Nil val;
};
 
//addition operator
template <typename X, typename Y>
struct Add {
    typedef Int<X::val + Y::val> val;
};
 
// zero
typedef Int<0> Zero;
 
//douoblring operator
template <typename X>
struct Double{
    typedef Int<X::val + X::val> val;
};
 
int main(int argc, char *argv[])
{
    typedef cons(4, cons(3, cons(2, cons(1, nil)))) l;
    typedef cons(5, l) l2;
    ListPrinter< l >::print();  cout << endl;
    ListPrinter< l2 >::print(); cout << endl;
     typedef Foldr<Add, Zero, l2>::val sum;
    sum::print(); cout << endl;
     typedef Map<Double, l2>::val l3;
    ListPrinter< l3 >::print(); cout << endl;
}

とまあ,考えてみたわけだけど,あとに別の用件で google で検索かけたらThe Boost C++ Metaprogramming Libraryとかいうものを見つけてしまった.boost に含まれいてるらしいが,上で考えたのと同じで全てを型で扱ってコンパイル時計算をしているらしい.いやぁ,やっぱ同じことを考える人はいるもんだなぁ.でも,こいつにはサイズに制限があるらしい(上限を上げるようにすればいいんだけど).ということで,上の Cons/Nil は制限一切無いので捨てたもんじゃない(はず?).

★下記に2つの英単語をスペースで区切って入力してください

Home > プログラミング > テンプレートでリストとか

Search
Feeds

Page Top