A compile-time binary search tree implementation using C++ templates.

template_search_tree.cpp

#include <iostream>

template <bool condition, typename T, typename F>
struct Conditional {
    typedef F result;
};

template <typename T, typename F>
struct Conditional<true, T, F> {
    typedef T result;
};

template <int a, int b, typename L, typename E, typename G>
struct Compare {
    typedef typename Conditional<
            a < b,
            L,
            typename Conditional<a == b, E, G>::result
    >::result result;
};

template <int k, int v, typename L, typename R>
struct Tree {
    static constexpr int key = k;
    static constexpr int value = v;
    typedef L left;
    typedef R right;
};

template <int k, typename Tree>
struct Search;

template <int k>
struct Search<k, void> {
    typedef void result;
};

template <int k, int ek, int ev, typename L, typename R>
struct Search<k, Tree<ek, ev, L, R>> {
    typedef typename Compare<
            k, ek,
            typename Search<k, L>::result,
            Tree<ek, ev, L, R>,
            typename Search<k, R>::result
    >::result result;
};

template <int k, int v, typename Tree>
struct Insert;

template <int k, int v, int ek, int ev, typename L, typename R>
struct Insert<k, v, Tree<ek, ev, L, R>> {
    typedef typename Compare<
            k, ek,
            Tree<ek, ev, typename Insert<k, v, L>::result, R>,
            Tree<k, v, L, R>,
            Tree<ek, ev, L, typename Insert<k, v, R>::result>
    >::result result;
};

template <int k, int v>
struct Insert<k, v, void> {
    typedef Tree<k, v, void, void> result;
};

template <typename Tree>
struct Count;

template <>
struct Count<void> {
    static const int value = 0;
};

template <int ek, int ev, typename L, typename R>
struct Count<Tree<ek, ev, L, R>> {
    static const int value = 1 + Count<L>::value + Count<R>::value;
};

int main() {
    typedef typename Insert<1, 9, void>::result tree;
    typedef typename Insert<2, 1, tree>::result tree1;
    typedef typename Insert<2, 4, tree1>::result tree2;
    typedef typename Insert<3, 9, tree2>::result tree3;
    typedef typename Insert<2, 16, tree3>::result tree4;

    std::cout << Count<tree4>::value << std::endl;
    std::cout << Search<1, tree4>::result::value << std::endl;
    std::cout << Search<2, tree4>::result::value << std::endl;
    std::cout << Search<3, tree4>::result::value << std::endl;
    std::cout << typeid(Search<1329, tree4>::result).name() << std::endl;
    return 0;
}