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

  2. Marc

    SG Guest

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

  3. Marc

    Marc Guest

    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.
    As long as I keep it "the way it is" for all working code...
    The removal of concepts didn't leave much time to polish alternatives
    in the library.
    Indeed, I already started using those.
    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. 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

    Oh, ok. Yes, I did misread your post. Sorry for the trouble.

    Cheers!
    SG
     
    SG, Sep 5, 2010
    #5
  6. Marc

    Marc Guest

    Glad to hear it :)
    :-(
    Means we can't rely on it in portable code...
    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?
     
    Marc, Sep 5, 2010
    #6
  7. <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.
    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

    kaballo Guest

    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,
     
    kaballo, Jan 27, 2014
    #8
    1. Advertisements

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.