4
\$\begingroup\$

I created a template trait which finds the common iterator category between a set of given iterator categories. More specifically, it's a class with a member type alias to one of the iterator tags which is the most efficient for the specific requirement set that is implied by both categories given as template arguments (the least "powerful" in the iterator hierarchy).

For example, given std::forward_iterator_tag, std::random_access_iterator_tag and std::bidirectional_iterator_tag, it provide std::forward_iterator_tag.

If all the given types are std::output_iterator_tag then it will provide std::output_iterator_tag. Otherwise, there is no member type alias. (std::output_iterator_tag must be treated differently because it is not in the input iterator hierarchy.)

#include <algorithm>
#include <iterator>
#include <tuple>
#include <type_traits>

namespace detail {
    // Gets the index of the first occurrence of a type in a tuple (inverse of std::tuple_element_t).
    template <typename T, class Tuple>
    struct tuple_type_index;

    // Specialisation for match on parameter pack's first type.
    template<typename T, typename... Ts>
    struct tuple_type_index<T, std::tuple<T, Ts...>> : std::integral_constant<std::size_t, 0> {};

    // Specialisation for no match on parameter pack's first type.
    template<typename T, typename U, typename... Ts>
    struct tuple_type_index<T, std::tuple<U, Ts...>> : std::integral_constant<std::size_t, 1 + tuple_type_index<T, std::tuple<Ts...>>::value> {};

    // Helper variable template.
    template<typename T, class Tuple>
    constexpr std::size_t tuple_type_index_v = tuple_type_index<T, Tuple>::value;


    // Hierarchy of input iterator categories (output iterator category is handled separately) from least to most powerful.
    using iterator_categories = std::tuple<std::input_iterator_tag, std::forward_iterator_tag, std::bidirectional_iterator_tag, std::random_access_iterator_tag>;
}


// Primary template (for 0 categories).
template<class... IteratorCategories>
struct common_iterator_category {};

// Helper type alias.
template<class... IteratorCategories>
using common_iterator_category_t = typename common_iterator_category<IteratorCategories...>::type;

// Specialisation for 1 category.
template<class IteratorCategory>
struct common_iterator_category<IteratorCategory> {
    using type = IteratorCategory;
};

// Specialisation for 2 non-output-iterator categories.
template<class IteratorCategory1, class IteratorCategory2>
struct common_iterator_category<IteratorCategory1, IteratorCategory2> {
    using type = std::tuple_element_t<
        std::min(
            detail::tuple_type_index_v<IteratorCategory1, detail::iterator_categories>,
            detail::tuple_type_index_v<IteratorCategory2, detail::iterator_categories>),
        detail::iterator_categories>;
};

// Specialisation for 2 output iterator categories.
template<>
struct common_iterator_category<std::output_iterator_tag, std::output_iterator_tag> {
    using type = std::output_iterator_tag;
};

// Specialisation for 3+ categories.
template<class IteratorCategory1, class IteratorCategory2, class... IteratorCategories>
struct common_iterator_category<IteratorCategory1, IteratorCategory2, IteratorCategories...> :
    common_iterator_category<common_iterator_category_t<IteratorCategory1, IteratorCategory2>, common_iterator_category_t<IteratorCategories...>> {};

The code with tests/examples is live here.

I am specifically interested in feedback with regards to the conciseness/efficiency of the design, and also whether it is well formed (I am worried about UB but "happens to work" or no diagnostic required issues). I'm not so much concerned with the tuple_type_index utility (it's just there because it happens to be required). But feedback of any sort is of course welcome.

\$\endgroup\$
6
\$\begingroup\$

If you have a typelist of iterator tag types, then std::common_type will find the common base type.

using InTag = std::istream_iterator<int>::iterator_category;
using BdTag = std::list<int>::iterator::iterator_category;
using RaTag = std::vector<int>::iterator::iterator_category;

static_assert(std::is_same_v<std::common_type_t<InTag, BdTag>, std::input_iterator_tag>);
static_assert(std::is_same_v<std::common_type_t<InTag, RaTag>, std::input_iterator_tag>);
static_assert(std::is_same_v<std::common_type_t<BdTag, RaTag>, std::bidirectional_iterator_tag>);

If you are unwrapping the tag type at the call site, just have the trait do it.

template <class... Iterators>
struct common_iterator_tag 
: std::common_type<typename std::iterator_traits<Iterators>::iterator_category...>
{
};

template <class... Iterators>
using common_iterator_tag_t = typename common_iterator_tag<Iterators...>::type;

using RaIter = std::vector<int>::iterator;
using InIter = std::istream_iterator<int>::iterator;

static_assert(std::is_same_v<std::input_iterator_tag, common_iterator_tag_t<RaIter, InIter>>);

using BackIter = std::back_insert_iterator<std::vector<int>>;
using InsertIter = std::insert_iterator<std::list<int>>;

static_assert(std::is_same_v<std::output_iterator_tag, common_iterator_tag_t<BackIter, InsertIter>>);
\$\endgroup\$
  • \$\begingroup\$ Oh I'm so stupid, I didn't even stop to look/think that they were in an inheritance relationship... Thanks! \$\endgroup\$ – MC ΔT Nov 11 '18 at 8:28
0
\$\begingroup\$

You should try to implement min and a minimal typelist to get rid of std::tuple and std::min (and their headers) and so, make it compatible with c++11 and reduce header dependencies.

but otherwise it's a pretty useful trait, well writed and easy to understand.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.