iterator category deduction from variadic parameters

Question

How can I fill in the ???

template<class...Itrs> struct itr_category { typedef /* ??? */ type; };

so that type is the most specialized of iterator_traits<Itrs>::iterator_category... which supports all the Itrs' operations, else failure (like enable_if<false>::type) if there is no single such category?

Most specialized means the most descended type (iterator_category) in the following inheritance:

struct input_iterator_tag { };
struct output_iterator_tag { };
struct forward_iterator_tag :       public         input_iterator_tag, 
                                    public        output_iterator_tag { };
struct bidirectional_iterator_tag : public       forward_iterator_tag { };
struct random_access_iterator_tag : public bidirectional_iterator_tag { };

So, for example, something like itr_category<InputIterator,OutputIterator,...> would fail.

NB: this is a different hierarchy than defined in std::iterator_traits (see 24.3 or http://en.cppreference.com/w/cpp/iterator/iterator_tags): hereforward_iterator_tag derives from both input_iterator_tag and output_iterator_tag, rather than just the former. This corresponds to the inheritance described in, e.g., the SGI documentation (see http://www.sgi.com/tech/stl/Iterators.html). Feel free to comment on this discrepancy if it is relevant (this is part of a zip iterator implementation, by the way).

Answer 1

First, you'll need a fold function for types, something like this:

template< template< typename, typename > class f, typename init, typename... types >
class fold;

template< template< typename, typename > class f, typename init >
struct fold< f, init > {
    typedef init type;
};

template< template< typename, typename > class f, typename init, typename type_arg, typename... type_args >
struct fold< f, init, type_arg, type_args... > {
    typedef typename fold< f, typename f< init, type_arg >::type, type_args... >::type type;
};

Then, define a combining function:

template< typename i1, typename i2 >
struct combine_iterators {
private:
    typedef typename iterator_traits< i1 >::category c1;
    typedef typename iterator_traits< i2 >::category c2;
    typedef decltype( false ? ( c1 * )nullptr : ( c2 * )nullptr ) ptype;
public:
    typedef typename std::decay< decltype( *( ptype )nullptr ) >::type type;
};

template<class...Itrs> struct itr_category {
    typedef typename fold< combine_iterators, random_access_iterator_tag, Itrs... >::type type;
};

And, basically, that's it:

class it1;
template<> struct iterator_traits< it1 > {
    typedef bidirectional_iterator_tag category;
};

class it2;
template<> struct iterator_traits< it2 > {
    typedef input_iterator_tag category;
};

class it3;
template<> struct iterator_traits< it3 > {
    typedef output_iterator_tag category;
};

itr_category< it1, it2 >::type x; // typeid( x ).name() == "struct input_iterator_tag"
itr_category< it1, it3 >::type y; // typeid( x ).name() == "struct output_iterator_tag"
itr_category< it2, it3 >::type z; // operand types are incompatible ("input_iterator_tag *" and "output_iterator_tag *")
itr_category< it1, it2, it3 >::type w; // operand types are incompatible ("input_iterator_tag *" and "output_iterator_tag *")

Answer 2

Simply define a common_category trait which yields the minimum. Then define the type as the type of common_category<firstiter, common_category<seconditer, etc>>. I forget the variadic template instruction for such things.