Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Purpose of iterator_traits::value_type

Reply
Thread Tools

Purpose of iterator_traits::value_type

 
 
chris
Guest
Posts: n/a
 
      12-09-2004
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
 
Reply With Quote
 
 
 
 
Victor Bazarov
Guest
Posts: n/a
 
      12-09-2004
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
 
Reply With Quote
 
 
 
 
chris
Guest
Posts: n/a
 
      12-09-2004
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
 
Reply With Quote
 
Victor Bazarov
Guest
Posts: n/a
 
      12-09-2004
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
 
Reply With Quote
 
chris
Guest
Posts: n/a
 
      12-09-2004
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
 
Reply With Quote
 
Victor Bazarov
Guest
Posts: n/a
 
      12-09-2004
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
 
Reply With Quote
 
Tom Widmer
Guest
Posts: n/a
 
      12-10-2004
On Thu, 09 Dec 2004 17:13:19 +0000, chris <(E-Mail Removed)> 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
 
Reply With Quote
 
chris
Guest
Posts: n/a
 
      12-10-2004
Tom Widmer wrote:
> On Thu, 09 Dec 2004 17:13:19 +0000, chris <(E-Mail Removed)> 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
 
Reply With Quote
 
Tom Widmer
Guest
Posts: n/a
 
      12-10-2004
On Fri, 10 Dec 2004 14:13:05 +0000, chris <(E-Mail Removed)> 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
 
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
What's the purpose of Download Manager in FF charleswalters@no-email.com Firefox 10 04-27-2005 08:17 PM
In Esposito's book, what's the purpose of going to session_expired.aspx? Rod ASP .Net 3 09-27-2004 01:50 AM
Visual Web Developer 2005 Express SCREWS UP YOUR CODE on PURPOSE...STOP TOUCHING MY CODE, MICROSOFT!!!! ik ASP .Net 6 07-16-2004 05:28 PM
HERE WE GO AGAIN, Visual Web Developer 2005 Express SCREWS UP YOUR CODE on PURPOSE...STOP TOUCHING MY CODE, MICROSOFT!!!! ik ASP .Net 8 07-09-2004 04:52 AM
What is the purpose of FormsAuthentication.SignOut()? Ali ASP .Net 1 01-29-2004 02:08 PM



Advertisments