Elegant way to static_assert() that a standard library container type is ordered?

Question

In a templated function where one parameter is a standard library container of type T, can I easily statically assert that T is an ordered container?

Is there a more elegant way to do this than to do something type-specific, like test for the presence of a hash_function() function to distinguish between std::map and std::unordered_map ?

Answer 1

Another simple one:

template <template <typename...> class Container>
struct is_ordered : std::false_type {};

template <> struct is_ordered<std::map>      : std::true_type {};
template <> struct is_ordered<std::set>      : std::true_type {};
template <> struct is_ordered<std::multimap> : std::true_type {};
template <> struct is_ordered<std::multiset> : std::true_type {};

and then just static_assert(is_ordered<Container>::value, "error") to use it. It's pretty easy to extend to custom containers too: just add a line like the above.

If you don't want to use template-templates at the call site, you can always wrap it ala:

template <typename T> struct is_ordered_2 : std::false_type {};
template <template <typename...> class Container, typename... Ts>
struct is_ordered_2<Container<Ts...>> : is_ordered<Container> {};

and then you can use it either way.

Answer 2

This approach is pretty simple:

// default result
template<class T>constexpr bool IsOrdered(const T&) {return false;}

// now enumerate the ordered standard library types of interest:
template<class K, class T, class C, class A>
constexpr bool IsOrdered(const std::map<K,T,C,A>&) {return true;}
// ...remaining types...

Answer 3

If you're only concerned with barring the use of a couple particular classes like std::unordered_map and std::unordered_set, for example, you could use type traits in concert with static_assert:

#include <type_traits>
#include <unordered_map>
#include <unordered_set>

template <typename Container, typename T>
void func(Container<T> &c)
{
    // make sure that the provided container isn't a type we don't want!
    static_assert(!std::is_same<Container<T>, std::unordered_map<T>>::value);
    static_assert(!std::is_same<Container<T>, std::unordered_set<T>>::value);
}

I'm not sure whether this qualifies as "type-specific" or not based on your original question. You're not looking at the innards of the prohibited classes at all (like looking for a hash_function(), but this method would require you to enumerate the containers that you don't want to work with.

Answer 4

You could (emphasis on could, cuz I don't think it is standard) do something like this:

template <typename T>
struct has_typedef_key_compare 
{
  // Types "yes" and "no" are guaranteed to have different sizes,
  // specifically sizeof(yes) == 1 and sizeof(no) == 2.
  typedef char yes[1];
  typedef char no[2];

  template <typename C>
  static yes& test(typename C::key_compare*);

  template <typename>
  static no& test(...);

  // If the "sizeof" of the result of calling test<T>(0) would be equal to sizeof(yes),
  // the first overload worked and T has a nested type named foobar.
  static const bool value = sizeof(test<T>(0)) == sizeof(yes);
};

template <typename T>
struct is_sorted_container
{
  static const bool value;
};

template <typename T>
const bool is_sorted_container<T>::value = has_typedef_key_compare<T>::value;

The rationale is that all sorted stl containers (that I looked at) have a key_compare function. Of course, this is NOT standard. This would NOT cover non-stl types. All in all, I don't like it, but I thought I'd post it as an interesting alternative.

How stl function (like std::upper_bound) cover this is to put the restriction of sorted iterator in the comments, and let the end user figure it out.