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?

The initialization of the map you show is wrong, you should switch the integers and the strings. — Some programmer dude
– Some programmer dude, Commented Dec 3, 2019 at 11:18
Sounds a bit like an X-Y problem. Do you want to get fast reverse-hashes for known set of values? Do you really need it? What is your actual problem? — Denis Sheremet
– Denis Sheremet, Commented Dec 3, 2019 at 11:21
I've edited my question accordingly. Let me know if anything is still unclear. — NaCl
– NaCl, Commented Dec 3, 2019 at 13:26

Barry · Accepted Answer · 2019-12-03 14:28:51Z

3

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.

edited Dec 3, 2019 at 14:28

answered Dec 3, 2019 at 14:00

Barry

312k32 gold badges734 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

NaCl Over a year ago

The first solution is way too cumbersome. Unfortunately, the second solution has the drawback that the user can't partially specialize map. This can be solved with a separate make_map function.

Barry Over a year ago

@NaCl Is that a drawback? And why do you think they can't?

Barry Over a year ago

@NaCl Also please don't edit people's answers like that. That's a significant change in direction.

NaCl Over a year ago

in a sense, since you might want to store size_t's in the map, which, to my knowledge, has no literal, so it might be deduced to size_t, but can also be something different, i.e. just unsigned int

NaCl · Accepted Answer · 2019-12-03 14:39:20Z

@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"} });

Collectives™ on Stack Overflow

Compile-Time Lookup-Table with initializer_list

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related