How to build a compile-time key/value store?

Question

I have a problem where I need to map an integer at compile time to another integer. Basically, I need the compile-time equivalent of std::map<int,int>. If a key is not found in the map, I'd like to return a default value.

The interface I'd like to use:

template<unsigned int default_value,
         unsigned int key0, unsigned int value0,
         unsigned int key1, unsigned int value1,
         ...>
struct static_map
{
  ...
};

template<unsigned int key, typename StaticMap>
struct lookup
{
  static unsigned int value = ...
};

lookup returns the value associated with key in the StaticMap. If key is not found, then default_value is returned.

In general, the number of key/value pairs will be bounded by some limit > 2. What is the best way to build static_map and lookup?

I should also mention that I'm limited to using C++03 language constructs, so no C++11, and no external library dependencies.

---

Here's the solution I arrived at, inspired by n.m. and DyP's answers below:

#include <iostream>

template<unsigned int k, unsigned int v>
struct key_value
{
  static const unsigned int key = k;
  static const unsigned int value = v;
};


template<typename Head, typename Tail = void>
struct cons
{
  template<unsigned int key, unsigned int default_value>
  struct get
  {
    static const unsigned int value = (key == Head::key) ? (Head::value) : Tail::template get<key,default_value>::value;
  };
};


template<typename Head>
struct cons<Head,void>
{
  template<unsigned int key, unsigned int default_value>
  struct get
  {
    static const unsigned int value = (key == Head::key) ? (Head::value) : default_value;
  };
};


template<unsigned int default_value,
         unsigned int key0, unsigned int value0,
         unsigned int key1, unsigned int value1,
         unsigned int key2, unsigned int value2,
         unsigned int key3, unsigned int value3,
         unsigned int key4, unsigned int value4,
         unsigned int key5, unsigned int value5,
         unsigned int key6, unsigned int value6,
         unsigned int key7, unsigned int value7>
struct static_map
{
  template<unsigned int key>
  struct get
  {
    typedef cons<
      key_value<key0,value0>,
      cons<
        key_value<key1,value1>,
        cons<
          key_value<key2,value2>,
          cons<
            key_value<key3,value3>,
            cons<
              key_value<key4,value4>,
              cons<
                key_value<key5,value5>,
                cons<
                  key_value<key6,value6>,
                  cons<
                    key_value<key7,value7>
                  >
                >
              >
            >
          >
        >
      >
    > impl;

    static const unsigned int value = impl::template get<key,default_value>::value;
  };
};


template<unsigned int key, typename StaticMap>
struct lookup
{
  static const unsigned int value = StaticMap::template get<key>::value;
};


int main()
{
  typedef static_map<13, 
                     0, 0,
                     1, 10,
                     2, 20,
                     3, 30,
                     4, 40,
                     5, 50,
                     6, 60,
                     7, 70
  > my_static_map;

  std::cout << "0 maps to " << lookup<0, my_static_map>::value << std::endl;
  std::cout << "1 maps to " << lookup<1, my_static_map>::value << std::endl;
  std::cout << "2 maps to " << lookup<2, my_static_map>::value << std::endl;
  std::cout << "3 maps to " << lookup<3, my_static_map>::value << std::endl;
  std::cout << "4 maps to " << lookup<4, my_static_map>::value << std::endl;
  std::cout << "5 maps to " << lookup<5, my_static_map>::value << std::endl;
  std::cout << "6 maps to " << lookup<6, my_static_map>::value << std::endl;
  std::cout << "7 maps to " << lookup<7, my_static_map>::value << std::endl;
  std::cout << "100 maps to " << lookup<100, my_static_map>::value << std::endl;

  return 0;
}

Cocktail

possible duplicate of Initializing a static std::map<int, int> in C++ – Division

@user93353: This question is unrelated to the question you've linked. – Cocktail

@DyP: Yes, something like boost's MPL map is what I need. Unfortunately, I can't depend on MPL, so I'd like to understand the implementation. – Cocktail

@JaredHoberock Oops the MPL map works on types. Probably not what you're looking for.. – Zwiebel

Will the limit be fixed or do you need multiple maps with different sizes? – Zwiebel

@DyP: The size of the map should be no greater than 8. – Cocktail

What is default_value supposed to do? – Zwiebel

@dyp: std::integral_constant<int,4> sidesteps the int->type conversion, making MPL viable – Amygdalate

Answer 1

In C++11:

template <int kk, int vv>
struct kv
{
    static const int k = kk, v = vv;
};

template <int dflt, typename...>
struct ct_map;

template <int dflt>
struct ct_map<dflt>
{
    template<int>
    struct get
    {
        static const int val = dflt;
    };
};

template<int dflt, int k, int v, typename... rest>
struct ct_map<dflt, kv<k, v>, rest...>
{
    template<int kk>
    struct get
    {
        static const int val =
            (kk == k) ?
            v :
            ct_map<dflt, rest...>::template get<kk>::val;
    };
};

typedef ct_map<42, kv<10, 20>, kv<11, 21>, kv<23, 7>> mymap;

#include <iostream>
int main()
{
    std::cout << mymap::get<10>::val << std::endl;
    std::cout << mymap::get<11>::val << std::endl;
    std::cout << mymap::get<23>::val << std::endl;
    std::cout << mymap::get<33>::val << std::endl;
}

Lani

Isn't a definition of kv::k and kv::v required (outside the class)? – Zwiebel

@DyP: no, because they are not odr-used. – Lani

How would you throw a compile-time error if a key is not found? – Herzen

@Herzen stick a static assert in the default instantiation, and get rid of the first parameter – Lani

Answer 2

Something like this would work:

template<int Key>
struct StaticMap {
  static const int Value = 0;
};

template<>
struct StaticMap<1> {
  static const int Value = 3;
};

int main()
{
  cout << StaticMap<0>::Value << ", " 
       << StaticMap<1>::Value << ", "
       << StaticMap<2>::Value << endl;
}

0 is the default value, and a key of 1 gives a value of 3. Add additional specializations as needed.

Is this the general idea of what you're looking for? It's not the interface you requested, although preprocessor macros (such as Boost.Preprocessor) could streamline and simplify setting it up.

Vick

Answer 3

You can use template specialization

template <char key>
struct Map;

template <char key>
struct Map { static const int value = -1; }; // not exists node

template <> struct Map< 'A' > { static const int value = 1; }; // 'A' -> 1
template <> struct Map< 'B' > { static const int value = 2; }; // 'B' -> 2
// ....

int lookup = Map<'B'>::value; // = 2

You can avail yourself of some macros to simplify the definition of content.

Capacitor

Answer 4

Essentially based on inheritance: Every map instantiation inherits the lookup types of its base class(es) (-> reduce problem) and defines a lookup for a key.

Edit: improved version base on n.m.'s ideas.

#include <iostream>
#include <cstddef>

template < int t_key, int t_value >
struct ct_int_pair
{
    enum { key = t_key, value = t_value };
};

struct dummy;

template < int default_value,
           typename key_value_pair0,
           typename key_value_pair1 = dummy,
           typename key_value_pair2 = dummy >
struct ct_map
    : ct_map < default_value, key_value_pair1, key_value_pair2, dummy >
{
    typedef ct_map < default_value, key_value_pair1, key_value_pair2, dummy > base;

    // DUMMY required for partial specialization
    template < int key, class DUMMY = dummy >
    struct lookup
    {
        enum { value = base::template lookup < key > :: value };
    };
      template < class DUMMY >
      struct lookup < key_value_pair0::key, DUMMY >
      {
          enum { value = key_value_pair0::value };
      };
};

  template < int default_value >
  struct ct_map < default_value, dummy, dummy, dummy >
  {
      template < int key >
      struct lookup
      {
          enum { value = default_value };
      };
  };


template < int key, typename StaticMap >
struct lookup
{
    enum { value = StaticMap :: template lookup < key > :: value };
};


// example

typedef ct_map < -1,
                 ct_int_pair<21, 42>,
                 ct_int_pair<10, 15> > my_map;

enum
{
     value0 = lookup<21, my_map>::value
   , value1 = lookup<10, my_map>::value
   , value2 = lookup<100, my_map>::value
};

int main()
{
    std::cout << value0 << " : " << value1 << " : " << value2 << std::endl;
}

Zwiebel

Answer 5

Similar question (though asked 2 years later), with my similar answer, but since here's no version for a 17 standard, here's mine:

#include <type_traits>
#include <tuple>

//tag for typenames
template <class T>
struct tag_type
{
    using type = T;
};

//tag for autos
template <auto val>
struct tag_auto
{
    constexpr static decltype(val) value = val;
};

//generic pair
template <typename key_tag, typename val_tag>
struct cexpr_pair
{
    using key = key_tag;
    using value = val_tag;
};

template <class ... cexpr_pairs>
class cexpr_generic_map
{
    template <typename cexpr_tag_key, size_t iter = 0>
    constexpr static auto Find()
    {
        //failed to find by key
        if constexpr (iter == sizeof...(cexpr_pairs))
            //you can substitute void with "tag_auto<default_value>"
            return cexpr_pair<cexpr_tag_key, void>();
        else
        {
            typedef std::tuple_element_t<iter, std::tuple<cexpr_pairs...>> cur_pair;
            if constexpr (std::is_same_v<cexpr_tag_key, cur_pair::key>)
                return cur_pair();
            else 
                return Find<cexpr_tag_key, iter + 1>();
        }
    }

public:

    template <typename tag_key>
    using found_pair = decltype(Find<tag_key>());
};

Usage example:

typedef cexpr_generic_map<
cexpr_pair<tag_auto<0>, tag_auto<4>>,
cexpr_pair<tag_auto<1>, tag_auto<8>>,
cexpr_pair<tag_auto<2>, tag_auto<15>>,
cexpr_pair<tag_auto<4>, tag_auto<0>>,
cexpr_pair<tag_auto<8>, tag_auto<1>>,
cexpr_pair<tag_auto<15>, tag_auto<2>>
> map_inverse;



static_assert(map_inverse::found_pair<tag_auto<0>>::value::value == 4);
static_assert(map_inverse::found_pair<tag_auto<1>>::value::value == 8);
static_assert(map_inverse::found_pair<tag_auto<2>>::value::value == 15);

static_assert(map_inverse::found_pair<tag_auto<4>>::value::value == 0);
static_assert(map_inverse::found_pair<tag_auto<8>>::value::value == 1);
static_assert(map_inverse::found_pair<tag_auto<15>>::value::value == 2);

And a Bonus: Since this map is "generic" either key and value can be a tag of any type or value. Moreover, they may be any type at all. And various cexpr_pairs can be stored alltogether. You just have to somehow enforce it to have unique keys.

Usage example:

struct abc
{
    void func1(int i, double d)
    {
        std::cout << i << '\n' << d << '\n';
    }

    int func2()
    {
        return 9;
    }
};

typedef cexpr_pair<tag_auto<1>, tag_auto<&abc::func1>> pair_func1;
typedef cexpr_pair<tag_auto<2>, tag_auto<&abc::func2>> pair_func2;
typedef cexpr_pair<tag_type<int>, tag_auto<&abc::func2>> int_func2;
typedef cexpr_pair<abc, tag_auto<18>> custom1;
typedef cexpr_pair<int, abc> custom2;

typedef cexpr_generic_map<pair_func1, pair_func2, int_func2, custom1, custom2> map_funcs;

    int main()
{
    abc a;
    (a.*map_funcs::found_pair<tag_auto<1>>::value::value)(6, 3.28);                         // 6 3.28

    std::cout << (a.*map_funcs::found_pair<tag_auto<2>>::value::value)() << std::endl;      // 9
    std::cout << (a.*map_funcs::found_pair<tag_type<int>>::value::value)() << std::endl;    // 9 
    std::cout << map_funcs::found_pair<abc>::value::value << std::endl;                     // 18
    map_funcs::found_pair<int>::value().func1(4, 8.15162342);                               // 4 8.15162342

    std::cin.get();
    return 0;

Capitate