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

Subject: Re: [Boost-users] [mpl] Iterator Concept Checking? SOLVED + Recommendation.
From: David Abrahams (dave_at_[hidden])
Date: 2010-11-03 22:02:44

At Tue, 2 Nov 2010 21:06:25 -0400,
Stirling Westrup 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.

Who states?  Where?  Oh, after searching... you mean, e.g.,
http://www.boost.org/doc/libs/1_44_0/libs/mpl/doc/refmanual/bidirectional-iterator.html
right?

> 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.

What implies that?  OK, found it...

> It would seem that one should use iterator_category to determine if
> something is an iterator or not, 

That wouldn't work for STL iterators; can you explain why you would
expect it to work here?

> 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.

I'm sorry, I don't understand what you're trying to say about
deprecation.  Deprecation is a human activity; iterator_category<>
can't deprecate anything.  

> 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.
> 
> 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.

Well, we have a problem, in that a BidirectionalIterator is-not-a
ForwardIterator by MPL's requirements, even though the documentation
claims it is a refinement.  So MPL's concepts are just broken, and we
need to fix that.  Aleksey?

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com