iterator_traits and SFINAE

Discussion in 'C++' started by Marc, Sep 5, 2010.

  1. Marc

    Marc Guest

    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::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?
    Marc, Sep 5, 2010
    #1
    1. Advertising

  2. Marc

    SG Guest

    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.

    > 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
    SG, Sep 5, 2010
    #2
    1. Advertising

  3. Marc

    Marc Guest

    On 5 sep, 16:47, SG <> 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::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.
    Marc, Sep 5, 2010
    #3
  4. On Sep 5, 9:28 am, Marc <> 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::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?


    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::eek: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
    Howard Hinnant, Sep 5, 2010
    #4
  5. Marc

    SG Guest

    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
    SG, Sep 5, 2010
    #5
  6. Marc

    Marc Guest

    On 5 sep, 18:43, Howard Hinnant <> 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::eek:utput_iterator_tag.


    I am curious, what led you to add this second requirement?
    Marc, Sep 5, 2010
    #6
  7. On Sep 5, 1:49 pm, Marc <> wrote:
    > On 5 sep, 18:43, Howard Hinnant <> 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::eek: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
    Howard Hinnant, Sep 5, 2010
    #7
  8. Marc

    Guest

    On Sunday, September 5, 2010 11:43:36 AM UTC-5, Howard Hinnant wrote:
    > On Sep 5, 9:28 am, Marc <> 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::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?

    >
    > 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::eek: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
    , Jan 27, 2014
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Lieven

    iterator_traits

    Lieven, Dec 2, 2004, in forum: C++
    Replies:
    3
    Views:
    454
    Siemel Naran
    Dec 3, 2004
  2. chris
    Replies:
    8
    Views:
    486
    Tom Widmer
    Dec 10, 2004
  3. Jess
    Replies:
    3
    Views:
    642
    Zeppe
    Jun 28, 2007
  4. Ioannis Vranos

    typename iterator_traits::pointer

    Ioannis Vranos, Jan 24, 2008, in forum: C++
    Replies:
    10
    Views:
    699
    Ioannis Vranos
    Jan 25, 2008
  5. Replies:
    14
    Views:
    1,310
    Triple-DES
    Feb 12, 2008
Loading...

Share This Page