How is boost::mpl::map (or set) implemented?

Question

I would like to know how to implement a template metaprogramming structure like boost::mpl::map, that is a structure that supports constant-time insertion and removal of elements, and testing for membership.

It is hard to find real implementation in boost headers behind all of workarounds, macros and generated code.

Answer 1

Basically, through clever use of overloading. Let's say you want to to construct a map with just two "elements": T --> U and X --> Y. If we flatten out all the inheritance hierarchy, we will end up with a type that looks something like this:

struct specific_mpl_map {

    U get(T );
    Y get(X );

    template <typename AnythingElse>
    void_ get(AnythingElse );

    pair<T, U> get(int_<0> );
    pair<X, Y> get(int_<1> );

    using size = int_<2>;
};

That way, a lookup for some key K would just be decltype(map.get(K{})), which is compile-time constant - you don't need to walk through all the pairs to figure out there is a get(K). And you also have a mechanism for iterating in order, via just calling get(int_<i>{}). Any insert/delete just creates a new map type with all the new expected get() functions.

This isn't exactly what the code looks like, really each get is in its own type and the whole thing is inherited linearly up for each pair that you add to the map, but this is approximately what the end-goal is.

It helps if you compile with -E and then just take a look at what gets dumped out. The key type is something called m_item, which defines static functions for each type of lookup. So if we want to do lookup by key, there is:

template< typename Key, typename T, typename Base >
struct m_item
    : Base // Base is the rest of the map less this element
{
    // some typedefs

    static aux::type_wrapper<T> value_by_key_(m_item const&, 
                                              aux::type_wrapper<Key>*); 
    using Base::value_by_key_;
};

Which at uses thusly:

template< typename Map, typename Key >
struct m_at
{
    typedef aux::type_wrapper<Key> key_;
    typedef __typeof__( Map::value_by_key_( 
                        aux::ptr_to_ref(static_cast<Map*>(0)), 
                        static_cast<key_*>(0) )

          ) type;
};

Where the base empty map also defines:

template< typename Dummy = na > struct map0
{
    static aux::type_wrapper<void_> value_by_key_(map0<> const&, 
                                                  void const volatile*);
};