Finding duplicate values of std::map at compile time

Question

I have a template class (BiMap) which is used as a bidirectional map for lookup purposes e.g. an enum value mapped to a std::string equivalent and vice versa.

To achieve this the std::string values must also be unique to prevent duplicate std::string values returning the first found enum key during a search by value lookup.

template<typename Key, typename Value>
class BiMap {
 public:
  explicit BiMap(std::initializer_list<std::pair<Key, Value>> &&items) : bimap_{items.begin(), items.end()} {
    assert(!HasDuplicates(bimap_));
  }

  Key GetKeyFromValue(const Value &value) const {
    auto it = std::find_if(bimap_.begin(), bimap_.end(), [&value](const std::pair<Key, Value> &kvp) {
      return kvp.second == value;
    });
    return (it != bimap_.end() ? it->first : Key());
  }

  Value GetValueFromKey(const Key &key) const {
    auto it = bimap_.find(key);
    return (it != bimap_.end() ? it->second : Value());
  }

 private:
  const std::map<Key, Value> bimap_;
};

I use a function called HasDuplicates to check for any duplicate values:

template<typename Key, typename Value>
bool HasDuplicates(const std::map<Key, Value> &bimap) {
  // Create a map to use the values as keys
  std::map<Value, Key> value_key_map;
  for (auto &kvp : bimap) value_key_map.emplace(kvp.second, kvp.first);

  // If there are no duplicate values then the sizes should be the same
  std::cout << "HasDuplicates: " << std::boolalpha << (value_key_map.size() != bimap.size()) << std::endl;
  return (value_key_map.size() != bimap.size());
}

And I can run the following example code which will indicate at runtime whether there is any duplicate values:

// Test 1: No duplicates
std::cout << "**No duplicates test:**" << std::endl;
const BiMap<std::string, int> bi_map_no_dups({{"foo", 1}, {"bar", 2}, {"foobar", 3}});
std::cout << "foo: " << bi_map_no_dups.GetValueFromKey("foo") << std::endl;
std::cout << "bar: " << bi_map_no_dups.GetValueFromKey("bar") << std::endl;
std::cout << "foobar: " << bi_map_no_dups.GetValueFromKey("foobar") << std::endl;

// Test 2: Duplicates
std::cout << "**Duplicates test:**" << std::endl;
const BiMap<std::string, int> bi_map_dups({{"foo", 1}, {"bar", 2}, {"foobar", 1}});
std::cout << "foo: " << bi_map_dups.GetValueFromKey("foo") << std::endl;
std::cout << "bar: " << bi_map_dups.GetValueFromKey("bar") << std::endl;
std::cout << "foobar: " << bi_map_dups.GetValueFromKey("foobar") << std::endl;

The output of this would be:

**No duplicates test:**
HasDuplicates: false
foo: 1
bar: 2
foobar: 3
**Duplicates test:**
HasDuplicates: true
main.cpp:22: BiMap<Key, Value>::BiMap(std::initializer_list<std::pair<_T1, _T2> >&&) [with Key = std::basic_string<char>; Value = int]: Assertion `!HasDuplicates(bimap_)' failed.

A working example of the above code can be found here.

The Question:

How can I evaluate whether the std::map has duplicate values at compile time?

What I've tried:

I've already tried to implement the constexpr template function like here:

template <typename K, typename V> constexpr bool has_duplicates(const std::map<K,V> *map)
{
    std::map<V,K> value_key_map;
    for(auto &kvp : map) value_key_map.emplace(map->second,map->first);
    return map->size() == value_key_map.size();
}

int main() {
 // Cannot get this part to work
 constexpr std::map<std::string, int> bimap({{"foo", 1}, {"bar", 2}, {"foobar", 1}});
 static_assert(!has_duplicates(&bimap));

 return 0;
}

Note: I'm using C++11 where I cannot yet declare local variables and loops inside the constexpr function and should thus revert to recursion as seen here. But, for this example I'm happy if I can find a suitable solution with C++14's constexpr features and I'll get a recursive version later on (if possible).

Answer 1

How can I evaluate whether the std::map has duplicate values at compile time?

You can't. std::map() isn't usable at compile time.

You could instead use https://github.com/serge-sans-paille/frozen or https://github.com/mapbox/eternal to make that check (or some other constexpr structure).

The other way (if you want to stay at the C++11 level) is to build a template metaprogramming based map, like in this answer.

Answer 2

With the help of the comment section, I was able to formulate a suitable solution to my problem.

Important: std::map is not constexpr and can't be used to evaluate its contents at compile time.

However, you can use std::array<std::pair<const K, V>, N> to assist in evaluating the contents at compile time from C++14 as follows:

template<typename K, typename T, size_t N>
constexpr bool has_duplicates(const std::array<std::pair<K, T>, N> *arr) {
  for (int i = 0; i < N - 1; i++) {
    for (int j = i + 1; j < N; j++) {
      if (compare_equal((*arr)[i].second,(*arr)[j].second) || 
          compare_equal((*arr)[i].first, (*arr)[j].first)) return true;
    }
  }
  return false;
}

with usage:

constexpr std::array<std::pair<int, const char *>, 3> arrd{{ {1, "foobar"},
                                                             {2, "bar"},
                                                             {3, "foobar"}}};
static_assert(!has_duplicates(&arrd), "Duplicates Found!");

and you need the following additional comparison functions:

template<typename A, typename B>
constexpr bool compare_equal(A a, B b) {
    return a == b;
}

template <>
constexpr bool compare_equal(const char * a, const char * b) {
    return *a == *b && (*a == '\0' || compare_equal(a + 1, b + 1));
}

For C++11 support you need to change the has_duplicates function to a recursive implementation. Here is a fully working example of both versions.

You can thus use this in your class to check for duplicate values at compile time.