Skip to content

Instantly share code, notes, and snippets.

@ldionne
Last active August 8, 2023 10:17
Show Gist options
  • Save ldionne/f7ff609f00dc7025a213 to your computer and use it in GitHub Desktop.
Save ldionne/f7ff609f00dc7025a213 to your computer and use it in GitHub Desktop.
Toy implementation of a static constexpr map
#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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment