July 8, 2019

A Look at Iterator Traits

  —The Iterator Category Trait.

I took the opportunity to develop a patch Boost::Utility to address bug 13002. I concluded:

The compiler error in the reproducer occurs because std::set does not provide a random access iterator.

Absolutely correct. And terribly short-sighted.

I didn’t think this was a bug because C++ doesn’t require support for the expression r += n, unless the object supports a random access iterator. This lack of support for this expression causes the compilation error reported in stl_iterator.h.

std::set doesn’t provide a random access iterator. It provides a bidirectional iterator. Same for std::list. std::vector provides a random access iterator.

Even the tests supported my thinking. But the tests were insufficient and I wasn’t aware of bug 10847.

I wish I could say I authored this patch. I didn’t. Here is the most relevant parts (full commit).

template< typename T >
struct is_iterator
{
private:
    typedef char yes_type;
    typedef char (&no_type)[2];

    template< typename U >
    static yes_type check_iterator_category(typename U::iterator_category*);
    template< typename U >
    static no_type check_iterator_category(...);

public:
    static BOOST_CONSTEXPR_OR_CONST bool value = sizeof(is_iterator< T >::BOOST_NESTED_TEMPLATE check_iterator_category< T >(0)) == sizeof(yes_type);
};

Important components:

• iterator_category defines the category of the iterator. Must be one of iterator category tags.

• BOOST_CONSTEXPR_OR_CONST sets value to a constexpr or const, depending upon whether the compiler supports constexpr or not.

• BOOST_NESTED_TEMPLATE enhances support for member templates.

template< typename T, typename Distance, bool IsIterator = is_iterator< T >::value >
struct next_advance_impl :
    public next_plus_assign_impl< T, Distance >
{
};

template< typename T, typename Distance, bool IsIterator = is_iterator< T >::value >
struct prior_advance_impl :
    public prior_minus_assign_impl< T, Distance >
{
};

Very cool.

I was wrong about the direction to take this patch because I didn’t look through the bug database to see if there were other open tickets against boost::next() and boost::prior().

On the bright side because someone authored bug 13002 I was able to participate in the improvement of Boost!