Disambiguate template specialization between map-like and vector-like containers

Question

template<class> struct Printer;

// I want this to match std::vector (and similar linear containers) 
template<template<class, class...> class T, class TV, class... TS> 
    struct Printer<T<TV, TS...>> { ... };

// I want this to match std::map (and similar map-like containers)
template<template<class, class, class...> class TM, class TK, class TV, typename... TS> 
    struct Printer<TM<TK, TV, TS...>> { ... }

int main() 
{
    // Both of these match the second specialization, which is only intended
    // for std::map (and similar map-like containers)
    Printer<std::vector<int>>::something();
    Printer<std::map<int, float>>::something();
}

As you can see from the example, std::vector and std::map both match the second specialization. I think it's because std::vector's allocator parameter gets matched to TV, which is intended for std::map's value.

How can I match std::vector (and other linear containers) with the first specialization and std::map (and other key-value containers) with the second one?

Note that the number of `template` arguments is a horrible way to solve your problem: it is brittle, and depends on implementation details you should not care about. — Yakk - Adam Nevraumont, Feb 09 '14 at 16:40
The correct (or at least, standardized) terms are **Sequential Container** and **Associative Container**. *n.b., this comment is more for Google, than you.* — Orwellophile, Nov 04 '17 at 12:44

score 19 · Accepted Answer · answered Feb 09 '14 at 16:08

The problem with the pattern-matching approach is that it will only ever work if for every single container you write a specialization. This is tedious work.

Instead you can rely on other properties:

a container will necessarily be iterable over via begin(c) and end(c) expressions
on top of this, an associative container will have a ::key_type nested type, among others, as expressed in § 23.2.4 [associative.rqmts].

Therefore, we can whip up a classifier, based on tag dispatching:

inline constexpr auto is_container_impl(...) -> std::false_type {
    return std::false_type{};
}

template <typename C>
constexpr auto is_container_impl(C const* c) ->
    decltype(begin(*c), end(*c), std::true_type{})
{
    return std::true_type{};
}

template <typename C>
constexpr auto is_container(C const& c) -> decltype(is_container_impl(&c)) {
    return is_container_impl(&c);
}

inline constexpr auto is_associative_container_impl(...)
    -> std::false_type
{ return std::false_type{}; }

template <typename C, typename = typename C::key_type>
constexpr auto is_associative_container_impl(C const*) -> std::true_type {
    return std::true_type{};
}

template <typename C>
constexpr auto is_associative_container(C const& c)
    -> decltype(is_associative_container_impl(&c))
{
    return is_associative_container_impl(&c);
}

And now you can write "simple" code:

template <typename C>
void print_container(C const& c, std::false_type/*is_associative*/) {
}

template <typename C>
void print_container(C const& c, std::true_type/*is_associative*/) {
}

template <typename C>
void print_container(C const& c) {
    return print_container(C, is_assocative_container(c));
}

Now, this might not be exactly what you wish for, because under this requirements a set is an associative container, but its value is not a pair, so you cannot print key: value. You have to adapt the tag-dispatching to your needs.

Technically you should check if `iterator_traits< decltype(begin(c)) >` and `iterator_traits< decltype(end(c)) >` exists and is the same in an ADL context that includes `using std::begin; using std::end;` works to determine if something is an iterable range. Still don't know if it is a container, but probably do not care. :) — Yakk - Adam Nevraumont, Feb 10 '14 at 01:09
Elegant code, awesome use of C++11! At first it looks as if this would match C arrays as containers (since `std::begin(nArray`) is valid) but you take advantage of decay into pointer (with `C const *c`) and this is no longer the case. Flawless! — Nikos Athanasiou, Feb 13 '14 at 18:42
@NikosAthanasiou: It was actually intended to match C arrays (after all they can be printed), to be honest I would have to test whether or not it does (don't remember off the top of my head whether `&c` will decay or not, though I thought it would not). — Matthieu M., Feb 13 '14 at 18:46

score 3 · Answer 2 · answered Feb 09 '14 at 16:02

Your question is a bit ambiguous as there are also containers which are neither sequential, nor "key-value", e.g. set. I take it you meant to distinguish sequence from associative containers?

If that is the case you can rely on the fact that associative containers have key_type, while the sequence containers do not. Here's a solution:

#include <type_traits>
#include <vector>
#include <map>

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

template<class T>
struct IsAssociativeContainer<T,
    typename std::enable_if<sizeof(typename T::key_type)!=0>::type>
  : std::true_type {};

template<class T, bool = IsAssociativeContainer<T>::value>
struct Printer;

// I want this to match std::vector (and similar linear containers) 
template<template<class, class...> class T, class TV, class... TS> 
    struct Printer<T<TV, TS...>, false> { static void something(); };

// I want this to match std::map (and similar map-like containers)
template<template<class, class, class...> class TM, class TK, class TV, typename... TS> 
    struct Printer<TM<TK, TV, TS...>, true> { static void something(); };

int main() 
{
    // Both of these match the second specialization, which is only intended
    // for std::map (and similar map-like containers)
    Printer<std::vector<int>>::something();
    Printer<std::map<int, float>>::something();
}

Live example

Richard Vock · Answer 3 · 2014-02-09T15:21:01.977

The problem here is that

template <class, class...> T

and

template <class, class, class...> TM

both match any template classes that have at least 2 template parameters which is the case in both your examples. One thing you can do is to make both template parameter lists more specific, like for example:

template <class>
struct Printer;

template <template<typename, typename> class C, template <typename> class A, typename T>
struct Printer< C<T, A<T>> > {
    ...
};

template <template<typename, typename, typename, typename> class C, template <typename> class Comp, template <typename> class A, typename K, typename T>
struct Printer< C<K, T, Comp<K>, A<std::pair<const K,T>>> > {
    ...
};

You can see it working for std::vector and std::map here: http://coliru.stacked-crooked.com/a/7f6b8546b1ab5ba9

Another possibility is to use SFINAE (actually I'd recommend using it in both scenarios):

template<template<class, class...> class T, class TV, class... TS, class = typename std::enable_if<std::is_same<T, std::vector>::value>::type> 
struct Printer<T<TV, TS...>> { ... };

template<template<class, class, class...> class TM, class TK, class TV, typename... TS, class = typename std::enable_if<std::is_same<T, std::map>::value>::type> 
struct Printer<TM<TK, TV, TS...>> { ... }

Edit: Oups, just read in the comments you wanted to match something 'std::vector'-like, not specifically std::vector. The first method however should at least differentiate between std::vector and std::map. If you want to write algorithms for containers with different ways to iterate over, why not write your functions for iterators and differentiate between those?

Edit2: The code before was miserably wrong. However it works now.

The first method can be used to write generic container traits, like done here: http://functionalcpp.wordpress.com/2013/08/22/container-traits/ I get the impression that this is what you're looking for... — Richard Vock, Feb 09 '14 at 14:54

Disambiguate template specialization between map-like and vector-like containers

3 Answers3

Linked