Section: 24.3.5.6 [bidirectional.iterators], 24.3.5.7 [random.access.iterators] Status: NAD Editorial Submitter: John Potter Opened: 2001-01-22 Last modified: 2016-01-28
Priority: Not Prioritized
View all other issues in [bidirectional.iterators].
View all issues with NAD Editorial status.
Discussion:
In section 24.3.5.6 [bidirectional.iterators],
Table 75 gives the return type of *r-- as convertible to T. This is
not consistent with Table 74 which gives the return type of *r++ as
T&. *r++ = t is valid while *r-- = t is invalid.
In section 24.3.5.7 [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.
Discussion from the Copenhagen meeting: the first part is
uncontroversial. The second part, operator[] for Random Access
Iterators, requires more thought. There are reasonable arguments on
both sides. Return by value from operator[] enables some potentially
useful iterators, e.g. a random access "iota iterator" (a.k.a
"counting iterator" or "int iterator"). There isn't any obvious way
to do this with return-by-reference, since the reference would be to a
temporary. On the other hand, reverse_iterator takes an
arbitrary Random Access Iterator as template argument, and its
operator[] returns by reference. If we decided that the return type
in Table 76 was correct, we would have to change
reverse_iterator. This change would probably affect user
code.
History: the contradiction between reverse_iterator and the
Random Access Iterator requirements has been present from an early
stage. In both the STL proposal adopted by the committee
(N0527==94-0140) and the STL technical report (HPL-95-11 (R.1), by
Stepanov and Lee), the Random Access Iterator requirements say that
operator[]'s return value is "convertible to T". In N0527
reverse_iterator's operator[] returns by value, but in HPL-95-11
(R.1), and in the STL implementation that HP released to the public,
reverse_iterator's operator[] returns by reference. In 1995, the
standard was amended to reflect the contents of HPL-95-11 (R.1). The
original intent for operator[] is unclear.
In the long term it may be desirable to add more fine-grained iterator requirements, so that access method and traversal strategy can be decoupled. (See "Improved Iterator Categories and Requirements", N1297 = 01-0011, by Jeremy Siek.) Any decisions about issue 299 should keep this possibility in mind.
Further discussion: I propose a compromise between John Potter's
resolution, which requires T& as the return type of
a[n], and the current wording, which requires convertible to
T. The compromise is to keep the convertible to T
for the return type of the expression a[n], but to also add
a[n] = t as a valid expression. This compromise "saves" the
common case uses of random access iterators, while at the same time
allowing iterators such as counting iterator and caching file
iterators to remain random access iterators (iterators where the
lifetime of the object returned by operator*() is tied to the
lifetime of the iterator).
Note that the compromise resolution necessitates a change to
reverse_iterator. It would need to use a proxy to support
a[n] = t.
Note also there is one kind of mutable random access iterator that
will no longer meet the new requirements. Currently, iterators that
return an r-value from operator[] meet the requirements for a
mutable random access iterator, even though the expression a[n] =
t will only modify a temporary that goes away. With this proposed
resolution, a[n] = t will be required to have the same
operational semantics as *(a + n) = t.
[ 2009-07-28 Reopened by Alisdair. No longer solved by concepts. ]
[ 2009-09-18 Alisdair adds: ]
Why can't we write through the reference returned from
operator[]on a random access iterator?Recommended solution:
In table Table 104 — Random access iterator requirements, replace
a[n]: convertible toconst T &T&ifXis mutable, otherwise convertible toconst T&
[ 2009-10 Santa Cruz: ]
Leave Open. Alisdair to spearhead a paper on revivification.
[ 2010 Pittsburgh: Moved to NAD Editorial. Rationale added below. ]
Rationale:
Solved by N3066.
Proposed resolution:
In section 24.1.4 [lib.bidirectdional.iterators], change the return
type in table 75 from "convertible to T" to
T&.
In section 24.1.5 [lib.random.access.iterators], change the
operational semantics for a[n] to " the r-value of
a[n] is equivalent to the r-value of *(a +
n)". Add a new row in the table for the expression a[n] = t
with a return type of convertible to T and operational semantics of
*(a + n) = t.
[Lillehammer: Real problem, but should be addressed as part of iterator redesign]
Rationale:
[ San Francisco: ]
Solved by N2758.