Compile-Time Lookup-Table with initializer_list

Question

Suppose you have some hash values and want to map them to their respective strings at compile time. Ideally, I'd love to be able to write something along the lines of:

constexpr std::map<int, std::string> map = { {1, "1"}, {2 ,"2"} };

Unfortunately, this is neither possible in C++17 nor C++2a. Nevertheless, I tried emulating this with std::array, but can't get the size of the initializer list at compile time to actually set the type of the array correctly without explicitly specifying the size. Here is my mockup:

template<typename T0, typename T1>
struct cxpair
{
    using first_type = T0;
    using second_type = T1;

    // interestingly, we can't just = default for some reason...
    constexpr cxpair()
        : first(), second()
    {  }

    constexpr cxpair(first_type&& first, second_type&& second)
        : first(first), second(second)
    {  }

    // std::pair doesn't have these as constexpr
    constexpr cxpair& operator=(cxpair<T0, T1>&& other)
    { first = other.first; second = other.second; return *this; }

    constexpr cxpair& operator=(const cxpair<T0, T1>& other)
    { first = other.first; second = other.second; return *this; }

    T0 first;
    T1 second;
};

template<typename Key, typename Value, std::size_t Size = 2>
struct map
{
    using key_type = Key;
    using mapped_type = Value;
    using value_type = cxpair<Key, Value>;

    constexpr map(std::initializer_list<value_type> list)
        : map(list.begin(), list.end())
    {  }

    template<typename Itr>
    constexpr map(Itr begin, const Itr &end)
    {
        std::size_t size = 0;
        while (begin != end) {
            if (size >= Size) {
                throw std::range_error("Index past end of internal data size");
            } else {
                auto& v = data[size++];
                v = std::move(*begin);
            }
            ++begin;
        }
    }

    // ... useful utility methods omitted

private:
    std::array<value_type, Size> data;
    // for the utilities, it makes sense to also have a size member, omitted for brevity
};

Now, if you just do it with plain std::array things work out of the box:

constexpr std::array<cxpair<int, std::string_view>, 2> mapp = {{ {1, "1"}, {2, "2"} }};

// even with plain pair
constexpr std::array<std::pair<int, std::string_view>, 2> mapp = {{ {1, "1"}, {2, "2"} }};

Unfortunately, we have to explicitly give the size of the array as second template argument. This is exactly what I want to avoid. For this, I tried building the map you see up there. With this buddy we can write stuff such as:

constexpr map<int, std::string_view> mapq = { {1, "1"} };
constexpr map<int, std::string_view> mapq = { {1, "1"}, {2, "2"} };

Unfortunately, as soon as we exceed the magic Size constant in the map, we get an error, so we need to give the size explicitly:

//// I want this to work without additional shenanigans:
//constexpr map<int, std::string_view> mapq = { {1, "1"}, {2, "2"}, {3, "3"} };
constexpr map<int, std::string_view, 3> mapq = { {1, "1"}, {2, "2"}, {3, "3"} };

Sure, as soon as you throw in the constexpr scope, you get a compile error and could just tweak the magic constant explicitly. However, this is an implementation detail I'd like to hide. The user should not need to deal with these low-level details, this is stuff the compiler should infer.

Unfortunately, I don't see a solution with the exact syntax map = { ... }. I don't even see light for things like constexpr auto map = make_map({ ... });. Besides, this is a different API from the runtime-stuff, which I'd like to avoid to increase ease of use.

So, is it somehow possible to infer this size parameter from an initializer list at compile time?

Answer 1

@Barry's answer pinpointed me in the right direction. Always explicitly listing pair in the list is undesirable. Moreover, I want to be able to partially specialize the template argument list of map. Consider the following example:

// for the sake of the example, suppose this works
constexpr map n({{1, "1"}, {2, "2"}});
              // -> decltype(n) == map<int, const char*, 2>

// the following won't work
constexpr map<std::size_t, const char*> m({{1, "1"}, {2, "2"}});

However, perhaps the user wants that the map contains std::size_t as key, which does not have a literal. i.e. s/he would have to define a user-defined literal just to do that.

We can resolve this by offloading the work to a make_map function, allowing us to partially specialize the map:

// deduction guide for map's array constructor
template<class Key, class Value, std::size_t Size>
map(cxpair<Key, Value>(&&)[Size]) -> map<Key, Value, Size>;

// make_map builds the map
template<typename Key, typename Value, std::size_t Size>
constexpr auto make_map(cxpair<Key, Value>(&&m)[Size]) -> map<Key, Value, Size>
{ return map<Key, Value, Size>(std::begin(m), std::end(m)); }

// allowing us to do:
constexpr auto mapr = make_map<int, std::string_view>({ {1, "1"},
                                                        {2, "2"},
                                                        {3, "3"} });

Answer 2

std::array has a deduction guide:

template <class T, class... U>
array(T, U...) -> array<T, 1 + sizeof...(U)>;

which lets you write:

// ok, a is array<int, 4>
constexpr std::array a = {1, 2, 3, 4};

We can follow the same principle and add a deduction guide for map like:

template <typename Key, typename Value, std::size_t Size>
struct map {
    constexpr map(std::initializer_list<std::pair<Key const, Value>>) { }
};

template <class T, class... U>
map(T, U...) -> map<typename T::first_type, typename T::second_type, sizeof...(U)+1>;

Which allows:

// ok, m is map<int, int, 3>
constexpr map m = {std::pair{1, 1}, std::pair{1, 2}, std::pair{2, 3}};

Unfortunately, this approach requires naming each type in the initializer list - you can't just write {1, 2} even after you wrote pair{1, 1}.

---

A different way of doing it is to take an rvalue array as an argument:

template <typename Key, typename Value, std::size_t Size>
struct map {
    constexpr map(std::pair<Key, Value>(&&)[Size]) { }
};

Which avoids having to write a deduction guide and lets you only have to write the type on the first one, at the cost of an extra pair of braces or parens:

// ok, n is map<int, int, 4>
constexpr map n{{std::pair{1, 1}, {1, 2}, {2, 3}, {3, 4}}};

// same
constexpr map n({std::pair{1, 1}, {1, 2}, {2, 3}, {3, 4}});

Note that the array is of pair<Key, Value> and not pair<Key const, Value> - which allows writing just pair{1, 1}. Since you're writing a constexpr map anyway, this distinction probably doesn't matter.