Purpose of iterator_traits::value_type

[chris]

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

 

[Victor Bazarov]

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

 

[chris]

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

 

[Victor Bazarov]

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

 

[chris]

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

 

[Victor Bazarov]

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

 

[Tom Widmer]

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

 

[chris]

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

 

[Tom Widmer]

"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