iterator_traits and SFINAE
Marc
the standard defines iterator_traits with:
namespace std {
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 two partial specializations for pointers.
Since the typedefs are always present, iterator_traits can't be
instantiated with a non-iterator template argument, and thus
iterator_traits can't reliably be used in the signature of a function
(it won't fall in the SFINAE category).
On the other hand, if iterator_traits was specified as an empty class
(no typedef) when Iterator::* don't exist (and Iterator is not a
pointer), it seems to me that iterator_traits would become usable for
sfinae purposes (std::distance wouldn't break user-defined distance
functions any more) and no currently valid code would break.
Several libraries already contain some kind of is_iterator helper; the
implementation would be almost the same and the helper would become
redundant.
Any opinion?
SG
>
> the standard defines iterator_traits with:
> namespace std {
> 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 two partial specializations for pointers.
> On the other hand, if iterator_traits was specified as an empty
> class (no typedef) when Iterator::* don't exist (and Iterator is
> not a pointer), it seems to me that iterator_traits would become
> usable for sfinae purposes (std::distance wouldn't break user-defined
> distance functions any more) and no currently valid code would break.
Sure, it would. Consider an iterator class X that provides these
typedefs. Given the definition of iterator_traits there is no need to
a specialization of iterator_traits. So, if your suggestion was to be
adopted, code that tries to use iterator_traits<X> would break.
> Any opinion?
I think it's too late in the game. std::iterator_traits is the way it
is.
Actually, I suggested something similar for the not-yet-standard
std::result_of so it can be used to constrain function templates. But
this would have made std::result_of an "unusual" class template. The
idea didn't get much love.
With other C++0x features around there will probably pop up other
idioms for constraining function templates (until we get the real
deal). For example, you can use variadic templates, decltype and
declval to check for many expressions:
// usage example
template<class Iter>
typeame last_type<
decltype( declval<ostream&>() << *declval<Iter&>() ),
decltype( ++declval<Iter&> ),
void>::type show(Iter beg, Iter end)
{
while (beg!=end) {
cout << ' ' << *beg;
++beg;
}
cout << '\n';
}
(where last_type is a class template that extracts the last type
parameter of the argument type pack)
With similar techniques you can write custom traits classes that only
provide some typedefs in case some expression "works out" to emulate a
lot of what concepts tried to do. I actually expect to see more
"concept emulation libraries" with respect to function template
constraining. Here's another example of how it could look like:
template<class Iter, REQUIRES(ForwardIterator<Iter>)>
void show(Iter beg, Iter end);
(taken from http://pizer.wordpress.com/2009/08/16/c0x-no-concepts-no-fun/
)
The only thing left where iterator_traits is any good is the iterator
category since, for example, it's impossible to distinguish between
input and forward terators just by checking "structural properties".
Cheers!
SG
Marc
> On 5 Sep., 15:28, Marc wrote:
> > the standard defines iterator_traits with:
> > namespace std {
> > 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 two partial specializations for pointers.
> > [...]
> > On the other hand, if iterator_traits was specified as an empty
> > class (no typedef) when Iterator::* don't exist (and Iterator is
> > not a pointer), it seems to me that iterator_traits would become
> > usable for sfinae purposes (std::distance wouldn't break user-defined
> > distance functions any more) and no currently valid code would break.
>
> Sure, it would. Consider an iterator class X that provides these
> typedefs. Given the definition of iterator_traits there is no need to
> a specialization of iterator_traits. So, if your suggestion was to be
> adopted, code that tries to use iterator_traits<X> would break.
Er, you misread my post (or I wasn't clear enough). What I suggest is:
- for pointers, provide the specialized typedefs as currently;
- for classes that provide the 5 typedefs, "forward" them as
currently;
- for other types, instead of 5 broken typedefs, have an empty class.
Only the third category, which by definition concerns only code that
didn't work, changes.
> I think it's too late in the game. std::iterator_traits is the way it
> is.
As long as I keep it "the way it is" for all working code...
> Actually, I suggested something similar for the not-yet-standard
> std::result_of so it can be used to constrain function templates. But
> this would have made std::result_of an "unusual" class template. The
> idea didn't get much love.
The removal of concepts didn't leave much time to polish alternatives
in the library.
> With other C++0x features around there will probably pop up other
> idioms for constraining function templates (until we get the real
> deal). For example, you can use variadic templates, decltype and
> declval to check for many expressions:
Indeed, I already started using those.
> With similar techniques you can write custom traits classes that only
> provide some typedefs in case some expression "works out" to emulate a
> lot of what concepts tried to do. I actually expect to see more
> "concept emulation libraries" with respect to function template
> constraining.
Indeed again.
One of the reasons I am specifically interested in iterator_traits is
that because of std::distance, the name "distance" becomes unsafe for
user-defined functions. There are a few other functions that have the
same issue.
Howard Hinnant
I've long thought that this is the quality way to implement
iterator_traits. I did so for the Metrowerks/Motorola/Freescale
CodeWarrior std::lib, and I've done so again here:
http://libcxx.llvm.org/
http://llvm.org/svn/llvm-project/libcxx/trunk/include/iterator
I also failed to try to standardize this technique. It never got high
enough on my priority queue, and my impression of the chances of
successful standardization consistently remained low. But I like it
exactly for all of the reasons you state.
This implementation of your idea keys only on the nested
iterator_category type. For X to qualify as an iterator (and thus for
iterator_traits<X> to be a non-empty class):
1. X::iterator_category must exist, and
2. X::iterator_category must be implicitly convertible to either
std::input_iterator_tag or std::output_iterator_tag.
Using these rules, I've never come across a case in the wild where
this design breaks code. Though breakage is certainly theoretically
possible (just vanishingly rare in my experience).
-Howard
SG
> Er, you misread my post (or I wasn't clear enough).
> What I suggest is:
> - for pointers, provide the specialized typedefs as currently;
> - for classes that provide the 5 typedefs, "forward" them as
> currently;
> - for other types, instead of 5 broken typedefs, have an empty class.
Oh, ok. Yes, I did misread your post. Sorry for the trouble.
Cheers!
SG
Marc
> I've long thought that this is the quality way to implement
> iterator_traits. I did so for the Metrowerks/Motorola/Freescale
> CodeWarrior std::lib, and I've done so again here:
Glad to hear it :-)
> I also failed to try to standardize this technique. It never got high
> enough on my priority queue, and my impression of the chances of
> successful standardization consistently remained low.
:-(
Means we can't rely on it in portable code...
> This implementation of your idea keys only on the nested
> iterator_category type.
That's also the only one I test in real code, I was trying to cover
all bases here.
> For X to qualify as an iterator (and thus for
> iterator_traits<X> to be a non-empty class):
>
> 1. X::iterator_category must exist, and
> 2. X::iterator_category must be implicitly convertible to either
> std::input_iterator_tag or std::output_iterator_tag.
I am curious, what led you to add this second requirement?
kab...@gmail.com
I found this post while trying to figure out a regression in Boost.Fusion caused exactly by this issue. The test case compiles fine on Clang but it fails with a compilation error as it should on MSVC, which was a vanishingly rare experience for me.
Regards,
--
Agustín K-ballo Bergé.-
http://talesofcpp.fusionfenix.com