[forwarded from http://bugs.debian.org/36600
 beeing not an C++ standard expert, please feel free to close the report, if not
appropriate]

discussion was on:

http://gcc.gnu.org/ml/libstdc++/1999-q4/msg00118.html
http://gcc.gnu.org/ml/libstdc++/1999-q4/msg00124.html

    Matthias

David Marwood:
The Dec 2, 1996 draft of the "Working Paper for Draft Proposed
International Standard for Information Systems Programming Language
C++" says that the multiset must support forward iterators.  A forward
iterator's operator* must return a reference (T&).  The implementation
in libstdc++2.9-dev multiset.h returns a const reference (const T&).
This is not correct.

$ g++ 36600.cc
36600.cc: In function `int main()':
36600.cc:11: error: invalid initialization of reference of type 'int&' 
   from expression of type 'const int'

#include <set>

using namespace std;

int main(void)
{
  typedef  multiset<int, less<int> > multiset_type;
  multiset_type x;
  x.insert(5);
  multiset_type::iterator iter = x.begin();
  multiset_type::reference y = *iter;
  y = 6;
}



Matt Austern:
That's unclear.  The C++ standard is contradictory, and this is
still an open issue before the library working group.  The
standardization committee hasn't yet decided how this issue
should be resolved.  (There are several related issues.  Some of
the signatures in set and multiset make no sense unless iterator
and const_iterator are the same type.)

David Marwood:
That's interesting.  What I'm working from is the "Working Paper for
Draft Proposed International Standard for Information Systems --
Programming Language C++" dated Dec 2, 1996.  Page 24-4, section
24.1.3 Forward iterators, has a table that says the expression "*a"
for iterator 'a' must return a T& (no mention of returning a
multiset_type::reference).

I can believe there are contradictions; it is, after all, a draft.


Matt Austern:
Oddly enough, that's not even the problem is was thinking of.  I
was thinking of contradictions in the associative container requirement
tables.  (The final standard has contradictions and omissions too, not
just the draft.   The C++ standardization committee is working on
addressing those defects.)

I think, though, that you may have found another subtle defect in the
standard.  Table 74 explicitly says, as it ought to say, that a
Forward Iterator need not be mutable.  (See the "assertion/note/pre/
post-condition" column for "*a".  It says "If X is mutable, *a = t
is valid".)  That's good, because otherwise the consequences would be
disastrous.  We certainly expect that iterator types like
list<int>::const_iterator, or const double*, are (immutable) Forward
Iterators.

The defect is that, as you observed, Table 74 also says that the
return type of *a is 'T&'.  These two things can be reconciled if
we interpret 'T' for 'const double*' as 'const double' rather than
'double', since Table 74, and the notation section in 24.1,
paragraph 9, are rather vague.  I'm not sure it's quite vague
enough, though, since elsewhere (24.3.1/2) we're given the example
of a nonmodifiable iterator whose value type is T, not const T,
and whose reference type is 'const T&'.

Your interpretation of Table 74 is that all Forward Iterators
must be modifiable.  That would mean that (for example)
vector<T>::const_iterator would have to be modifiable, since
23.1.1/5 says that "iterator and const_iterator types for sequences
must be at least of the forward iterator category".  I think we
would agree that this is undesirable.

Historically, I'm afraid this defect is just because the iterator
tables in the standard were a first-generation effort to define a
precise set of iterator requirements.  I think I should open up
another library issue for this problem.

			--Matt Austern