Compile Time Constant Map

I have implemented this compile time map as a way of learning templates and constexpr classes:

```
template
class Element {
public:
const K key;
const V value;
constexpr Element(const K& key, const V& value) :
key(key), value(value) {};
};

template
constexpr Element El(const K& key, const V& value) {
return Element(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 ConstMap {
const Element el;
const ConstMap 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
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(),

class Element looks an awful lot like std::pair; I wonder if you could just use std::pair, to eliminate some lines of code.

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 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();
}

Rather than all this rigmarole, why not just throw? That's equally non-constexpr, and has the benefit of not (segfaulting|returning a wrong answer) when you're not in a constexpr context. Thus:

constexpr bool must_contain(const K& key) const {
  return ContainsUnchecked(key) ? true : throw "oops";
}
constexpr bool must_not_contain_duplicates() const {
  return AllAreUnique() ? true : throw "oops";
}

Check the sizeof(ConstMap) before and after getting rid of the (non-static) const V *null, by the way!

As einpoklum says, if you really want to make your code shorter and simpler and you already know that what's making it long and complicated is recursive templates, then you should try to eliminate those recursive templates! (I have a blog post on the subject.) In this case it's easy because the Standard Library already gives us std::array:

It would end up looking something like this (UNTESTED CODE).

template
class ConstMap {
  std::array> data_;

public:
  template
  constexpr ConstMap(Elements... elements) : data_{std::move(elements)...} {}

  constexpr bool AllAreUnique() const {
      // This could easily be 2x faster but I am lazy
      for (auto&& a : data_) {
          for (auto&& b : data_) {
              if (&a != &b && a.first == b.first) return false;
          }
      }
      return true;
  }
  constexpr bool Contains(const K& key) const {
      return std::find_if(data_.begin(), data_.end(), [](const auto& elt){
          return elt.first == key;
      }) != data_.end();
  }
  constexpr const V& Get(const K& key) const {
      auto it = std::find_if(data_.begin(), data_.end(), [](const auto& elt){
          return elt.first == key;
      });
      if (it != data_.end()) return it->second;
      throw "not found";
  }
};

Incidentally, I don't see why you bother to check must_not_contain_duplicates() over and over. Surely you should just check that one time in the constructor, if ever! And in fact there's no real reason your thing couldn't hold duplicates; there's no particular invariant that would break, is there? So just let go and let it.

But if you want to enforce that invariant, then you'd do it like this:

template
  constexpr ConstMap(Elements... elements) : data_{std::move(elements)...} {
      if (not AllAreUnique()) throw "oops";
  }

Speaking of invariants... what you've made here is not a map in any meaningful sense. At best it's a flatmap, and honestly I'd just tell it like it is: it's an array.

A map would support faster-than-O(N) lookup: either binary search (that being a TreeMap in Javaspeak, or a std::map in C++) or by hashing (that being a HashMap in Javaspeak, or std::unordered_map in C++). If all it has is linear search, then it's an unsorted array...

...or std::array in C++. Not coincidentally, what we ended up with was a really thin wrapper around std::array!

StackExchange Code Review Q#77925, answer score: 3