How do I constrain a template parameter to comply to a Key in std::map?

Question

I have a class template that intends to use its parameter K as the key to a map.

Is there any way to restrict the template parameter to be a type that complies with the Key in std::map?

I realize that even without such constraint, the compiler would spit out a pile of template errors like K having no operator < (), but it would be nice if I can make my code more obvious in specifying requirements.

C++11 solutions are welcome.

template< typename K >
class Foo
{
  // lots of other code here...

  private:
    std::map< K, size_t > m_map;
};

Answer 1

It depends on what you mean by "complies." If you want to verify that K has a < operator then you might try the Boost Concept Checking Library.

#include "boost/concept_check.hpp"

template< typename K >
class Foo
{
  BOOST_CONCEPT_ASSERT((boost::LessThanComparable< K >));

  // lots of other code here...

  private:
    std::map< K, size_t > m_map;
};

However if you want to verify that < defines a StrictWeakOrdering on K, that would require testing run-time behaviour under all possible inputs.

Answer 2

C++11 version:

#include <type_traits>

template<class T>
struct satisfies_key_req{
  struct nat{};

  template<class K> static auto test(K* k) -> decltype(*k < *k);
  template<class K> static nat  test(...);

  static bool const value = !std::is_same<decltype(test<T>(0)), nat>::value;
};

#include <iostream>

struct foo{};

int main(){
    static bool const b = satisfies_key_req<int>::value;
    std::cout << b << '\n';
    static bool const b2 = satisfies_key_req<foo>::value;
    std::cout << b2 << '\n';
}

Output:

1
0

---

The key point I used here is expression SFINAE: auto test(K* k) -> decltype(*k < *k). If the expression in the trailing-return-type is not valid, then this particular overload of test is removed from the overload set. In other words, it's SFINAE'd.

§14.8.2 [temp.deduct]

p6 At certain points in the template argument deduction process it is necessary to take a function type that makes use of template parameters and replace those template parameters with the corresponding template arguments. This is done at the beginning of template argument deduction when any explicitly specified template arguments are substituted into the function type, and again at the end of template argument deduction when any template arguments that were deduced or obtained from default arguments are substituted.

p7 The substitution occurs in all types and expressions that are used in the function type and in template parameter declarations. The expressions include not only constant expressions such as those that appear in array bounds or as nontype template arguments but also general expressions (i.e., non-constant expressions) inside sizeof, decltype, and other contexts that allow non-constant expressions.

p8 If a substitution results in an invalid type or expression, type deduction fails. An invalid type or expression is one that would be ill-formed if written using the substituted arguments. [...]

---

You can use it in three flavors for your Foo class to trigger an error.

// static_assert, arguably the best choice
template< typename K >
class Foo
{
  static_assert<satisfies_key_req<K>::value, "K does not satisfy key requirements");
  // lots of other code here...

  private:
    std::map< K, size_t > m_map;
};

// new-style SFINAE'd, maybe not really clear
template<
  typename K,
  typename = typename std::enable_if<
               satisfies_key_req<K>::value
             >::type
>
class Foo
{
  // lots of other code here...

  private:
    std::map< K, size_t > m_map;
};

// partial specialization, clarity similar to SFINAE approach
template< 
  typename K,
  bool = satisfies_key_req<K>::value
>
class Foo
{
  // lots of other code here...

  private:
    std::map< K, size_t > m_map;
};

template<typename K>
class Foo<K, false>;

Answer 3

A complete solution to your problem probably is impossible. But I can suggest you a solution, if you want to restrict K to be a specific type you can define your class as follows

template <class K, bool = std::is_same<K,int>::value>
class Foo { ... };

template <class K>
class Foo<K,false> { Foo(); };

So if K is int your class works as expected. Otherwise you can not costruct object of type Foo<K>. Obviously you can refine the condition.

To check if K has the operator< you can use boost::has_less, but as you can check in the documentation this traits doesn't work properly always.

Answer 4

From your question, I guess you want one suitable error instead of loads of errors.

Following code finds, if a type has a valid operator < or not:

namespace OperatorExist
{
  typedef char no[3]; // '3' can be any awkward number
  template<typename T> no& operator < (const T&, const T&);

  template<typename T>
  struct LessThan {
    static const bool value = (sizeof(*(T*)(0) < *(T*)(0)) != sizeof(no));
  };
}

Now, you can specialize class Foo using the above construct:

template<typename K, bool = OperatorExist::LessThan<K>::value>
class Foo 
{
  // lots of other code here...
  private:
    std::map<K, size_t> m_map;
};

template<typename K>
class Foo<K, false>; // unimplemented for types not suitable for 'std::map'

As soon as you use some type A which doesn't have compatibility with std::map, the compiler will complain with single error:

error: aggregate ‘Foo<A> oa’ has incomplete type and cannot be defined

Demo