Toy implementation of a static constexpr map

static_map.cpp

#include <algorithm>
#include <array>
#include <cassert>
#include <experimental/string_view>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <utility>


//////////////////////////////////////////////////////////////////////////////
// Notes:
// 1. The map is not actually constexpr. However, it could become constexpr
//    trivially by implementing functions like std::find_if as constexpr
//    functions. In other words, there is no fundamental limitation for
//    making this map actually constexpr, only laziness.
//
// 2. This implementation does require default-constructing the keys and the
//    values beforehand, which is annoying. We could use raw storage instead
//    of std::array, and then use in-place new instead of assignment in
//    `insert_impl`, but in-place new can't appear in a constant expression.
//    It might be possible to pre-compute the end-index of each key before
//    doing anything, and then initialize each (key, value) pair at the right
//    index at once. That would be more work, though.
//////////////////////////////////////////////////////////////////////////////

template <typename Key, typename Value, std::size_t N>
struct map {
    std::array<std::pair<Key, Value>, N> storage_;

private:
    constexpr void insert_impl(std::pair<Key, Value> const& pair,
                                std::array<bool, N>& initialized)
    {
        std::size_t hash = std::hash<Key>{}(pair.first);
        auto start = std::next(initialized.begin(), hash % N);
        auto it = std::find(start, initialized.end(), false);

        if (it != initialized.end()) {
            std::size_t index = std::distance(initialized.begin(), it);
            storage_[index] = pair;
            initialized[index] = true;
            return;
        }

        it = std::find(initialized.begin(), start, false);
        if (it != start) {
            std::size_t index = std::distance(initialized.begin(), it);
            storage_[index] = pair;
            initialized[index] = true;
            return;
        }

        assert(false && "should never be reached");
    }

public:
    template <typename ...K, typename ...V>
    constexpr explicit map(std::pair<K, V> const& ...pairs) {
        std::array<bool, N> initialized{}; // all false at the beginning
        int expand[] = {(insert_impl(pairs, initialized), int{})...};
        (void)expand;
    }

    constexpr Value const& at(Key const& key) const {
        std::size_t hash = std::hash<Key>{}(key);
        auto start = std::next(storage_.begin(), hash % N);
        auto it = std::find_if(start, storage_.end(), [&](auto const& p) {
            return p.first == key;
        });

        if (it != storage_.end())
            return it->second;

        it = std::find_if(storage_.begin(), start, [&](auto const& p) {
            return p.first == key;
        });
        if (it != start)
            return it->second;
        else
            throw std::out_of_range{"no such key in the map"};
    }
};

template <bool ...b>
struct and_
    : std::is_same<and_<b...>, and_<(b, true)...>>
{ };

template <typename Key, typename Value, typename ...Pairs>
constexpr auto make_map(Pairs const& ...pairs) {
    static_assert(and_<std::is_same<Key, typename Pairs::first_type>::value...>::value,
        "make_map requires all keys to have the same type");

    static_assert(and_<std::is_same<Value, typename Pairs::second_type>::value...>::value,
        "make_map requires all values to have the same type");

    return map<Key, Value, sizeof...(Pairs)>{pairs...};
}



//////////////////////////////////////////////////////////////////////////////

enum class weekday { sunday, monday, tuesday, wednesday, thursday, friday, saturday };

#define STRING_VIEW(str) std::experimental::string_view{ str, sizeof(str)-1 }

int main() {
    auto map = make_map<std::experimental::string_view, weekday>(
        std::make_pair( STRING_VIEW("sunday"),    weekday::sunday ),
        std::make_pair( STRING_VIEW("monday"),    weekday::monday ),
        std::make_pair( STRING_VIEW("tuesday"),   weekday::tuesday ),
        std::make_pair( STRING_VIEW("wednesday"), weekday::wednesday ),
        std::make_pair( STRING_VIEW("thursday"),  weekday::thursday ),
        std::make_pair( STRING_VIEW("friday"),    weekday::friday ),
        std::make_pair( STRING_VIEW("saturday"),  weekday::saturday)
    );

    assert(map.at("sunday") == weekday::sunday);
    assert(map.at("monday") == weekday::monday);
    assert(map.at("tuesday") == weekday::tuesday);
    assert(map.at("wednesday") == weekday::wednesday);
    assert(map.at("thursday") == weekday::thursday);
    assert(map.at("friday") == weekday::friday);
    assert(map.at("saturday") == weekday::saturday);
}