association list for types in C++

alist.cc

#include <type_traits>
#include <utility>

namespace association_list {
template<typename... Ps>
struct alist {};

namespace dispatch {
template<typename A, typename K>
struct lookup {};

template<typename K, typename V, typename S>
struct lookup<alist<std::pair<K, V>>, S> {
    typedef typename std::conditional<std::is_same<K, S>::value,
                                      V,
                                      void>::type type;
};

template<typename K, typename V, typename... Ps, typename S>
struct lookup<alist<std::pair<K, V>, Ps...>, S> {
    typedef typename std::conditional<std::is_same<K, S>::value,
                                      V,
                                      typename lookup<alist<Ps...>,
                                                      S>::type>::type type;
};

template<typename A, typename K>
struct contains {};

template<typename S>
struct contains<alist<>, S> {
    constexpr static bool value = false;
};

template<typename K, typename V, typename S>
struct contains<alist<std::pair<K, V>>, S> {
    constexpr static bool value = std::is_same<K, S>::value;
};

template<typename K, typename V, typename... Ps, typename S>
struct contains<alist<std::pair<K, V>, Ps...>, S> {
    constexpr static bool value =
        std::is_same<K, S>::value || contains<alist<Ps...>, S>::value;
};

template<typename A, typename K, typename V>
struct insert {};

template<typename Ik, typename Iv>
struct insert<alist<>, Ik, Iv> {
    typedef alist<std::pair<Ik, Iv>> type;
};

template<typename K, typename V, typename Ik, typename Iv>
struct insert<alist<std::pair<K, V>>, Ik, Iv> {
    typedef typename std::conditional<std::is_same<K, Ik>::value,
                                      alist<std::pair<Ik, Iv>>,
                                      alist<std::pair<K, V>,
                                            std::pair<Ik, Iv>>>::type type;
};

namespace {
template<typename P, typename A>
struct cons {};

template<typename P, typename... Ps>
struct cons<P, alist<Ps...>> {
    typedef alist<P, Ps...> type;
};
}

template<typename K, typename V, typename... Ps, typename Ik, typename Iv>
struct insert<alist<std::pair<K, V>, Ps...>, Ik, Iv> {
private:
    typedef typename std::conditional<std::is_same<K, Ik>::value,
                                      alist<std::pair<Ik, Iv>, Ps...>,
                                      typename cons<std::pair<K, V>,
                                                    typename insert<alist<Ps...>,
                                                                    Ik,
                                                                    Iv>::type>::type>::type type;
};
}

template<typename A, typename K>
using lookup = typename dispatch::lookup<A, K>::type;

template<typename A, typename K>
auto contains = dispatch::contains<A, K>::value;

template<typename A, typename K, typename V>
using insert = typename dispatch::insert<A, K, V>::type;
}

#include <cstdint>
#include <iostream>

template<std::int64_t value>
using int_constant = std::integral_constant<std::int64_t, value>;


int main() {
    using namespace association_list;

    using a = alist<>;
    using key = int_constant<1>;
    using value = int_constant<-1>;
    using inserted = insert<a, key, value>;

    std::cout << "key in a: " << contains<a, key> << '\n'
              << "key in inserted: " << contains<inserted, key> << '\n';

    using new_key = int_constant<2>;
    using new_value = int_constant<-2>;
    using two_keys = insert<inserted, new_key, new_value>;

    std::cout << "two_keys[1]: " << lookup<two_keys, key>{}() << '\n'
              << "two_keys[2]: " << lookup<two_keys, new_key>{}() << '\n';
}

out

$ ./a.out 
key in a: 0
key in inserted: 1
two_keys[1]: -1
two_keys[2]: -2