Template distinguishing between maps and sets

Question

In creating a code common for set, unordered_set, map, and unordered_map, I need the few methods, where the handling is actually different. My problem is getting the compiler to deduce, which implementation to use.

Consider the example:

#include <map>
#include <unordered_set>
#include <string>
#include <iostream>

using namespace std;

static unordered_set<string>    quiet;
static map<const string, const string>  noisy;

template <template <typename ...> class Set, typename K>
static void insert(Set<K> &store, const string &key, const string &)
{
    cout << __PRETTY_FUNCTION__ << "(" << key << ")\n";
    store.insert(key);
}

template <template <typename ...> class Map, typename K, typename V>
static void insert(Map<K, V> &store, const string &key, const string &v)
{
    cout << __PRETTY_FUNCTION__ << "(" << key << ", " << v << ")\n";
    store.insert(make_pair(key, v));
}

int
main(int, char **)
{
    insert(noisy, "cat", "meow");
    insert(quiet, "wallaby", ""); /* macropods have no vocal cords */

    return 0;
}

Though the cat-line works, the wallaby-line triggers the following error from the compiler (clang-10):

t.cc:22:8: error: no matching member function for call to 'insert'
        store.insert(make_pair(key, v));
        ~~~~~~^~~~~~
t.cc:29:2: note: in instantiation of function template specialization
      'insert<unordered_set, std::__1::basic_string<char>, std::__1::hash<std::__1::basic_string<char> > >' requested here
        insert(quiet, "wallaby", ""); /* macropods have no vocal cords */

The error makes it obvious, the quiet, which is an unordered_set, is routed to the insert-implementation for map too -- instead of that made for the unordered_set.

Now, this is not entirely hopeless -- if I:

1. Spell out all of the template-parameters -- including the optional ones (comparator, allocator, etc.)

   template <template <typename ...> class Set, typename K, typename A, typename C>
   static void insert(Set<K, A, C> &store, const string &key, const string &)
   ...
   template <template <typename ...> class Map, typename K, typename V, typename A, typename C>
   static void insert(Map<K, V, A, C> &store, const string &key, const string &v)
   

2. Replace the unordered_set with set.

The program will compile and work as expected -- the compiler will distinguish set from map by the number of arguments each template takes (three vs. four).

But unordered_set has the same number of arguments as map (four)... And unordered_map has five arguments, so it will not be routed to the map-handling method...

How can I tighten the set-handling function's declaration for both types of sets to be handled by it? How can I handle both maps and unordered_maps in the same code?

Answer 1

You can use SFINAE techniques to basically say: consider this overload only when the insert call inside is well-formed. E.g. something like this:

template <template <typename ...> class Set, typename K>
static auto insert(Set<K> &store, const string &key, const string &)
  -> std::void_t<decltype(store.insert(key))>
{
    cout << __PRETTY_FUNCTION__ << "(" << key << ")" << endl;
    store.insert(key);
}

template <template <typename ...> class Map, typename K, typename V>
static auto insert(Map<K, V> &store, const string &key, const string &v)
  -> std::void_t<decltype(store.insert(make_pair(key, v)))>
{
    cout << __PRETTY_FUNCTION__ << "(" << key << ", " << v << ")" << endl;
    store.insert(make_pair(key, v));
}

Demo

Answer 2

std::map and std::unordered_map both have mapped_type member type and their set counterparts don't. So, we can add some SFINAE with the help of std::void_t:

template<template<typename...> class Map, typename K, typename V,
         typename = std::void_t<typename Map<K, V>::mapped_type>>
void insert(Map<K, V>&, const string&, const string&) {
    // ...
}

A more general solution if you need (and in your example you don't) to constraint both function templates:

template<class, typename = void>
struct is_map : std::false_type { };

template<class Map>
struct is_map<Map, std::void_t<typename Map::mapped_type>> : std::true_type { };

template<template<typename...> class Set, typename K, 
         std::enable_if_t<!is_map<Set<K>>::value, int> = 0>
void insert(Set<K>&, const string&, const string&) {
    // ...
}

template<template <typename...> class Map, typename K, typename V,
         std::enable_if_t<is_map<Map<K, V>>::value, int> = 0>
void insert(Map<K, V>&, const string&, const string&) {
    // ...
}

---

C++11 solution:

template<class...>  // or just <class> if genericity is not needed
struct std_void {
    using type = void;
};

template<template<typename...> class Map, typename K, typename V,
         typename = typename std_void<typename Map<K, V>::mapped_type>::type>
void insert(Map<K, V>&, const string&, const string&) {
    // ...
}

Note added. The code in the question was targeted at GCC 4.4.7. This is a pretty old GCC version, which doesn't fully support C++11 standard. In particular, it doesn't support using type aliases, so std_void should be implemented via old-fashioned typedef:

template<class...>
struct std_void {
    typedef void type;
};

Answer 3

First of all, the actual solution, that works with compiler-versions currently found in the wild -- tested with gcc-4.4.7 (stock compiler on RedHat6), gcc-8.3.1, and clang-10 is:

template<class...>  // or just <class> if genericity is not needed
struct std_void {
    typedef void type;
};

template<template<typename...> class Map, typename K, typename V,
         typename = std_void<typename Map<K, V>::mapped_type>>
void insert(Map<K, V>& store, const string &key, const string &value) {
    // ...
}

To a reader from the (glorious) future, by all means, use the techniques proposed by @Evg (on whose proposal this one is based) or the one by @Igor-Tandetnik -- if your compiler supports the necessary features.

Evg's answer -- and this one derived from it -- select the template based on whether or not its type defines a mapped_type. Igor's differentiates on the arguments taken by the template's insert-method. Either would've been suitable to my purposes, but Evg's was easier to adapt to the older compiler.

---

In closing, I must vent my frustration with the state of C++: this shouldn't be so difficult. I got it to work, but a colleague trying to read my code will not understand it -- not without multiple passes through it and numerous curses and "gotchas!"

Yes, the C++ programs are compiled (into binary, rather than "byte", code), and the run-time type information (RTTI) necessary for the full "reflection" is (very) expensive.

But what I needed does not require run time reflection! All of the information necessary is known at compile time, so why don't I have all the necessary language-features already, three decades after it was first introduced? Even 10 years is way too long a wait for such functionality -- chip-manufacturers make processors 32-times fatter during the same period.

The constexpr is sort of it, thank you kindly, but it was added so recently, my compiler still has no support for it...

Answer 4

You must use partial template specializations. Like this:

template<template<typename... > class Map, typename T, typename U> static void
insert (Map<T,U>&, const T&, const U&); // generic function
template<typename T, typename U> static void
insert<std::map<T,U>, T, U> (std::map<T,U>&, const T&, const U&); // this is only called if Map is std::map
// you can put more specializations here

The first function is a generic function, which will be called for all Map except if the type Map doesn't appear in any template specialization for the same function. The second function is the same as the first but it's body is only excecuted if the type Map is std::map<T,U>.

See the wikipedia article on partial template specialization