Compile Time Constant Map

Question

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?

1. Eliminate the template parameter
2. Eliminate the need for a second specialization

Issues that prevent this:

• The rest and el variables need to not exist or be of different types when size == 0.

I'd also love to hear any suggestions you have for cleaning up the code in general.

Answer 1

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<int,int,10>) 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 K, class V, int size>
class ConstMap {
  std::array<std::pair<K, V>> data_;

public:
  template<class... Elements>
  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<class... Elements>
  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!