Home > Articles > Programming > C/C++

  • Print
  • + Share This
This chapter is from the book

42.6 Constraining the Iterator Category

Given that we've chosen to eschew random access iterator semantics, we actually have a problem on our hands. If we adapt a random access iterator, the adapted form will think it's a random access iterator—the iterator_category member type of the adapted type will be std::random_access_iterator_tag—even though we've supplied it only with bidirectional iterator semantics. This is a problem. As soon as we try to pass this off to an algorithm that has a specialized form for handling random access iterators, things are going to get ugly. What you tend to see in this case is an enormous list of error messages, and ensconced within, if you're lucky enough to spot it, will be some mention of a missing operator -(), or operator +(), or some other operation specific to random access iterators.

You might wonder why we've not come across this with the other adaptors. Well, transform_iterator (Chapter 36), member_selector_iterator (Chapter 38), and index_iterator (extra chapter on the CD) are all able to exhibit the iterator category of their base type; filter_iterator, by its very nature, cannot.

Thus, the final act of cunning is to use the min_iterator_category template and its 16 full specializations, each of which corresponds to a permutation of two standard iterator categories. The primary template and several of the specializations are shown in Listing 42.5. In each permutation, the member type iterator_category is defined as the lesser refinement of the two specializing types.

Listing 42.5. Primary Template and Some Specializations of min_iterator_category

template< typename C1 // First category
        , typename C2 // Second category
        >
struct min_iterator_category;

template <>
struct min_iterator_category<  std::input_iterator_tag
                            ,  std::input_iterator_tag
                            >
{
  typedef std::input_iterator_tag iterator_category;
};
template <>
struct min_iterator_category< std::forward_iterator_tag
                            , std::input_iterator_tag
                            >
{
  typedef std::input_iterator_tag iterator_category;
};
. . .
template <>
struct min_iterator_category<  std::bidirectional_iterator_tag
                            ,  std::random_access_iterator_tag
                            >
{
  typedef  std::bidirectional_iterator_tag iterator_category;
};
template <>
struct min_iterator_category<  std::random_access_iterator_tag
                            ,  std::random_access_iterator_tag
                            >
{
  typedef  std::random_access_iterator_tag iterator_category;
};

The traits class is used to limit the iterator_category member type to the maximum sensible refinement that is supportable (Listing 42.6).

Listing 42.6. Definition of filter_iterator

template< typename I // The underlying iterator
        , typename P // The unary predicate that will select the items
        , typename T = adapted_iterator_traits<I>
        >
class filter_iterator
{
public: // Member Types
  . . .
  typedef filter_iterator<I, P, T>                 class_type;
  typedef typename min_iterator_category<                              
                           typename traits_type::iterator_category
                         , std::bidirectional_iterator_tag
                         >::iterator_category      iterator_category;
  . . .
  • + Share This
  • 🔖 Save To Your Account