iterator dereference requirements
liftmaster
INTERNATIONAL
STANDARD
ISO/IEC
14882
First edition
1998-09-01
this gives as a requirement for bidirectional iterators that dereferencing
returns A type T&
then for random access iterators, in addition to the specifications for
bidirectional iterators, among other things it says that operator[] a[n]
should be equivilent to *(a+n) but only specifies the result of operator[]
as being convertible to T (not that it is specifically T&).
Is this a mistake?
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Greg Herlihy
liftmaster wrote:
> I am working from
>
>
> INTERNATIONAL
> STANDARD
> ISO/IEC
> 14882
> First edition
> 1998-09-01
>
>
> this gives as a requirement for bidirectional iterators that dereferencing
> returns A type T&
>
> then for random access iterators, in addition to the specifications for
> bidirectional iterators, among other things it says that operator[] a[n]
> should be equivilent to *(a+n) but only specifies the result of operator[]
> as being convertible to T (not that it is specifically T&).
>
> Is this a mistake?
No mistake, at least, not yet. :) See open library issue #299 at
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1830.html for
a complete discussion.
Greg
Matthias Hofmann
news:d87584f4f0470aff...@localhost.talkaboutprogramming.com...
> I am working from
>
>
> INTERNATIONAL
> STANDARD
> ISO/IEC
> 14882
> First edition
> 1998-09-01
>
>
> this gives as a requirement for bidirectional iterators that dereferencing
> returns A type T&
Actually, this is the requirement for forward iterators. But bidirectional
operators are required to satisfy the requirements for forward iterators, so
your statement is correct.
> then for random access iterators, in addition to the specifications for
> bidirectional iterators
This is the answer to your question. Random access iterators are required to
satisfy the requirements for bidirectional iterators (which in turn are
required to satisfy the requirements for forward iterators), so
dereferencing a random access iterator returns a T&.
> among other things it says that operator[] a[n]
> should be equivilent to *(a+n) but only specifies the result of operator[]
> as being convertible to T (not that it is specifically T&).
>
> Is this a mistake?
No. As I have tried to explain above, random access iterators "inherit"
their requirements from bidirectional iterators, which in turn "inherit"
their requirements from forward iterators.
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
Greg Herlihy
The portion of the Standard quoted above shows that one of the
requirements for a random access iterator is not in fact inherited from
a bidirectional iterator. That is the whole crux of the issue. And by
your own reasoning, the requirement in question could only be a
mistake.
Since neither forward nor bidirectional iterators implement the []
operator, the Standard states that an expression like
a[n]
(a is a random access iterator) should be "equivalent" to
*(a+n)
But instead of being equivalent, the Standard specifies that the return
type for operator[] can be any type that is "convertible to T". This is
far more lax stipulation than the requirement for a bidirectional
iterator's operator* (which must return a T&).
A class is allowed to tighten its inherited requirements, but is not
allowed to liberalize them (otherwise they would not be called
"requirements").
Greg
David Abrahams
>> No. As I have tried to explain above, random access iterators "inherit"
>> their requirements from bidirectional iterators, which in turn "inherit"
>> their requirements from forward iterators.
>
> The portion of the Standard quoted above shows that one of the
> requirements for a random access iterator is not in fact inherited from
> a bidirectional iterator. That is the whole crux of the issue. And by
> your own reasoning, the requirement in question could only be a
> mistake.
>
> Since neither forward nor bidirectional iterators implement the []
> operator, the Standard states that an expression like
>
> a[n]
>
> (a is a random access iterator) should be "equivalent" to
>
> *(a+n)
>
> But instead of being equivalent, the Standard specifies that the return
> type for operator[] can be any type that is "convertible to T". This is
> far more lax stipulation than the requirement for a bidirectional
> iterator's operator* (which must return a T&).
>
> A class is allowed to tighten its inherited requirements, but is not
> allowed to liberalize them (otherwise they would not be called
> "requirements").
Which bidirectional iterator requirements do you think are being
liberalized here? If you are reading the requirements on a[n] as
somehow loosening the requirements on *a, you're misinterpreting the
text. That said, there are some mistakes in this part of the
standard. Please see
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1830.html#299
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
Matthias Hofmann
news:1126658733.3...@g49g2000cwa.googlegroups.com...
> The portion of the Standard quoted above shows that one of the
> requirements for a random access iterator is not in fact inherited from
> a bidirectional iterator.
I assume that the requirement you are talking about is the result of a[n]
being convertible to T.
> That is the whole crux of the issue. And by
> your own reasoning, the requirement in question could only be a
> mistake.
>
> Since neither forward nor bidirectional iterators implement the []
> operator, the Standard states that an expression like
>
> a[n]
>
> (a is a random access iterator) should be "equivalent" to
>
> *(a+n)
>
> But instead of being equivalent, the Standard specifies that the return
> type for operator[] can be any type that is "convertible to T". This is
> far more lax stipulation than the requirement for a bidirectional
> iterator's operator* (which must return a T&).
>
> A class is allowed to tighten its inherited requirements, but is not
> allowed to liberalize them (otherwise they would not be called
> "requirements").
It looks indeed as if a random access iterator was required to return a T&
when using operator* (because this requirement is inherited), while applying
operator[] only required the iterator to return a type that is convertible
to T.
I don't know if this is a mistake. The reason is maybe to allow for proxy
classes. For example, note that std::vector<bool>::reference is class, not a
typedef for T&. However, std::vector<bool>::iterator is apparently not a
random access iterator at all, see:
http://www.gotw.ca/publications/N1211.pdf
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
David Abrahams
> It looks indeed as if a random access iterator was required to return a T&
> when using operator* (because this requirement is inherited), while applying
> operator[] only required the iterator to return a type that is convertible
> to T.
>
> I don't know if this is a mistake.
I don't think it's a mistake.
> The reason is maybe to allow for proxy classes.
IMO the real reason is explained at
http://www.boost.org/libs/iterator/doc/iterator_facade.html#operator
HTH,
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Matthias Hofmann
news:uoe6vj...@boost-consulting.com...
> > The reason is maybe to allow for proxy classes.
>
> IMO the real reason is explained at
> http://www.boost.org/libs/iterator/doc/iterator_facade.html#operator
I read the information in the link above as well as the information about
counting_iterator<> at
http://www.boost.org/libs/iterator/doc/counting_iterator.html
Please tell me if I understand this correctly: The current C++ standard
defines the expression
a[n] = t; // a is a random access iterator.
to be invalid in order to make possible the implementation of iterators that
allow the replacement of
int N = 7;
std::vector<int> numbers;
for ( int i = 0; i < N; ++i )
numbers.push_back( i );
with the following code:
int N = 7;
std::vector<int> numbers;
typedef std::vector<int>::iterator n_iter;
std::copy(boost::counting_iterator<int>(0),
boost::counting_iterator<int>(N),
std::back_inserter(numbers));
If this is the reason for having operator[] not return a T&, then I think
this needs to be changed, as almost anyone would expect operator[] to return
a T&, especially as this is true for regular pointers as well as for
operator*. Furthermore, I respectfully suggest that counting_iterator<> is
rather useless.
Please do not misinterpret my statements about counting_iterator<> as
criticism against the boost library in general, which I am sure has a lot of
benefits and offers many useful features.
Besides, I don't know about "caching file iterators", which are mentioned in
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1830.html#299
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
dave_abrahams
Matthias Hofmann wrote:
> "David Abrahams" <da...@boost-consulting.com> schrieb im Newsbeitrag
> news:uoe6vj...@boost-consulting.com...
>
> > > The reason is maybe to allow for proxy classes.
> >
> > IMO the real reason is explained at
> > http://www.boost.org/libs/iterator/doc/iterator_facade.html#operator
>
> I read the information in the link above as well as the information about
> counting_iterator<> at
> http://www.boost.org/libs/iterator/doc/counting_iterator.html
>
> Please tell me if I understand this correctly: The current C++ standard
> defines the expression
>
> a[n] = t; // a is a random access iterator.
>
> to be invalid
No, the link I specified above does not address that issue. It
addresses the issue of why a[n] is not required to yield a reference.
> in order to make possible the implementation of iterators that
> allow the replacement of
>
> int N = 7;
> std::vector<int> numbers;
> for ( int i = 0; i < N; ++i )
> numbers.push_back( i );
>
> with the following code:
>
> int N = 7;
> std::vector<int> numbers;
> typedef std::vector<int>::iterator n_iter;
> std::copy(boost::counting_iterator<int>(0),
> boost::counting_iterator<int>(N),
> std::back_inserter(numbers));
No, c'mon, that would be ridiculous.
a[n] is not required to yield a reference because that would rule out
_all_ random access iterators that reference a value_type object held
internally to the iterator. counting_iterator is only one example of
such an iterator.
> If this is the reason for having operator[] not return a T&, then I think
> this needs to be changed, as almost anyone would expect operator[] to return
> a T&, especially as this is true for regular pointers as well as for
> operator*.
Generic algorithms don't need operator[] at all. As with many other
features inherited from built-in pointers, requiring it on random
access iterators was a case of overspecification. I don't find any
argument for tightening the requirements compelling, especially since
that would render many currently legal programs and libraries
ill-formed.
> Furthermore, I respectfully suggest that counting_iterator<> is
> rather useless.
You're entitled to that opinion, but it's irrelevant, since the
standard requirement is not aimed specifically at supporting
counting_iterator.
> Please do not misinterpret my statements about counting_iterator<> as
> criticism against the boost library in general, which I am sure has a lot of
> benefits and offers many useful features.
>
> Besides, I don't know about "caching file iterators", which are mentioned in
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1830.html#299
Imagine you want to iterate over some on-disk collection of records
with a random access iterator and you don't want to keep them all in
memory. How would you do it? Remember that operator* must return a
reference.
See the problem now?
--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com
Matthias Hofmann
news:1126808633.7...@g43g2000cwa.googlegroups.com...
> > Please tell me if I understand this correctly: The current C++ standard
> > defines the expression
> >
> > a[n] = t; // a is a random access iterator.
> >
> > to be invalid
>
> No, the link I specified above does not address that issue. It
> addresses the issue of why a[n] is not required to yield a reference.
But the standard still defines that expression to be invalid, doesn't it?
Here's a corresponding quote from the last link in my previous post:
"In section 24.1.5 [lib.random.access.iterators], Table 76 gives the return
type of a[n] as convertible to T. This is not consistent with the semantics
of *(a + n) which returns T& by Table 74. *(a + n) = t is valid while a[n] =
t is invalid."
> > in order to make possible the implementation of iterators that
> > allow the replacement of
> >
> > int N = 7;
> > std::vector<int> numbers;
> > for ( int i = 0; i < N; ++i )
> > numbers.push_back( i );
> >
> > with the following code:
> >
> > int N = 7;
> > std::vector<int> numbers;
> > typedef std::vector<int>::iterator n_iter;
> > std::copy(boost::counting_iterator<int>(0),
> > boost::counting_iterator<int>(N),
> > std::back_inserter(numbers));
>
> No, c'mon, that would be ridiculous.
>
> a[n] is not required to yield a reference because that would rule out
> _all_ random access iterators that reference a value_type object held
> internally to the iterator. counting_iterator is only one example of
> such an iterator.
I know that the authors of the standard did not have *exactly* this example
in mind. But I still doubt that iterators *such as* counting_iterator
justify the inconsistency of operator[] with the semantics of *(a + n).
> Generic algorithms don't need operator[] at all. As with many other
> features inherited from built-in pointers, requiring it on random
> access iterators was a case of overspecification.
I have always thought that the idea was to make iterators as close to
pointers as possible? If this is the case, then I find it rather natural to
have random access iterators support operator[]. Besides, I think it is
always best to make user defined operators behave as similarly as possible
to the built-in ones, because this is what users expect. Wouldn't you be
surprised if an assignment to a[n] did not change the value of a[n], or if
it caused a compile time or run time error? (Assuming, of course, that n is
not out of range.)
> I don't find any
> argument for tightening the requirements compelling, especially since
> that would render many currently legal programs and libraries
> ill-formed.
Why? These libraries won't have to change classes like counting_iterator,
they would only have to stop labeling them "iterators" in the sense of the
standard. Note that you said yourself that generic algorithms don't need
operator[] at all, so there is actually no need to make these classes be
iterators.
Everyone can implement user-defined operators in whatever way he likes, I
might even have operator+ do a subtraction - I don't think this would
violate the standard, although it would certainly create confusion.
Therefore, there is no problem with operator[] returning anything you like
while at the same time requiring operator[] returning a T& *for iterators*.
> Imagine you want to iterate over some on-disk collection of records
> with a random access iterator and you don't want to keep them all in
> memory. How would you do it? Remember that operator* must return a
> reference.
>
> See the problem now?
I guess the problem is the same as with counting_iterator: the T& would
reference an object that goes out of scope as soon as operator[] returns.
However, I don't know how a caching file iterator is usually implemented.
One last thing about counting_iterator, just out of curiosity: why is it
actually called an iterator? It does not iterate through anything, does it?
Well, it does iterate through a sequence of numbers, but they do not belong
to any container. That makes it a little different from the usual iterators.
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
dave_abrahams
Matthias Hofmann wrote:
> "dave_abrahams" <da...@boost-consulting.com> schrieb im Newsbeitrag
> news:1126808633.7...@g43g2000cwa.googlegroups.com...
>
> > > Please tell me if I understand this correctly: The current C++ standard
> > > defines the expression
> > >
> > > a[n] = t; // a is a random access iterator.
> > >
> > > to be invalid
> >
> > No, the link I specified above does not address that issue. It
> > addresses the issue of why a[n] is not required to yield a reference.
>
> But the standard still defines that expression to be invalid, doesn't it?
The C++98 standard does, yes. And appropriately so unless you want to
disqualify int const* as a random access iterator. Of course you'll
note that similar allowances aren't made for forward iterator with *a =
x. The standard iterator requirements have lots of problems.
> > a[n] is not required to yield a reference because that would rule out
> > _all_ random access iterators that reference a value_type object held
> > internally to the iterator. counting_iterator is only one example of
> > such an iterator.
>
> I know that the authors of the standard did not have *exactly* this example
> in mind. But I still doubt that iterators *such as* counting_iterator
> justify the inconsistency of operator[] with the semantics of *(a + n).
You're entitled to your opinion, of course.
> > Generic algorithms don't need operator[] at all. As with many other
> > features inherited from built-in pointers, requiring it on random
> > access iterators was a case of overspecification.
>
> I have always thought that the idea was to make iterators as close to
> pointers as possible?
It was *an* idea; not the main one. Unfortunately that idea goes
against one of the main principles of generic programming: that concept
requirements should be minimal.
> If this is the case, then I find it rather natural to
> have random access iterators support operator[]. Besides, I think it is
> always best to make user defined operators behave as similarly as possible
> to the built-in ones, because this is what users expect.
If your expectations are based on false premises there's nothing I can
do for you. The role of concepts isn't to make everything look like
something you're already familiar with; it's to provide a means of
interface specification for generic programming.
> Wouldn't you be
> surprised if an assignment to a[n] did not change the value of a[n], or if
> it caused a compile time or run time error? (Assuming, of course, that n is
> not out of range.)
Not at all, depending on the type of a. See int const*, for example.
If a were a range-checked array type a runtime error might be very
expected.
> > I don't find any
> > argument for tightening the requirements compelling, especially since
> > that would render many currently legal programs and libraries
> > ill-formed.
>
> Why? These libraries won't have to change classes like counting_iterator,
> they would only have to stop labeling them "iterators" in the sense of the
> standard.
That would render illegal any code that uses counting_iterator (and
others like it) with std::copy, for example. This is not just a
technicality: it will cause portable, currently legal programs to
break. Standard library implementations and other code using iterators
would be free to assume that operator[] returns a reference, could
start to use operator[] in algorithm implementations, and then the code
that uses currently-legal iterators, would break.
> Note that you said yourself that generic algorithms don't need
> operator[] at all, so there is actually no need to make these classes be
> iterators.
I don't see how the second part of the sentence follows from the first
part. Anything that will be passed to a standard algorithm where the
algorithm expects an iterator certainly needs to be an iterator.
> Everyone can implement user-defined operators in whatever way he likes, I
> might even have operator+ do a subtraction - I don't think this would
> violate the standard, although it would certainly create confusion.
> Therefore, there is no problem with operator[] returning anything you like
> while at the same time requiring operator[] returning a T& *for iterators*.
There certainly is a problem with that. First, as I have said before,
it would rule out some very useful iterators. Second, as I explained
in this message, it would invalidate some currently valid programs.
> > Imagine you want to iterate over some on-disk collection of records
> > with a random access iterator and you don't want to keep them all in
> > memory. How would you do it? Remember that operator* must return a
> > reference.
> >
> > See the problem now?
>
> I guess the problem is the same as with counting_iterator: the T& would
> reference an object that goes out of scope as soon as operator[] returns.
Exactly.
> However, I don't know how a caching file iterator is usually implemented.
Writing to the iterator writes to the internal cache. Reading from the
iterator reads from disk if the cache is invalid, and then returns a
reference to the internal cache. Moving the iterator writes the
internal cache to disk.
> One last thing about counting_iterator, just out of curiosity: why is it
> actually called an iterator?
This question reflects your presumption that an iterator has to be
"like a pointer," but that is not the true intent of the iterator
concepts. It's called an iterator because it satisfies the iterator
requirements and can be used accordingly with standard algorithms and
any other generic components that take iterator arguments.
> It does not iterate through anything, does it?
Yes. It iterates through a sequence of values in much the same way
that an input_iterator iterates through a sequence of values. An
iterator doesn't have to reference any persistent data.
> Well, it does iterate through a sequence of numbers, but they do not belong
> to any container. That makes it a little different from the usual iterators.
Like istream_iterator? ;-)
--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com
Gabriel Dos Reis
[...]
| > One last thing about counting_iterator, just out of curiosity: why is it
| > actually called an iterator?
|
| This question reflects your presumption that an iterator has to be
| "like a pointer," but that is not the true intent of the iterator
| concepts.
There is some basis for his presumed "presumption".
24.1/1
Iterators are a generalization of pointers that allow a C++
program to work with different data structures (containers) in a
uniform manner.
I'm not saying that an iterator _should be_ "like a pointer"; but
given the standard formulation, I would not throw the rock at Matthias
Hofmann.
--
Gabriel Dos Reis
g...@integrable-solutions.net
David Abrahams
> "dave_abrahams" <da...@boost-consulting.com> writes:
>
> [...]
>
> | > One last thing about counting_iterator, just out of curiosity: why is it
> | > actually called an iterator?
> |
> | This question reflects your presumption that an iterator has to be
^^^^^^^^^
> | "like a pointer," but that is not the true intent of the iterator
> | concepts.
>
> There is some basis for his presumed "presumption".
>
> 24.1/1
>
> Iterators are a generalization of pointers that allow a C++
> program to work with different data structures (containers) in a
> uniform manner.
>
>
> I'm not saying that an iterator _should be_ "like a pointer"; but
> given the standard formulation, I would not throw the rock at
> Matthias Hofmann.
I didn't mean to throw any rocks at Matthias Hofmann, even
metaphorically. I hoped that this exchange, which I quote from the
same message you cite, would make it clear that I acknowledge
"pointerishness" was a design goal of iterators.
> I have always thought that the idea was to make iterators as close
> to pointers as possible?
It was *an* idea; not the main one. Unfortunately that idea goes
against one of the main principles of generic programming: that
concept requirements should be minimal.
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
Matthias Hofmann
> > > > a[n] = t; // a is a random access iterator.
> > But the standard still defines that expression to be invalid, doesn't
it?
>
> The C++98 standard does, yes. And appropriately so unless you want to
> disqualify int const* as a random access iterator.
int const* is a constant iterator. My assumption for the expression above
was that "a" is not a constant iterator.
> If your expectations are based on false premises there's nothing I can
> do for you. The role of concepts isn't to make everything look like
> something you're already familiar with; it's to provide a means of
> interface specification for generic programming.
Is it a false premise that ordinary pointers and random access iterators
provide the same interface? If they do not, then there's something wrong
with the 'concept'.
> If a were a range-checked array type a runtime error might be very
> expected.
A range error is something entirely different.
> That would render illegal any code that uses counting_iterator (and
> others like it) with std::copy, for example. This is not just a
> technicality: it will cause portable, currently legal programs to
> break. Standard library implementations and other code using iterators
> would be free to assume that operator[] returns a reference, could
> start to use operator[] in algorithm implementations, and then the code
> that uses currently-legal iterators, would break.
Well, that's true. Maybe it is too late for a change, but that does not
justify the original decision to make operator[] not return a reference.
> > Note that you said yourself that generic algorithms don't need
> > operator[] at all, so there is actually no need to make these classes be
> > iterators.
>
> I don't see how the second part of the sentence follows from the first
> part. Anything that will be passed to a standard algorithm where the
> algorithm expects an iterator certainly needs to be an iterator.
I thought that the special capabilities of these classes with respect to
operator[] was the main reason for providing them. So if the generic
algorithms don't need operator[] at all, then there would be no reason to
use any of these classes with std::copy or other generic algorithms.
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
David Abrahams
> "dave_abrahams" <da...@boost-consulting.com> schrieb im Newsbeitrag
> news:1126896527....@g44g2000cwa.googlegroups.com...
>
>> > > > a[n] = t; // a is a random access iterator.
>
>> > But the standard still defines that expression to be invalid, doesn't
> it?
>>
>> The C++98 standard does, yes. And appropriately so unless you want to
>> disqualify int const* as a random access iterator.
>
> int const* is a constant iterator. My assumption for the expression above
> was that "a" is not a constant iterator.
So you want to require the operator[] of mutable iterators to return a
reference, yes?
>> If your expectations are based on false premises there's nothing I can
>> do for you. The role of concepts isn't to make everything look like
>> something you're already familiar with; it's to provide a means of
>> interface specification for generic programming.
>
> Is it a false premise that ordinary pointers and random access iterators
> provide the same interface?
Yes. Ordinary pointers are models of random access iterator, so
random access iterators in general provide a subset of the interface
of pointers.
> If they do not, then there's something wrong with the 'concept'.
No. Random access iterators in general will never provide exactly the
same interface as pointers. For example, all pointers can be
converted to void const volatile*. Only a pointer can be passed to
this function template (leaving aside explicit template arguments):
template <class T> void f(T*);
I could go on, but I'm sure you get the idea.
>> If a were a range-checked array type a runtime error might be very
>> expected.
>
> A range error is something entirely different.
It's an error at runtime. I don't know what you have in mind when you
say "a runtime error" if not that.
>> That would render illegal any code that uses counting_iterator (and
>> others like it) with std::copy, for example. This is not just a
>> technicality: it will cause portable, currently legal programs to
>> break. Standard library implementations and other code using iterators
>> would be free to assume that operator[] returns a reference, could
>> start to use operator[] in algorithm implementations, and then the code
>> that uses currently-legal iterators, would break.
>
> Well, that's true. Maybe it is too late for a change, but that does not
> justify the original decision to make operator[] not return a reference.
No, it does not. I have already given you the justification: it makes
possible some very useful iterators that would otherwise be prohibited.
>> > Note that you said yourself that generic algorithms don't need
>> > operator[] at all, so there is actually no need to make these classes be
>> > iterators.
>>
>> I don't see how the second part of the sentence follows from the first
>> part. Anything that will be passed to a standard algorithm where the
>> algorithm expects an iterator certainly needs to be an iterator.
>
> I thought that the special capabilities of these classes with respect to
> operator[] was the main reason for providing them.
:) That's an interesting way to look at it, but no.
The "special capabilities" (I would rather say, "the special
restrictions") of these classes with respect to operator[] are simply
a necessary byproduct of the way their important members (operator*,
operator++, et al) work.
> So if the generic algorithms don't need operator[] at all, then
> there would be no reason to use any of these classes with std::copy
> or other generic algorithms.
!!
The reason to use these classes with generic algorithms has nothing to
do with operator[]; it has to do with their fundamental
characteristics. As I've been trying to tell you, operator[] is in no
way fundamental to iterators.
--
Dave Abrahams
Boost Consulting
Matthias Hofmann
news:u64sv3...@boost-consulting.com...
> > int const* is a constant iterator. My assumption for the expression
above
> > was that "a" is not a constant iterator.
>
> So you want to require the operator[] of mutable iterators to return a
> reference, yes?
As you have explained in your previous post, this would break existing code.
Therefore, I'd rather say that it would have been better to require
operator[] to return a reference when the standard was first written. I am
not sure whether it should be changed now.
> Yes. Ordinary pointers are models of random access iterator, so
> random access iterators in general provide a subset of the interface
> of pointers.
Your point of view seems to be that ordinary pointers kind of inherit from
random access iterators. However, ordinary pointers and random access
iterators share operator[], but only one of them returns a reference. I am
not an expert, but I think this violates the rules of object oriented
design.
> >> If a were a range-checked array type a runtime error might be very
> >> expected.
> >
> > A range error is something entirely different.
>
> It's an error at runtime. I don't know what you have in mind when you
> say "a runtime error" if not that.
I think I had a dangling reference in mind, which obviously cannot occur if
no reference is returned.
> > Well, that's true. Maybe it is too late for a change, but that does not
> > justify the original decision to make operator[] not return a reference.
>
> No, it does not. I have already given you the justification: it makes
> possible some very useful iterators that would otherwise be prohibited.
Well, now we are entering an area of taste rather than logic. You want less
intuitive random access iterators in order to be able to implement certain
classes while I want the interface of random access iterators to be as
consistent with ordinary pointers as possible.
> The reason to use these classes with generic algorithms has nothing to
> do with operator[]; it has to do with their fundamental
> characteristics. As I've been trying to tell you, operator[] is in no
> way fundamental to iterators.
It seems to be a matter of opinion which operators are fundamental to
iterators or random access iterators. I have always felt like random access
iterators are very similar to pointers and that this was a design goal. This
is why the restriction on operator[] surprised me.
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
David Abrahams
> "David Abrahams" <da...@boost-consulting.com> schrieb im Newsbeitrag
> news:u64sv3...@boost-consulting.com...
>
>> > int const* is a constant iterator. My assumption for the expression
> above
>> > was that "a" is not a constant iterator.
>>
>> So you want to require the operator[] of mutable iterators to return a
>> reference, yes?
>
> As you have explained in your previous post, this would break existing code.
> Therefore, I'd rather say that it would have been better to require
> operator[] to return a reference when the standard was first written. I am
> not sure whether it should be changed now.
>
>> Yes. Ordinary pointers are models of random access iterator, so
>> random access iterators in general provide a subset of the interface
>> of pointers.
>
> Your point of view seems to be that ordinary pointers kind of inherit from
> random access iterators.
Depending on your definition of "kind of," then yes. To use the
proper generic programming terms, the concept "pointer" is a
refinement of the concept "random access iterator."
> However, ordinary pointers and random access iterators share
> operator[], but only one of them returns a reference.
A random access iterator's operator[] *may* return a reference, but it
might not.
> I am not an expert, but I think this violates the rules of object
> oriented design.
This is not OO; it's generic programming. I don't know what rules
you're thinking of. The rules of generic programming say that a
refinement of a concept has to have requirements that are at least as
restrictive as those of the original concept.
You could think of real references as "kind of" inheriting from the
category of allowed return types of operator[], and maybe it will make
more sense to you as a covariant return type.
>> >> If a were a range-checked array type a runtime error might be very
>> >> expected.
>> >
>> > A range error is something entirely different.
>>
>> It's an error at runtime. I don't know what you have in mind when you
>> say "a runtime error" if not that.
>
> I think I had a dangling reference in mind, which obviously cannot
> occur if no reference is returned.
I don't understand how this relates to your argument, then. Clearly
that "surprising" runtime error case is only possible when the
operator[] corresponds to your expectations that it return a
reference.
>> > Well, that's true. Maybe it is too late for a change, but that does not
>> > justify the original decision to make operator[] not return a reference.
>>
>> No, it does not. I have already given you the justification: it makes
>> possible some very useful iterators that would otherwise be prohibited.
>
> Well, now we are entering an area of taste rather than logic. You
> want less intuitive random access iterators in order to be able to
> implement certain classes while I want the interface of random
> access iterators to be as consistent with ordinary pointers as
> possible.
I understand your priorities. However, I think those priorities would
be objectively bad for generic programming. I wouldn't want to
require every random access iterator to be convertible to void const
volatile*. That is a similarity that is certainly possible to achieve
and enforce, but it would be useless.
>> The reason to use these classes with generic algorithms has nothing
>> to do with operator[]; it has to do with their fundamental
>> characteristics. As I've been trying to tell you, operator[] is in
>> no way fundamental to iterators.
>
> It seems to be a matter of opinion which operators are fundamental to
> iterators or random access iterators.
I think you can support my opinion by looking at the body of real
generic code that uses random access iterators. You'll find very few
uses of operator[].
> I have always felt like random access iterators are very similar to
> pointers and that this was a design goal. This is why the
> restriction on operator[] surprised me.
Yes, it was a design goal. It was misguided, or at least pursued
further than it ought to have been. It left us with some appendages
like operator[] that serve no other purpose than to surprise people
like you.
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Gerhard Menzl
>>Yes. Ordinary pointers are models of random access iterator, so
>>random access iterators in general provide a subset of the interface
>>of pointers.
>
> Your point of view seems to be that ordinary pointers kind of inherit
> from random access iterators. However, ordinary pointers and random
> access iterators share operator[], but only one of them returns a
> reference. I am not an expert, but I think this violates the rules of
> object oriented design.
It's strange to accuse a generically designed library of violating
object-oriented design. It's BEHAVES-IN-SOME-RESPECTS-AS, not IS-A.
--
Gerhard Menzl
#dogma int main ()
Humans may reply by replacing the thermal post part of my e-mail address
with "kapsch" and the top level domain part with "net".
Matthias Hofmann
> > Your point of view seems to be that ordinary pointers kind of inherit
from
> > random access iterators.
>
> Depending on your definition of "kind of," then yes. To use the
> proper generic programming terms, the concept "pointer" is a
> refinement of the concept "random access iterator."
My first idea was to write that "ordinary pointers *conceptually* inherit
from random access iterators", so my definition of "kind of" is quite the
way you understood it.
> This is not OO; it's generic programming. I don't know what rules
> you're thinking of. The rules of generic programming say that a
> refinement of a concept has to have requirements that are at least as
> restrictive as those of the original concept.
>
> You could think of real references as "kind of" inheriting from the
> category of allowed return types of operator[], and maybe it will make
> more sense to you as a covariant return type.
I think you are right. operator[] being more restrictive for oridinary
pointers makes it possible that I can use an ordinary pointer anywhere I can
use a random access iterator, but not the other way round.
However, I would like to have both ordinary pointers and random access
iterators to "kind of" inherit from a more abstract concept, one that has
operator[] return a reference. That would mean that ordinary pointers and
random access iterators were interchangeable, in terms of operator[].
> > I think I had a dangling reference in mind, which obviously cannot
> > occur if no reference is returned.
>
> I don't understand how this relates to your argument, then. Clearly
> that "surprising" runtime error case is only possible when the
> operator[] corresponds to your expectations that it return a
> reference.
I probably had those problems related to returning a reference to a local
object from operator[] in mind, but this was actually not relevant for my
argument.
> > Well, now we are entering an area of taste rather than logic. You
> > want less intuitive random access iterators in order to be able to
> > implement certain classes while I want the interface of random
> > access iterators to be as consistent with ordinary pointers as
> > possible.
>
> I understand your priorities. However, I think those priorities would
> be objectively bad for generic programming. I wouldn't want to
> require every random access iterator to be convertible to void const
> volatile*. That is a similarity that is certainly possible to achieve
> and enforce, but it would be useless.
I have to admit that I have not run into any difficulties due to the current
solution so far. If someone really needs operator[] to return a reference,
then it is probably easy to find a workaround.
By the way, what does the standard say about
std::vector<>::iterator::operator[]? Does it return a reference? If yes,
then things are fine anyway.
> I think you can support my opinion by looking at the body of real
> generic code that uses random access iterators. You'll find very few
> uses of operator[].
Maybe because operator[] does not work as would be required? ;-)
> Yes, it was a design goal. It was misguided, or at least pursued
> further than it ought to have been. It left us with some appendages
> like operator[] that serve no other purpose than to surprise people
> like you.
If the standard had remained silent about operator[] for random access
iterators, what would have been different? I think most people would have
expected it to return a reference, as this would be most analogous to *( a +
n). On the other hand, they would not have found such a guarantee, so they
would have started to ask questions. And so the standard has answered these
questions in anticipation of those questions. And the answer was surprising,
indeed... ;-)
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Matthias Hofmann
news:43317ec7$1...@news.kapsch.co.at...
> Matthias Hofmann wrote:
>
>
> >>Yes. Ordinary pointers are models of random access iterator, so
> >>random access iterators in general provide a subset of the interface
> >>of pointers.
> >
> > Your point of view seems to be that ordinary pointers kind of inherit
> > from random access iterators. However, ordinary pointers and random
> > access iterators share operator[], but only one of them returns a
> > reference. I am not an expert, but I think this violates the rules of
> > object oriented design.
>
> It's strange to accuse a generically designed library of violating
> object-oriented design. It's BEHAVES-IN-SOME-RESPECTS-AS, not IS-A.
As Dave Abrahams has explained in his most recent post, an ordinary pointer
IS-A random access iterator as far as operator[] is concerned. As this only
goes for operator[], you are right that an ordinary pointer generally only
BEHAVES-IN-SOME-RESPECTS-AS a random access iterator.
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
David Abrahams
>> > Well, now we are entering an area of taste rather than logic. You
>> > want less intuitive random access iterators in order to be able to
>> > implement certain classes while I want the interface of random
>> > access iterators to be as consistent with ordinary pointers as
>> > possible.
>>
>> I understand your priorities. However, I think those priorities would
>> be objectively bad for generic programming. I wouldn't want to
>> require every random access iterator to be convertible to void const
>> volatile*. That is a similarity that is certainly possible to achieve
>> and enforce, but it would be useless.
>
> I have to admit that I have not run into any difficulties due to the current
> solution so far. If someone really needs operator[] to return a reference,
> then it is probably easy to find a workaround.
*(p + n)
> By the way, what does the standard say about
> std::vector<>::iterator::operator[]?
Nothing special.
> Does it return a reference?
Not necessarily.
> If yes, then things are fine anyway.
I think things are still fine anyway.
>> I think you can support my opinion by looking at the body of real
>> generic code that uses random access iterators. You'll find very
>> few uses of operator[].
>
> Maybe because operator[] does not work as would be required? ;-)
No. Look at the standard algorithms if you don't have any other
generic code in front of you. It wouldn't benefit at all from using
operator[].
>> Yes, it was a design goal. It was misguided, or at least pursued
>> further than it ought to have been. It left us with some
>> appendages like operator[] that serve no other purpose than to
>> surprise people like you.
>
> If the standard had remained silent about operator[] for random
> access iterators, what would have been different?
If it had remained altogether silent about operator[], then random
access iterators wouldn't have been required to implement operator[]
at all.
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
David Abrahams
> As Dave Abrahams has explained in his most recent post, an ordinary
> pointer IS-A random access iterator as far as operator[] is
> concerned. As this only goes for operator[], you are right that an
> ordinary pointer generally only BEHAVES-IN-SOME-RESPECTS-AS a random
> access iterator.
No, that's incorrect. In all respects, it fulfills the requirements
of the "random access iterator" concept a pointer IS-A random access
iterator.
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
liftmaster
The stanandard sometimes seems to suggest that for an iterator of const
data eg " const float* " the "value type" T is not const ("float") and
sometimes seems to suggest that it is const. I am not accusing the
standard of contradicting itself, just pointing out that I don't think it
is entierly clear. If the type of T in this case IS considered to be
non-const then e.g. const float* does not meet the requirements for a
random access iterator (and note that iterator_traits<const
float*>::value_type is non-const).
David Abrahams
> The stanandard sometimes seems to suggest that for an iterator of const
> data eg " const float* " the "value type" T is not const ("float") and
> sometimes seems to suggest that it is const. I am not accusing the
> standard of contradicting itself, just pointing out that I don't think it
> is entierly clear.
It's true that the standard's documentation of an iterator's
associated types is not very explicit, but I don't think the standard
ever suggests that the value_type of a constant iterator should be
const. If you've found such a suggestion, I'd like to see it.
> If the type of T in this case IS considered to be
> non-const then e.g. const float* does not meet the requirements for a
> random access iterator
Aside from the writability requirement
*a = x
which is overspecified for all iterator categories (the standard
failed to distinguish mutable from constant iterators, except
informally) what other random access requirements do you think are
violated?
> (and note that iterator_traits<const float*>::value_type is
> non-const).
And that's proper; it's a usability thing. Imagine what generic
algorithms wanting to declare a temporary (non-constant) value would
have to do. For example, try writing an algorithm taking two
iterators that computes the sum of a non-empty sequence of numbers.
Yes, you can strip const with some ugly traits, but should you have
to?
--
Dave Abrahams
Boost Consulting
www.boost-consulting.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Matthias Hofmann
>
> The stanandard sometimes seems to suggest that for an iterator of const
> data eg " const float* " the "value type" T is not const ("float") and
> sometimes seems to suggest that it is const. I am not accusing the
> standard of contradicting itself, just pointing out that I don't think it
> is entierly clear. If the type of T in this case IS considered to be
> non-const then e.g. const float* does not meet the requirements for a
> random access iterator (and note that iterator_traits<const
> float*>::value_type is non-const).
I am also surprised that the following code does not compile on Visual
Studio .NET 2002:
#include <iostream>
#include <iterator>
int main()
{
// This line fails to compile.
typedef std::iterator_traits<const float*>::value_type type;
std::cout << typeid( type ).name() << std::endl;
return 0;
}
The standard says that iterator_traits<> is specialized for pointers, but it
does not seem like those guys in Redmond have ever read it. Or is there
another header I need to include besides <iterator>?
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
P.J. Plauger
news:43352f74$0$26235$9b4e...@newsread2.arcor-online.net...
> "liftmaster" <manin...@another.com> schrieb im Newsbeitrag
>
news:0bf9ff4b8855d50f...@localhost.talkaboutprogramming.com...
>>
>> The stanandard sometimes seems to suggest that for an iterator of const
>> data eg " const float* " the "value type" T is not const ("float") and
>> sometimes seems to suggest that it is const. I am not accusing the
>> standard of contradicting itself, just pointing out that I don't think it
>> is entierly clear. If the type of T in this case IS considered to be
>> non-const then e.g. const float* does not meet the requirements for a
>> random access iterator (and note that iterator_traits<const
>> float*>::value_type is non-const).
>
> I am also surprised that the following code does not compile on Visual
> Studio .NET 2002:
>
> #include <iostream>
> #include <iterator>
>
> int main()
> {
> // This line fails to compile.
> typedef std::iterator_traits<const float*>::value_type type;
>
> std::cout << typeid( type ).name() << std::endl;
>
> return 0;
> }
>
> The standard says that iterator_traits<> is specialized for pointers, but
> it
> does not seem like those guys in Redmond have ever read it. Or is there
> another header I need to include besides <iterator>?
Those guys in Redmond have read it, and so have I. In fact, I
helped write it. Nevertheless, the C++ Standard is not terribly
clear about the use of const with the STL part of the Standard
C++ library. Put simply, you'd better not try to specialize
quite a number of template classes with const types. These
include the containers, allocators, and practically all iterators.
I suspect "a careful reading of the document" tells you this, but
it could doubtless be made clearer.
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com