Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > iterator_traits and SFINAE

Reply
Thread Tools

iterator_traits and SFINAE

 
 
Marc
Guest
Posts: n/a
 
      09-05-2010
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?
 
Reply With Quote
 
 
 
 
SG
Guest
Posts: n/a
 
      09-05-2010
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: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.

> 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/1...ncepts-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
 
Reply With Quote
 
 
 
 
Marc
Guest
Posts: n/a
 
      09-05-2010
On 5 sep, 16:47, SG <(E-Mail Removed)> wrote:
> 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: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.
 
Reply With Quote
 
Howard Hinnant
Guest
Posts: n/a
 
      09-05-2010
On Sep 5, 9:28*am, Marc <(E-Mail Removed)> wrote:
> 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/lib...clude/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
 
Reply With Quote
 
SG
Guest
Posts: n/a
 
      09-05-2010
On 5 Sep., 18:31, Marc wrote:
> 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
 
Reply With Quote
 
Marc
Guest
Posts: n/a
 
      09-05-2010
On 5 sep, 18:43, Howard Hinnant <(E-Mail Removed)> wrote:
> 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?
 
Reply With Quote
 
Howard Hinnant
Guest
Posts: n/a
 
      09-05-2010
On Sep 5, 1:49*pm, Marc <(E-Mail Removed)> wrote:
> On 5 sep, 18:43, Howard Hinnant <(E-Mail Removed)> wrote:
>
>
> > 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...


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

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


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
 
Reply With Quote
 
kaballo@gmail.com
Guest
Posts: n/a
 
      01-27-2014
On Sunday, September 5, 2010 11:43:36 AM UTC-5, Howard Hinnant wrote:
> On Sep 5, 9:28*am, Marc <(E-Mail Removed)> wrote:
> > 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/lib...clude/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,
--
Agustín K-ballo Bergé.-
http://talesofcpp.fusionfenix.com
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
iterator_traits::value_type on back_insert_iterator - returns void anto.anish@gmail.com C++ 14 02-12-2008 11:14 AM
typename iterator_traits::pointer Ioannis Vranos C++ 10 01-25-2008 12:25 AM
help on std::iterator_traits? Jess C++ 3 06-28-2007 03:01 PM
Purpose of iterator_traits::value_type chris C++ 8 12-10-2004 04:02 PM
iterator_traits Lieven C++ 3 12-03-2004 06:33 AM



Advertisments