I have implemented this compile time map as a way of learning templates and constexpr
classes:
template<class K, class V>
class Element {
public:
const K key;
const V value;
constexpr Element(const K& key, const V& value) :
key(key), value(value) {};
};
template<class K, class V>
constexpr Element<K, V> El(const K& key, const V& value) {
return Element<K, V>(key, value);
}
void test_element() {
static_assert(El(1,2).key == 1, "El wrong!");
static_assert(El(1,2).value == 2, "El wrong!");
static_assert(El(2,3).key == 2, "El wrong!");
static_assert(El(3,4).value == 4, "El wrong!");
}
template<class K, class V, int size>
class ConstMap {
const Element<K, V> el;
const ConstMap<K, V, size - 1> rest;
const V* null = nullptr;
// These two functions cause a compilation error when evaluated in a constexpr context.
const V& DUPLICATE_KEYS_PRESENT() const { return *null ; }
const bool DOES_NOT_CONTAIN() const { return true; }
constexpr bool AllAreUnique() const {
return IsUniqueUnchecked() && rest.AllAreUnique();
}
constexpr bool IsUniqueUnchecked() const {
return !rest.ContainsUnchecked(el.key);
}
constexpr int SizeUnchecked() const {
return size;
}
constexpr bool ContainsUnchecked(const K& key) const {
return el.key == key || rest.ContainsUnchecked(key);
}
constexpr const V& GetUnchecked(const K& key) const {
return el.key == key ? el.value : rest.GetUnchecked(key);
}
constexpr bool must_contain(const K& key) const {
return ContainsUnchecked(key) ? true : DOES_NOT_CONTAIN();
}
constexpr bool must_not_contain_duplicates() const {
return AllAreUnique() ? true : DUPLICATE_KEYS_PRESENT();
}
public:
template<class Head, class... Rest>
constexpr ConstMap(Head head, Rest... rest) : el(head), rest(rest...) {}
constexpr int Size() const {
return must_not_contain_duplicates(), SizeUnchecked();
}
constexpr bool Contains(const K& key) const {
return must_not_contain_duplicates(), ContainsUnchecked(key);
}
constexpr const V& Get(const K& key) const {
return must_not_contain_duplicates(), must_contain(key), GetUnchecked(key);
}
friend class ConstMap<K, V, size + 1>;
};
template<class K, class V>
class ConstMap<K, V, 0> {
const V* null = nullptr;
// Same as above. Compilation error.
const V& CALLED_GET_ON_NONEXISTENT_KEY() const { return *null; }
constexpr bool AllAreUnique() const {
return IsUniqueUnchecked();
}
constexpr bool IsUniqueUnchecked() const {
return true;
}
constexpr int SizeUnchecked() const {
return 0;
}
constexpr bool ContainsUnchecked(const K& key) const {
return false;
}
constexpr const V& GetUnchecked(const K& key) const {
return CALLED_GET_ON_NONEXISTENT_KEY();
}
public:
constexpr ConstMap() {}
constexpr int Size() const {
return SizeUnchecked();
}
constexpr bool Contains(const K& key) const {
return ContainsUnchecked(key);
}
constexpr const V& Get(const K& key) const {
return GetUnchecked(key);
}
friend class ConstMap<K, V, 1>;
};
template<class K, class V, class... Args>
constexpr ConstMap<K, V, sizeof...(Args)> BuildConstMap(Args... args) {
return ConstMap<K, V, sizeof...(args)>(args...);
}
void test_const_map() {
static_assert(BuildConstMap<int, int>().Size() == 0, "Map size wrong!");
static_assert(BuildConstMap<int, int>(El(2,3)).Size() == 1, "Map size wrong!");
static_assert(BuildConstMap<int, int>(El(1,2),El(2,3)).Size() == 2, "Map size wrong!");
static_assert(!BuildConstMap<int, int>().Contains(2), "Contains wrong!");
static_assert(BuildConstMap<int, int>(El(1,2),El(2,3)).Contains(2), "Contains wrong!");
static_assert(BuildConstMap<int, int>(El(1,2),El(2,3)).Contains(1), "Contains wrong!");
static_assert(!BuildConstMap<int, int>(El(1,2),El(2,3)).Contains(3), "Contains wrong!");
static_assert(BuildConstMap<int, int>(El(1,2),El(2,3)).Get(1) == 2, "Get wrong!");
static_assert(BuildConstMap<int, int>(El(1,2),El(2,3)).Get(2) == 3, "Get wrong!");
// These cause a compilation error:
// Get on nonexistent element.
// static_assert(BuildConstMap<int, int>(El(1,2),El(2,3)).Get(3) == 4, "Get wrong!");
// Get on nonexistent element in empty map.
// static_assert(BuildConstMap<int, int>().Get(3) == 4, "Get wrong!");
// Get with duplicate elements.
// static_assert(BuildConstMap<int, int>(El(1,2),El(2,3),El(2,5)).Get(2) == 4, "Duplicate detection wrong!");
// static_assert(BuildConstMap<int, int>(El(1,2),El(2,3),El(2,5)).Size() == 4, "Duplicate detection wrong!");
// static_assert(BuildConstMap<int, int>(El(1,2),El(2,3),El(2,5)).Contains(2) == 4, "Duplicate detection wrong!");
}
constexpr auto cmap = BuildConstMap<int, int>(El(0,0),
El(1,2),
El(2,3));
int main() {
test_element();
test_const_map();
return cmap.Get(0);
}
I really dislike that I need two specializations, which necessitate a size template parameter. Is there some way to do any of these things?
- Eliminate the template parameter
- Eliminate the need for a second specialization
Issues that prevent this:
- The
rest
andel
variables need to not exist or be of different types whensize == 0
.
I'd also love to hear any suggestions you have for cleaning up the code in general.
std::array
of key-value pairs? \$\endgroup\$