Doc No: | N4068 |
Date: | 2014-06-28 |
Reply to: | stdbill.h@pobox.com |
The problem is probably best solved using concepts; but we already have iterator tags and they’re not going away. This short paper asks whether there’s interest in having more finely-grained iterator tags. At this point, it’s just a partly-baked idea intended to get a discussion started.
struct reference_tag { };
struct lvalue_tag { }; struct rvalue_tag { };
struct equality_comparable_tag { };
struct multipass_tag { };
struct decrementable_tag { };
struct random_move_tag { };
template<class... Tags> struct basic_iterator_tag { };
And then the existing iterator tags that we all know and love could become:
typedef basic_iterator_tag<lvalue_tag> output_iterator_tag; typedef basic_iterator_tag<rvalue_tag, equality_comparable_tag> input_iterator_tag; typedef basic_iterator_tag<reference_tag, lvalue_tag, rvalue_tag, equality_comparable_tag, multipass_tag> forward_iterator_tag; typedef basic_iterator_tag<reference_tag, lvalue_tag, rvalue_tag, equality_comparable_tag, multipass_tag, decrementable_tag> bidirectional_iterator_tag; typedef basic_iterator_tag<reference_tag, lvalue_tag, rvalue_tag, equality_comparable_tag, multipass_tag, decrementable_tag, random_move_tag> random_access_iterator_tag;
typedef basic_iterator_tag<lvalue_tag, rvalue_tag, equality_comparable_tag, multipass_tag, decrementable_tag, random_move_tag> vector_bool_iterator_tag;Note that it lacks reference_tag in the parameter pack because *iter returns a proxy instead of a proper bool&.
typedef basic_iterator_tag<rvalue_tag, equality_comparable_tag, multipass_tag, decrementable_tag, random_move_tag> scrolling_cursor_tag;A scrolling cursor can move back and forth by arbitrary distances; but it lacks both reference_tag and lvalue_tag because *iter probably returns by const reference a value cached in the iterator itself.
#include <iostream> #include <type_traits> namespace std { namespace experimental { // // The proposed iterator tags: // struct reference_tag { }; struct lvalue_tag { }; struct rvalue_tag { }; struct equality_comparable_tag { }; struct multipass_tag { }; struct decrementable_tag { }; struct random_move_tag { }; template<class... Tags> struct basic_iterator_tag { }; // // The existing iterator tags: // typedef basic_iterator_tag<lvalue_tag> output_iterator_tag; typedef basic_iterator_tag<rvalue_tag, equality_comparable_tag> input_iterator_tag; typedef basic_iterator_tag<reference_tag, lvalue_tag, rvalue_tag, equality_comparable_tag, multipass_tag> forward_iterator_tag; typedef basic_iterator_tag<reference_tag, lvalue_tag, rvalue_tag, equality_comparable_tag, multipass_tag, decrementable_tag> bidirectional_iterator_tag; typedef basic_iterator_tag<reference_tag, lvalue_tag, rvalue_tag, equality_comparable_tag, multipass_tag, decrementable_tag, random_move_tag> random_access_iterator_tag; // // Whether a parameter pack contains a given type // (probably an implementation detail in the standard library): // template <class Required, class... Present> struct _Pack_has_type; template <class Required> struct _Pack_has_type<Required> : false_type { }; template <class Required, class... Rest> struct _Pack_has_type<Required, Required, Rest...> : true_type { }; template <class Required, class First, class... Rest> struct _Pack_has_type<Required, First, Rest...> : _Pack_has_type<Required, Rest...> { }; // // Whether a basic_iterator_tag (Candidate) has a parameter pack that’s // a superset of the pack of some minimum basic_iterator_tag (Required): // template <class Candidate, class Required> struct has_iterator_tags; template <class... Candidates> struct has_iterator_tags<basic_iterator_tag<Candidates...>, basic_iterator_tag<>> : true_type { }; template <class... Candidates, class Reqd1, class... ReqdRest> struct has_iterator_tags<basic_iterator_tag<Candidates...>, basic_iterator_tag<Reqd1, ReqdRest...>> : integral_constant<bool, _Pack_has_type<Reqd1, Candidates...>::value && has_iterator_tags<basic_iterator_tag<Candidates...>, basic_iterator_tag<ReqdRest...>>::value> { }; } // namespace experimental } // namespace std namespace { using std::experimental::has_iterator_tags; using std::experimental::basic_iterator_tag; using std::experimental::random_move_tag; namespace detail { template<class Iter> void my_algorithm(Iter, std::false_type) { std::cout << "Less efficient\n"; } template<class Iter> void my_algorithm(Iter, std::true_type) { std::cout << "More efficient\n"; } } template<class Iter> void my_algorithm(Iter first) { detail::my_algorithm(first, has_iterator_tags<typename Iter::iterator_category, basic_iterator_tag<random_move_tag>>()); } struct my_forward_iterator { typedef std::experimental::forward_iterator_tag iterator_category; }; struct my_random_iterator { typedef std::experimental::random_access_iterator_tag iterator_category; }; } // anonymous namespace int main() { my_algorithm(my_forward_iterator()); my_algorithm(my_random_iterator()); }