Re: [boost] Report from Berlin C++ Standards Committee meeting

From: Howard Hinnant (howard.hinnant_at_[hidden])
Date: 2006-04-15 16:36:51

On Apr 15, 2006, at 3:06 PM, Daniel Walker wrote:

> On 4/15/06, David Abrahams <dave_at_[hidden]> wrote:
>> "Daniel Walker" <daniel.j.walker_at_[hidden]> writes:
>>
>>> On 4/11/06, David Abrahams <dave_at_[hidden]> wrote:
>>>> Thorsten Ottosen <thorsten.ottosen_at_[hidden]> writes:
>>>>
>>>>>> cannot have overloads (in C++98) taking containers/ranges:
>>>>>>
>>>>>>    fn( Iterator first, Iterator last )
>>>>>>    fn( Iterator first, Iterator last, Functor f )
>>>>>>    fn( Range rng )
>>>>>>    fn( Range rng, Functor f )
>>>>>>
>>>>>> as the last overload is ambiguous. Concepts will allow this to  
>>>>>> be resolved
>>>>>> as a Functor will not match the Iterator requirements :).
>>>>>
>>>>> you can use enable_if on the latter and disable it the two  
>>>>> types are the
>>>>> same.
>>>>
>>>> Not if you happen to have a type that is both a valid range and a
>>>> valid function object.
>>>>
>>>> Yes, that's a corner case, but it's the corner of a large floating
>>>> block of ice.
>>>
>>> For this idiom, I use boost::iterator_range like so,
>>>
>>> fn( Iterator first, Iterator last )
>>> fn( Iterator first, Iterator last, Functor f )
>>> fn( boost::iterator_range<Iterator> rng )
>>> fn( boost::iterator_range<Iterator> rng,  Functor f )
>>
>> This is not generic.  Now you can't pass other valid Ranges
>> (e.g. std::vector<T>) as the first argument to fn.
>
> Yeah, I know. This is just a work-around because the generic version
> isn't possible today due to the overload ambiguity. You can indirectly
> use the functions with other valid Ranges like vector, but it's a
> hassle because you first have to convert them using
> make_iterator_range(). In some circumstances, for the time being, this
> may be acceptable for this particular idiom (overloading algorithms to
> take both iterators and ranges), but really I agree that it further
> illustrates the need for in-language support for concepts in a future
> version of C++ in order to make the overloads generic.

Actually in this particular case, all we need is a more smartly  
designed std::iterator_traits class:

Spec:
---
template <class Iterator>
struct iterator_traits
{
};
However if Iterator has the nested types: difference_type,  
value_type, pointer, reference and iterator_category, and if  
Iterator::iterator_category (if it exists) is implicitly convertible  
to either std::input_iterator_tag, or std::output_iterator_tag, then  
the struct iterator_traits is instead:
template <class Iterator>
struct iterator_traits
{
     typedef typename Iterator::difference_type   difference_type;
     typedef typename Iterator::value_type        value_type;
     typedef typename Iterator::pointer           pointer;
     typedef typename Iterator::reference         reference;
     typedef typename Iterator::iterator_category iterator_category;
};
Plus the pointer specializations...
Plus any user-defined specializations...
---
Such an iterator_traits is easy to implement today with has_member_*  
and is_convertible.  And now you can say iterator_traits<any type at  
all>.  The instantiation always compiles and may or may not have the  
nested typedefs.
Then you can make an is_input_iterator trait:
A type T is an input iterator if iterator_traits<T> has a member  
called iterator_category that is convertible to std::input_iterator_tag.
enable_if your fn with is_input_iterator<InputIterator>, and you're  
done.
You can get most of the way there with today's iterator_traits.   
You'll miss user-defined iterators that specialize iterator_traits  
instead of containing the nested types directly (which is practically  
no types at all).  Just change is_iterator to look for the nested  
types, and then specialize is_iterator for pointer types.  Then you  
can build is_input_iterator on top of is_iterator.
That's not an argument against concepts.  Its just a fun and useful  
exercise to build is_input_iterator<T>.  Maybe someone can see a  
better way to do it with today's iterator_traits than what I've  
described.
-Howard