Re: [Boost-users] [mpl] Iterator Concept Checking? SOLVED + Recommendation.

Subject: Re: [Boost-users] [mpl] Iterator Concept Checking? SOLVED + Recommendation.
From: Aleksey Gurtovoy (agurtovoy_at_[hidden])
Date: 2010-11-08 03:11:40

On Tue, 02 Nov 2010 20:06:25 -0500, Stirling Westrup <swestrup_at_[hidden]>  
wrote:

> On Sun, Oct 31, 2010 at 6:16 PM, Stirling Westrup <swestrup_at_[hidden]>  
> wrote:
>> On Sat, Oct 30, 2010 at 8:57 PM, David Abrahams <dave_at_[hidden]>  
>> wrote:
>>>
>>> At Sat, 30 Oct 2010 17:55:35 -0400,
>>> Stirling Westrup wrote:
>>>>
>>>> I am writing some algorithms to operate on MPL sequences, and I would
>>>> like to use some form of concept checking to ensure that the types
>>>> passed in that are supposed to be iterators are, in fact, iterators.
>>>>
>
> I have solved the problem I was working on, but as I'm not completely
> happy with my solution, I thought I'd post it here and make a
> recommendation for a small change to MPL that would have simplified my
> work.
>
> I discovered while reading about the iterator_category metafunction
> that the iterator tags had ascending values. (
> http://www.boost.org/doc/libs/1_44_0/libs/mpl/doc/refmanual/iterator-category.html
> ). This is only documented there, and not in the description of the
> individual iterator categories. In fact, the individual iterator
> categories are completely misleading as they state that there is a
> member named 'category' that is convertible to the type of the tag.
> Since a random iterator is a refinement of a forward iterator and
> therefor has at least the same set of requirements, it would imply
> that:
>
> BOOST_MPL_ASSERT
>   (( is_convertible<RandomIterator::category,forward_iterator_tag>))
>
> should succeed, and it does NOT.

I agree, the docs are currently misleading/incorrect; please see below,  
though.

> It would seem that one should use iterator_category to determine if
> something is an iterator or not, but its only actually defined when
> its type is an iterator, so that doesn't really work. I ended up
> writing my own version that was defined for all types, like this:
>
>    struct non_iterator_tag : mpl::int_<INT_MIN>
> 	{ typedef non_iterator_tag type; };
>
>    BOOST_MPL_HAS_XXX_TRAIT_NAMED_DEF(has_category,category,false)
>
>       template<bool b, typename T>
>       struct category_impl
> 	{
> 	  typedef non_iterator_tag type;
> 	  static const type::value_type value = type::value;
> 	};
>
>       template<typename T>
>       struct category_impl<true,T>
> 	{
> 	  typedef typename mpl::iterator_category<T>::type type;
> 	  static const int value = type::value;
> 	};
>
>
>       // just like mpl::iterator_category<T> but can be passed any
>       // type, and returns mplx::not_iterator_tag on bad types. Note
>       // that this value will compare less-than any valid iterator
>       // tag.
>       template<typename T>
>       struct category
> 	: category_impl<has_category<T>::value,T>
> 	{};
>
>       template<typename Iterator>
>       struct is_forward_iterator
> 	{
> 	  typedef typename mpl::greater_equal
> 	    < typename category<Iterator>::type
> 	    , mpl::forward_iterator_tag
> 	    >::type type;
> 	};
>
>       template<typename Iterator>
>       struct is_bidirectional_iterator
> 	{
> 	  typedef typename mpl::greater_equal
> 	    < typename category<Iterator>::type
> 	    , mpl::bidirectional_iterator_tag
> 	    >::type type;
> 	};
>
>       template<typename Iterator>
>       struct is_random_access_iterator
> 	{
> 	  typedef typename mpl::greater_equal
> 	    < typename category<Iterator>::type
> 	    , mpl::random_access_iterator_tag
> 	    >::type type;
> 	};
>
>
> The above works, but it relies upon me testing to see if there is an
> embedded category member, which I suspect is going to get deprecated
> by iterator_category<> just like all the other members were. It would
> be far preferable for me if there was an actual non_iterator_tag and
> iterator_category<> were already defined for all types, so it could
> both be used in a convenient manner, and so that there was an obvious
> way to write a specialization in the case that, for instance, one
> needed the type 'int' to be an iterator.

I considered this at some point, but in the end failed to come up with a  
use case for an iterator type that _has_ to be adopted "as is" and decided  
not to bother. Plus checking for the 'category' member is a little to  
broad of a test, IMHO.

>
> In the very least, please update the documentation to mention the
> actual relationships between the tags in the discussion about the
> iterators, and to remove the incorrect 'convertible' description.
>

We can either fix the docs or fix the code. I'm actually inclined to fix  
the code.

There are two reasons why I deviated from the standard iterator tags'  
relationship:

  1. I wanted this to work:

     typedef typename min<
           typename iterator_category<iter1>::type
         , typename iterator_category<iter2>::type
         >::type category;

  2. I *thought* I had no use case for keeping the inheritance, and  
preserving
     it while also supporting #1 seemed like unnecessary hassle.

Now that you pointed out that by removing it I both broke the docs *and*  
violated at least one person's expectations, "the hassle" seems more like  
a win-win solution to me: the docs would become correct again, you (and  
the rest of the users) would get intuitively expected, standard-like  
relationship between tags and ability to test them with 'is_convertible',  
and I'd still get to keep #1.

Thoughts?

-- 
Aleksey Gurtovoy
MetaCommunications Engineering