iterator_traits and SFINAE

[Marc]

Hello,

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:ointer 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:ointer 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

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]

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:ointer 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]

Hello,

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:ointer 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?

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:utput_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:utput_iterator_tag.

I am curious, what led you to add this second requirement?

 

[Howard Hinnant]

:-(
Means we can't rely on it in portable code...

<nod> Noted. If enough people care enough to complain to their
vendor, then it will become a de-facto standard, and will likely be
standardized in the next round.

That's also the only one I test in real code, I was trying to cover
all bases here.



I am curious, what led you to add this second requirement?

Just paranoia, combined with ease of implementation. I didn't want to
completely reserve the spelling "iterator_category" across all
namespaces and applications. But if you have a nested type spelled
"iterator_category" /and/ it is implicitly convertible to one of the
std-defined iterator tags, then you probably really do intend that
iterator_category serve the std-defined purpose (as opposed to just
accidentally having the same name used for another purpose).

-Howard

 

[kaballo]

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:utput_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

The addition of `next`/`prev` in C++11 causes problems with unqualified uses of those names when a type from the std namespace is involved, which IMHOare not vanishingly rare cases.

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,