C++实现编译期二分查找树

先上Haskell代码

data Tree a = EmptyTree | Node{
    value   ::a,
    left    :: Tree a,
    right   :: Tree a
}deriving (Show,Read,Eq)
              
singleton :: a->Tree a
singleton x =Node x EmptyTree EmptyTree

treeInsert ::(Ord a) =>a -> Tree a ->Tree a
treeInsert x s =singleton x
treeInsert x (Node a left right)
    |x==a = Node x left right
    |x< a = Node a (treeInsert x left) right
    |x> a = Node a left (treeInsert x right)


findTree::(Ord a) =>a->Tree a->Bool
findTree a EmptyTree = False
findTree a (Node x left right) 
    | a==x=True
    | a<x =findTree a left
    | a>x =findTree a right


listToTree :: (Ord a)=> [a]->Tree a

listToTree [] =EmptyTree
listToTree (x:xs) =treeInsert x (listToTree xs)

然后是C++代码

struct EmptyTree{};

template<int V,typename L,typename R>
struct Tree{
    static const int value=V;
    using Left=L;
    using Right=R;
};

template<int V>
struct Singleton{
    
    using Type=Tree<V, EmptyTree, EmptyTree>;
};

template<int V,typename Tree>
struct TreeInsert;

template<int V>
struct TreeInsert<V,EmptyTree>{
    using Type=typename Singleton<V>::Type;
};

template<int V,int TV,typename L,typename R>
struct TreeInsert<V,Tree<TV, L, R>>{
    using Type=typename conditional<V==TV,Tree<TV, L, R>,
    typename conditional< V<TV,Tree<TV,typename TreeInsert<V,L>::Type,R>,Tree<TV,L,typename TreeInsert<V,R>::Type>>::type> ::type;
};
template<int V,typename T>
struct FindTree;

template<int V>
struct FindTree<V,EmptyTree>{
    static const bool value=false;
};

template<int V,int TV,typename L,typename R>
struct FindTree<V,Tree<TV,L,R>>{
    static const bool value=conditional<V==TV,true_type,
    typename conditional< V<TV, FindTree<V,L>,FindTree<V,R> >::type>::type::value;
};

template<int ...Args>
struct CreateTree;

template<int T>
struct CreateTree<T>{
    using Type=typename Singleton<T>::Type;
};
template<int T,int...TS>
struct CreateTree<T,TS...>{
    using Type=typename TreeInsert<T, typename CreateTree<TS...>::Type>::Type;
};

测试代码

using t=CreateTree<3,2,4,10,1,6>::Type;
    cout<<FindTree<1, t>::value<<endl;
    cout<<FindTree<2, t>::value<<endl;
    cout<<FindTree<3, t>::value<<endl;
    cout<<FindTree<4, t>::value<<endl;
    cout<<FindTree<5, t>::value<<endl;
    cout<<FindTree<6, t>::value<<endl;
    cout<<FindTree<7, t>::value<<endl;
    cout<<FindTree<8, t>::value<<endl;
    cout<<FindTree<9, t>::value<<endl;
    cout<<FindTree<10, t>::value<<endl;

测试结果

true
true
true
true
false
true
false
false
false
true

结论

C++代码比haskell长好多，也特别难看，C++真垃圾。