Purpose of iterator_traits::value_type

Discussion in 'C++' started by chris, Dec 9, 2004.

  1. chris

    chris Guest

    I tried to post this to comp.std.c++ some time ago, but for some reason
    I aren't getting any automatic confirmation. I thought I would therefore
    post it here.

    Some time ago I submitted what is now Defect Report 484 on the standard
    library. I'm beginning to wonder if I've just misunderstood the purpose
    of iterator_traits::value_type.

    I constructed an input iterator where *i returns an int, but I set
    iterator_traits::value_type to bool. This should be valid, as operater*
    only has to be convertable to the value_type. I then tried the following:

    Have an input iterator iterate through the values {2,3,5}, and use
    std::find to find a "true". On all the compilers I have access to this
    failed, as the compilers simply compared the ints in the array to
    boolean true, which returns false.

    Reading the standard, I can't decide if this is correct behaviour or
    not.. on one hand it looks like this is exactly what std::find claims to
    do (find the first element where *a==true). On the other hand it seems
    reasonable that an implementation can assume it can copy dereferenced
    iterators in a variable of type iterator_traits::value_type, and if it
    did so the returned answer would be different.

    Chris
    chris, Dec 9, 2004
    #1
    1. Advertising

  2. chris wrote:
    > I tried to post this to comp.std.c++ some time ago, but for some reason
    > I aren't getting any automatic confirmation. I thought I would therefore
    > post it here.
    >
    > Some time ago I submitted what is now Defect Report 484 on the standard
    > library. I'm beginning to wonder if I've just misunderstood the purpose
    > of iterator_traits::value_type.
    >
    > I constructed an input iterator where *i returns an int, but I set
    > iterator_traits::value_type to bool. This should be valid, as operater*
    > only has to be convertable to the value_type. I then tried the following:
    >
    > Have an input iterator iterate through the values {2,3,5}, and use
    > std::find to find a "true". On all the compilers I have access to this
    > failed, as the compilers simply compared the ints in the array to
    > boolean true, which returns false.
    >
    > Reading the standard, I can't decide if this is correct behaviour or
    > not.. on one hand it looks like this is exactly what std::find claims to
    > do (find the first element where *a==true). On the other hand it seems
    > reasonable that an implementation can assume it can copy dereferenced
    > iterators in a variable of type iterator_traits::value_type, and if it
    > did so the returned answer would be different.


    I am not sure where you get the latter (the "on the other hand") thing.
    The *a has a particular type, and you defined it to be 'int' (I suppose
    you do return corresponding value there). Unless there is no equality
    operator for the type returned from operator*, there is no need to copy.

    No implementation should perform unnecessary copying.

    V
    Victor Bazarov, Dec 9, 2004
    #2
    1. Advertising

  3. chris

    chris Guest

    Victor Bazarov wrote:
    > chris wrote:
    >
    >> I tried to post this to comp.std.c++ some time ago, but for some
    >> reason I aren't getting any automatic confirmation. I thought I would
    >> therefore post it here.
    >>
    >> Some time ago I submitted what is now Defect Report 484 on the
    >> standard library. I'm beginning to wonder if I've just misunderstood
    >> the purpose of iterator_traits::value_type.
    >>
    >> I constructed an input iterator where *i returns an int, but I set
    >> iterator_traits::value_type to bool. This should be valid, as
    >> operater* only has to be convertable to the value_type. I then tried
    >> the following:
    >>
    >> Have an input iterator iterate through the values {2,3,5}, and use
    >> std::find to find a "true". On all the compilers I have access to this
    >> failed, as the compilers simply compared the ints in the array to
    >> boolean true, which returns false.
    >>
    >> Reading the standard, I can't decide if this is correct behaviour or
    >> not.. on one hand it looks like this is exactly what std::find claims
    >> to do (find the first element where *a==true). On the other hand it
    >> seems reasonable that an implementation can assume it can copy
    >> dereferenced iterators in a variable of type
    >> iterator_traits::value_type, and if it did so the returned answer
    >> would be different.

    >
    >
    > I am not sure where you get the latter (the "on the other hand") thing.
    > The *a has a particular type, and you defined it to be 'int' (I suppose
    > you do return corresponding value there). Unless there is no equality
    > operator for the type returned from operator*, there is no need to copy.
    >
    > No implementation should perform unnecessary copying.
    >

    No implementation should. However are you saying that NO implementation
    should EVER copy a dereferenced iterator to a variable of type
    iterator_traits::value_type where the iterator is an input_iterator?
    Because that seems like quite a strong condition, and I didn't realise
    it was true.

    Chris
    chris, Dec 9, 2004
    #3
  4. chris wrote:
    > Victor Bazarov wrote:
    >
    >> chris wrote:
    >>
    >>> I tried to post this to comp.std.c++ some time ago, but for some
    >>> reason I aren't getting any automatic confirmation. I thought I would
    >>> therefore post it here.
    >>>
    >>> Some time ago I submitted what is now Defect Report 484 on the
    >>> standard library. I'm beginning to wonder if I've just misunderstood
    >>> the purpose of iterator_traits::value_type.
    >>>
    >>> I constructed an input iterator where *i returns an int, but I set
    >>> iterator_traits::value_type to bool. This should be valid, as
    >>> operater* only has to be convertable to the value_type. I then tried
    >>> the following:
    >>>
    >>> Have an input iterator iterate through the values {2,3,5}, and use
    >>> std::find to find a "true". On all the compilers I have access to
    >>> this failed, as the compilers simply compared the ints in the array
    >>> to boolean true, which returns false.
    >>>
    >>> Reading the standard, I can't decide if this is correct behaviour or
    >>> not.. on one hand it looks like this is exactly what std::find claims
    >>> to do (find the first element where *a==true). On the other hand it
    >>> seems reasonable that an implementation can assume it can copy
    >>> dereferenced iterators in a variable of type
    >>> iterator_traits::value_type, and if it did so the returned answer
    >>> would be different.

    >>
    >>
    >>
    >> I am not sure where you get the latter (the "on the other hand") thing.
    >> The *a has a particular type, and you defined it to be 'int' (I suppose
    >> you do return corresponding value there). Unless there is no equality
    >> operator for the type returned from operator*, there is no need to copy.
    >>
    >> No implementation should perform unnecessary copying.
    >>

    > No implementation should. However are you saying that NO implementation
    > should EVER copy a dereferenced iterator to a variable of type
    > iterator_traits::value_type where the iterator is an input_iterator?
    > Because that seems like quite a strong condition, and I didn't realise
    > it was true.


    I think the copying has to be approached on the case to case basis and
    decided when such copying is in fact taking place. 'std::find' does not
    seem one of those places, since its semantics are well defined.

    I was thinking of a possible example where copying is necessary even with
    'std::find', and the only thing comes to mind is the absence of operator==
    for the type returned from operator*, and instead existence of operator==
    for the 'iterator_traits::value_type'. Since you have your example
    environment completely set up, could you test it with

    struct noequality { };
    struct hasequality {
    bool operator==(hasequality const&) const;
    hasequality();
    hasequality(noequality); // parameterized c-tor
    };

    struct youriterator {
    ...
    noequality operator *();
    };

    ... iterator_traits<youriterator> {
    typedef hasequality value_type;
    ...
    };

    Which should mean that 'youriterator' returns 'noequality', which is in
    turn convertible to 'hasequality', which does have operator== defined.

    I am interested to see if the compiler will force the conversion. I do
    not expect it to, though. For the second exercise, remove the operator==
    from the 'hasequality' and define a global one:

    bool operator==(hasequality const&, hasequality const&);

    For non-members user conversions of operands are tried during lookup.

    See what I mean?

    V
    Victor Bazarov, Dec 9, 2004
    #4
  5. chris

    chris Guest

    Victor Bazarov wrote:
    > chris wrote:
    >
    >> Victor Bazarov wrote:
    >>
    >>> chris wrote:
    >>>
    >>>> I tried to post this to comp.std.c++ some time ago, but for some
    >>>> reason I aren't getting any automatic confirmation. I thought I
    >>>> would therefore post it here.
    >>>>
    >>>> Some time ago I submitted what is now Defect Report 484 on the
    >>>> standard library. I'm beginning to wonder if I've just misunderstood
    >>>> the purpose of iterator_traits::value_type.
    >>>>
    >>>> I constructed an input iterator where *i returns an int, but I set
    >>>> iterator_traits::value_type to bool. This should be valid, as
    >>>> operater* only has to be convertable to the value_type. I then tried
    >>>> the following:
    >>>>
    >>>> Have an input iterator iterate through the values {2,3,5}, and use
    >>>> std::find to find a "true". On all the compilers I have access to
    >>>> this failed, as the compilers simply compared the ints in the array
    >>>> to boolean true, which returns false.
    >>>>
    >>>> Reading the standard, I can't decide if this is correct behaviour or
    >>>> not.. on one hand it looks like this is exactly what std::find
    >>>> claims to do (find the first element where *a==true). On the other
    >>>> hand it seems reasonable that an implementation can assume it can
    >>>> copy dereferenced iterators in a variable of type
    >>>> iterator_traits::value_type, and if it did so the returned answer
    >>>> would be different.
    >>>
    >>>
    >>>
    >>>
    >>> I am not sure where you get the latter (the "on the other hand") thing.
    >>> The *a has a particular type, and you defined it to be 'int' (I suppose
    >>> you do return corresponding value there). Unless there is no equality
    >>> operator for the type returned from operator*, there is no need to copy.
    >>>
    >>> No implementation should perform unnecessary copying.
    >>>

    >> No implementation should. However are you saying that NO
    >> implementation should EVER copy a dereferenced iterator to a variable
    >> of type iterator_traits::value_type where the iterator is an
    >> input_iterator? Because that seems like quite a strong condition, and
    >> I didn't realise it was true.

    >
    >
    > I think the copying has to be approached on the case to case basis and
    > decided when such copying is in fact taking place. 'std::find' does not
    > seem one of those places, since its semantics are well defined.
    >

    Hmm.. I'm not convinced that's good enough. Saying "case by case basis"
    is clearly no good with regards the standard (unless of course someone
    goes through the whole standard, and does the case-by-case comparison).
    I wonder if "convertable to T" should just be tightened a list, like
    "one of const T, T, T&, const T&", or some such? Is that what was meant...

    <snip example>
    actually, this seems to work fine :)

    Chris
    chris, Dec 9, 2004
    #5
  6. chris wrote:
    > Victor Bazarov wrote:
    >
    >> chris wrote:
    >>
    >>> Victor Bazarov wrote:
    >>>
    >>>> chris wrote:
    >>>>
    >>>>> I tried to post this to comp.std.c++ some time ago, but for some
    >>>>> reason I aren't getting any automatic confirmation. I thought I
    >>>>> would therefore post it here.
    >>>>>
    >>>>> Some time ago I submitted what is now Defect Report 484 on the
    >>>>> standard library. I'm beginning to wonder if I've just
    >>>>> misunderstood the purpose of iterator_traits::value_type.
    >>>>>
    >>>>> I constructed an input iterator where *i returns an int, but I set
    >>>>> iterator_traits::value_type to bool. This should be valid, as
    >>>>> operater* only has to be convertable to the value_type. I then
    >>>>> tried the following:
    >>>>>
    >>>>> Have an input iterator iterate through the values {2,3,5}, and use
    >>>>> std::find to find a "true". On all the compilers I have access to
    >>>>> this failed, as the compilers simply compared the ints in the array
    >>>>> to boolean true, which returns false.
    >>>>>
    >>>>> Reading the standard, I can't decide if this is correct behaviour
    >>>>> or not.. on one hand it looks like this is exactly what std::find
    >>>>> claims to do (find the first element where *a==true). On the other
    >>>>> hand it seems reasonable that an implementation can assume it can
    >>>>> copy dereferenced iterators in a variable of type
    >>>>> iterator_traits::value_type, and if it did so the returned answer
    >>>>> would be different.
    >>>>
    >>>>
    >>>>
    >>>>
    >>>>
    >>>> I am not sure where you get the latter (the "on the other hand") thing.
    >>>> The *a has a particular type, and you defined it to be 'int' (I suppose
    >>>> you do return corresponding value there). Unless there is no equality
    >>>> operator for the type returned from operator*, there is no need to
    >>>> copy.
    >>>>
    >>>> No implementation should perform unnecessary copying.
    >>>>
    >>> No implementation should. However are you saying that NO
    >>> implementation should EVER copy a dereferenced iterator to a variable
    >>> of type iterator_traits::value_type where the iterator is an
    >>> input_iterator? Because that seems like quite a strong condition, and
    >>> I didn't realise it was true.

    >>
    >>
    >>
    >> I think the copying has to be approached on the case to case basis and
    >> decided when such copying is in fact taking place. 'std::find' does not
    >> seem one of those places, since its semantics are well defined.
    >>

    > Hmm.. I'm not convinced that's good enough. Saying "case by case basis"
    > is clearly no good with regards the standard (unless of course someone
    > goes through the whole standard, and does the case-by-case comparison).
    > I wonder if "convertable to T" should just be tightened a list, like
    > "one of const T, T, T&, const T&", or some such? Is that what was meant...


    For every algorithm that has its semantics defined in the standard, there
    is no need to use "case by case basis" approach. Just like with 'find',
    those things shall not have copying (or, reverse, shall have copying) as
    part of the overall algorithm, but they are already there. Such approach
    will be needed (IMHO) for all cases outside the Standard, for which
    semantics are either invented by the programmer or simply not mentioned in
    the Standard.

    OTOH, I am probably wrong again, and today I'm just too lazy to think any
    harder...

    > <snip example>
    > actually, this seems to work fine :)


    Well... Good! :)

    V
    Victor Bazarov, Dec 9, 2004
    #6
  7. chris

    Tom Widmer Guest

    On Thu, 09 Dec 2004 17:13:19 +0000, chris <> wrote:

    >I tried to post this to comp.std.c++ some time ago, but for some reason
    >I aren't getting any automatic confirmation. I thought I would therefore
    >post it here.
    >
    >Some time ago I submitted what is now Defect Report 484 on the standard
    >library. I'm beginning to wonder if I've just misunderstood the purpose
    >of iterator_traits::value_type.
    >
    >I constructed an input iterator where *i returns an int, but I set
    >iterator_traits::value_type to bool. This should be valid, as operater*
    >only has to be convertable to the value_type.


    But the "value type" of an iterator is defined to be the type of the
    "value" *it. I assume by taking about the "value", we can drop
    references desired. See 24.1/1. 24.3.1 seems to be pretty clear that
    value_type must be *the* value type of the iterator, not any type T
    over which the iterator meets the input iterator requirements. IMHO.

    > I then tried the following:
    >
    >Have an input iterator iterate through the values {2,3,5}, and use
    >std::find to find a "true". On all the compilers I have access to this
    >failed, as the compilers simply compared the ints in the array to
    >boolean true, which returns false.
    >
    >Reading the standard, I can't decide if this is correct behaviour or
    >not.. on one hand it looks like this is exactly what std::find claims to
    >do (find the first element where *a==true). On the other hand it seems
    >reasonable that an implementation can assume it can copy dereferenced
    >iterators in a variable of type iterator_traits::value_type, and if it
    >did so the returned answer would be different.


    Not if iterator_traits::value_type is defined to be *the* value type
    of the iterator, not just some type "T" over which it passes the
    iterator requirements.

    Tom
    Tom Widmer, Dec 10, 2004
    #7
  8. chris

    chris Guest

    Tom Widmer wrote:
    > On Thu, 09 Dec 2004 17:13:19 +0000, chris <> wrote:
    >
    >
    >>I tried to post this to comp.std.c++ some time ago, but for some reason
    >>I aren't getting any automatic confirmation. I thought I would therefore
    >>post it here.
    >>
    >>Some time ago I submitted what is now Defect Report 484 on the standard
    >>library. I'm beginning to wonder if I've just misunderstood the purpose
    >>of iterator_traits::value_type.
    >>
    >>I constructed an input iterator where *i returns an int, but I set
    >>iterator_traits::value_type to bool. This should be valid, as operater*
    >>only has to be convertable to the value_type.

    >
    >
    > But the "value type" of an iterator is defined to be the type of the
    > "value" *it. I assume by taking about the "value", we can drop
    > references desired. See 24.1/1. 24.3.1 seems to be pretty clear that
    > value_type must be *the* value type of the iterator, not any type T
    > over which the iterator meets the input iterator requirements. IMHO.
    >


    I was getting my reading from:

    24.4.1 1: "A class or a built-in type X satisfies the requirements of an
    input iterator for the value type T..."

    Table 72:

    "*a convertible to T"

    ....

    "value_type if the value type of the iterator"

    So I read that *a has to be only convertable to T, and that *a does not
    have to be the same type as iterator_traits::value_type.

    While we are on the subject of input iterators, out of interest what is
    the opinion on the Note after table 72:

    "Note: For input iterators, a==b does not imply ++a == ++b ...."

    Actually, is ++a == ++b a well-defined statement??

    If we look at ++r, then it looks like it is saying that the pre is "r is
    dererferencable", and the post containes "any copies of the previous
    value of r are no longer required to be dereferenceable".

    Therefore I think that this statement is a) undefined and b) not helpful..

    any thoughts? :)

    Chris
    chris, Dec 10, 2004
    #8
  9. chris

    Tom Widmer Guest

    On Fri, 10 Dec 2004 14:13:05 +0000, chris <> wrote:

    >"value_type if the value type of the iterator"
    >
    >So I read that *a has to be only convertable to T, and that *a does not
    >have to be the same type as iterator_traits::value_type.


    Yeah, if you miss the very start of 24.1 then it does read that way.
    But there definitely is a difference between the family of types, T,
    that an iterator is a valid input iterator for, and the value type of
    that iterator (which will of course be a member of the set of Ts).

    >While we are on the subject of input iterators, out of interest what is
    >the opinion on the Note after table 72:
    >
    >"Note: For input iterators, a==b does not imply ++a == ++b ...."
    >
    >Actually, is ++a == ++b a well-defined statement??


    Nope, not in general, although it is well-formed at least.

    >If we look at ++r, then it looks like it is saying that the pre is "r is
    >dererferencable", and the post containes "any copies of the previous
    >value of r are no longer required to be dereferenceable".
    >
    >Therefore I think that this statement is a) undefined and b) not helpful..


    Certainly agreed on the a) bit.

    Tom
    Tom Widmer, Dec 10, 2004
    #9
    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. Jess
    Replies:
    3
    Views:
    643
    Zeppe
    Jun 28, 2007
  3. Ioannis Vranos

    typename iterator_traits::pointer

    Ioannis Vranos, Jan 24, 2008, in forum: C++
    Replies:
    10
    Views:
    699
    Ioannis Vranos
    Jan 25, 2008
  4. Replies:
    14
    Views:
    1,312
    Triple-DES
    Feb 12, 2008
  5. Taras_96
    Replies:
    0
    Views:
    376
    Taras_96
    Apr 1, 2008
Loading...

Share This Page