David Abrahams wrote:
>
> "Scott Meyers" <smeyers@aristeia.com> wrote in message
> news:MPG.14c75e1bb21c7377989772@news.supernews.com...
> > Maybe it's just me, but I find the Committee's attitude towards the
> > mutability of set/multiset elements even more Delphic than usual.  The
> > standard makes clear that for a non-const set<T>, dereferencing a
> > set<T>::iterator yields a T&.
>
> Where does it do that?

Table 65: container::iterator is required to be an iterator type
pointing to T. 23.3.3p1: set<T> is an associative container. 23.1.2p6:
associative containers have bidirectional iterators. 24.1.4p1:
bidirectional iterators satisfy forward iterator requirements.  Table
74: dereferencing a forward iterator pointing to T returns T&.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Okay, I think I'm making headway, but I still don't understand why the
Committee rejected issue #82.  If elements of a set are supposed to be
immutable, why not declare them const?

On Fri, 12 Jan 2001 03:39:40 CST, Matthew Austern wrote:
> There's an important distinction that the issues lists may not make
> clear enough: the distinction between whether an container has
> modifiable elements, and whether its value type is const.
...
> In my opinion (and, I believe, the opinion of other LWG members),
> there are still flaws related to issues of const in containers and
> iterators.  Historically, I think the problem is that the original STL
> proposal wasn't careful enough to decide whether the value type of a
> nonmodifying iterator was T or const T.  We've gradually been moving
> towards an understanding that it is the former

I think it would help me a lot if you could explain why you (collectively)
have been moving towards this understanding.  It sounds like if I
understood that, I'd understand why, if you want to say that the elements
of a container are immutable, you don't just declare them const.

On Fri, 12 Jan 2001 03:43:26 CST, David Abrahams wrote:
> "Scott Meyers" <smeyers@aristeia.com> wrote in message
> news:MPG.14c75e1bb21c7377989772@news.supernews.com...
> > Maybe it's just me, but I find the Committee's attitude towards the
> > mutability of set/multiset elements even more Delphic than usual.  The
> > standard makes clear that for a non-const set<T>, dereferencing a
> > set<T>::iterator yields a T&.
>
> Where does it do that?

I found the reasoning in Herb Sutter's article compelling.  I didn't
realize that it wasn't universally accepted.

> I agree that this is a fuzzy statement. I think it actually means is that
> there is another way that the standard specifies the constness of keys for
> set/multiset.

That now seems clear.  But *why* does it use an alternative mechanism when
using const would seem to be direct an unambiguous?

> >   1.  For sets and multisets, keys are const.
>
> Right.

But the resolution to issue #82 explicitly says that this is *not* right.

Scott

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Maybe it's just me, but I find the Committee's attitude towards the
mutability of set/multiset elements even more Delphic than usual.  The
standard makes clear that for a non-const set<T>, dereferencing a
set<T>::iterator yields a T&.  We conclude that set elements are mutable.

An issue was raised on this suggesting that set/multiset keys should be
const (LWG #82), but it was rejected.  "The Standard is correct as
written."  Clear enough, except that it continues, "it uses a different
mechanism (const &) for set and multiset. See issue 103 for a related
issue."  This suggests that set/multiset keys are deliberately not const,
but are also not supposed to be modifiable.  Hmmm.

Issue #103 has "Ready" status, which seems to mean that it's highly likely
to be adopted.  I have trouble understanding it.  Here is the proposed
resolution, which I assume is what the Committee has essentially decided to
adopt:

  At the end of paragraph 3: "For any two keys k1 and k2 in the same
  container, calling comp(k1, k2) shall always return the same value."

This I understand.  It allows keys to be modified as long as you don't do
anything stupid.  Fine.  It also handles the case where portions of the
conceptual key are stored outside the object.  Equally fine.

  At the end of paragraph 5: "Keys in an associative container are
  immutable."

This seems to take away all the flexibility that the preceding comment
appeared to grant.  If keys are immutable, why aren't they just declared
const?

  At the end of paragraph 6: "For associative containers where the value
  type is the same as the key type, both iterator and const_iterator are
  constant iterators. It is unspecified whether or not iterator and
  const_iterator are the same type."

What is a "constant iterator", and how does it differ from a
const_iterator?

>From what I can tell, the behavior the Committeee seems to want to specify
is this:

  1.  For sets and multisets, keys are const.
  2.  All functions on set/multiset that return iterators really return
      const_iterators.
  3.  "For any two keys k1 and k2 in the same container, calling comp(k1, k2)
      shall always return the same value."

But 1 and 2 were explicitly rejected.  Can somebody please explain this to
me?

Thanks,

Scott

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Off the top of my head:

Scott Meyers <smeyers@aristeia.com> writes:
>The standard makes clear that for a non-const set<T>, dereferencing a
>set<T>::iterator yields a T&.  We conclude that set elements are mutable.

I happen to agree, based on lib.container.requirements, but I think some
others don't. I don't recall the reasons, but I think part of it was that an
existing implementation had set::iterator and set::const_iterator as the
same type -- which I think is nonconforming, but others think it is (or
should be) okay.

As Scott knows, I devoted a C++ Report column to this very topic ("Standard
Library News, Part 2: Sets and Maps", C++ Report 11(9), October 1999).

>Issue #103 has "Ready" status, which seems to mean that it's highly likely
>to be adopted.  I have trouble understanding it.  Here is the proposed
>resolution, which I assume is what the Committee has essentially decided to
>adopt:
>
>  At the end of paragraph 3: "For any two keys k1 and k2 in the same
>  container, calling comp(k1, k2) shall always return the same value."
>
>This I understand.  It allows keys to be modified as long as you don't do
>anything stupid.  Fine.  It also handles the case where portions of the
>conceptual key are stored outside the object.  Equally fine.

Thanks, I wrote that, at Dublin I think (April 1999). Or, more accurately, I
wrote the longer Option C of which this was essentially the first sentence;
it would have been nice to keep the full note to show the intent.

I don't recall much discussion at Kona (October 1999). I could have been out
of the room when it happened.

Alas, I couldn't attend the Tokyo meeting (April 2000), where the following
parts were added, and I didn't notice it afterwards... my fault, I should
have been more diligent in searching the issues list for the string "Tokyo".

>  At the end of paragraph 5: "Keys in an associative container are
>  immutable."
>
>This seems to take away all the flexibility that the preceding comment
>appeared to grant.  If keys are immutable, why aren't they just declared
>const?
>
>  At the end of paragraph 6: "For associative containers where the value
>  type is the same as the key type, both iterator and const_iterator are
>  constant iterators. It is unspecified whether or not iterator and
>  const_iterator are the same type."
>
>What is a "constant iterator", and how does it differ from a
>const_iterator?

I don't know. Presumably iterators that do not permit modification of the
pointed-at object.

I happen to disagree with "the argument which swayed the LWG" toward this
resolution, on the grounds that const can't protect from many said simple
user oversights (such as using data physically outside the object as part of
the comparison) in the first place, so compile-time safety for element
ordering violations is largely a will-o-the-wisp anyway. More detailed
discussion appeared under the subheads "Option #1: Say 'const Means const!'
(Insufficient)" and "Option #2: Say 'Always Change Keys Using
Remove-Then-Insert' (Better, But Still Insufficient)" in the above-mentioned
article.

Although I disagree with the proposed (and now actual) resolution, I'll
defend the fact that it's at least self-consistent: The second and third
points implement the intended resolution; the first patches the hole related
to data outside the object (e.g., in separate memory or a disk file) being
used in the comparison, by adding a(n indirect) requirement that such data
not change.

>>From what I can tell, the behavior the Committeee seems to want to specify
>is this:
>
>  1.  For sets and multisets, keys are const.
>  2.  All functions on set/multiset that return iterators really return
>      const_iterators.
>  3.  "For any two keys k1 and k2 in the same container, calling comp(k1, k2)
>      shall always return the same value."
>
>But 1 and 2 were explicitly rejected.

What I think you're saying is that the rationale for issue #82 appears to be
inconsistent with the rationale for issue #103, right? I'll leave that for
another day... it's after midnight now, and I may already have made thinkos
in the above.

>Can somebody please explain this to me?

Perhaps someone who was at Tokyo would like to comment. (Quite a few people
missed Tokyo because of the distance/timing; how well was the LWG "staffed"
at that meeting?)

I don't remember any discussion of this at Toronto, but it may have occurred
while I was out of the room.

Herb

---
Herb Sutter (mailto:hsutter@acm.org)

Contributing Editor, C/C++ Users Journal (http://www.cuj.com)

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

"Scott Meyers" <smeyers@aristeia.com> wrote in message
news:MPG.14c75e1bb21c7377989772@news.supernews.com...
> Maybe it's just me, but I find the Committee's attitude towards the
> mutability of set/multiset elements even more Delphic than usual.  The
> standard makes clear that for a non-const set<T>, dereferencing a
> set<T>::iterator yields a T&.

Where does it do that?

> We conclude that set elements are mutable.

Maybe you do... heck, maybe I do, too, but I don't think so. ;-)

> An issue was raised on this suggesting that set/multiset keys should be
> const (LWG #82), but it was rejected. "The Standard is correct as
> written."  Clear enough,

Probably not...

> except that it continues, "it uses a different
> mechanism (const &) for set and multiset. See issue 103 for a related
> issue."  This suggests that set/multiset keys are deliberately not const,
> but are also not supposed to be modifiable.  Hmmm.

I agree that this is a fuzzy statement. I think it actually means is that
there is another way that the standard specifies the constness of keys for
set/multiset.

> Issue #103 has "Ready" status, which seems to mean that it's highly likely
> to be adopted.  I have trouble understanding it.  Here is the proposed
> resolution, which I assume is what the Committee has essentially decided
to
> adopt:
>
>   At the end of paragraph 3: "For any two keys k1 and k2 in the same
>   container, calling comp(k1, k2) shall always return the same value."
>
> This I understand.  It allows keys to be modified as long as you don't do
> anything stupid.

If you read the rationale at the bottom of the issue, you can see that this
isn't the intent.

> Fine.  It also handles the case where portions of the
> conceptual key are stored outside the object.  Equally fine.
>
>   At the end of paragraph 5: "Keys in an associative container are
>   immutable."
>
> This seems to take away all the flexibility that the preceding comment
> appeared to grant.  If keys are immutable, why aren't they just declared
> const?

I think that's one of the things we're trying to do in LWG 103.

>   At the end of paragraph 6: "For associative containers where the value
>   type is the same as the key type, both iterator and const_iterator are
>   constant iterators. It is unspecified whether or not iterator and
>   const_iterator are the same type."
>
> What is a "constant iterator", and how does it differ from a
> const_iterator?

See 24.1 paragraph 4:

4 Besides its category, a forward, bidirectional, or random access iterator
can also be mutable or constant depending on whether the result of the
expression *i behaves as a reference or as a reference to a constant.
Constant iterators do not satisfy the requirements for output iterators, and
the result of the expression *i (for constant iterator i) cannot be used in
an expression where an lvalue is required.

> >From what I can tell, the behavior the Committeee seems to want to
specify
> is this:
>
>   1.  For sets and multisets, keys are const.

Right.

>   2.  All functions on set/multiset that return iterators really return
>       const_iterators.

Not quite. set<>::iterator may be a different type from
set<>::const_iterator, but must be functionally equivalent.

>   3.  "For any two keys k1 and k2 in the same container, calling comp(k1,
k2)
>       shall always return the same value."


> But 1 and 2 were explicitly rejected.  Can somebody please explain this to
> me?

Who rejected 1 and 2? The proposed resolution, in full, is:

Add the following to 23.1.2 lib.associative.reqmts at the indicated
location:

  At the end of paragraph 3: "For any two keys k1 and k2 in the same
container, calling comp(k1, k2) shall always return the same value."

  At the end of paragraph 5: "Keys in an associative container are
immutable."

  At the end of paragraph 6: "For associative containers where the value
type is the same as the key type, both iterator and const_iterator are
constant iterators. It is unspecified whether or not iterator and
const_iterator are the same type."




---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Scott Meyers wrote:
>
> >From what I can tell, the behavior the Committeee seems to want to specify
> is this:
>
>   1.  For sets and multisets, keys are const.
>   2.  All functions on set/multiset that return iterators really return
>       const_iterators.
>   3.  "For any two keys k1 and k2 in the same container, calling comp(k1, k2)
>       shall always return the same value."
>
> But 1 and 2 were explicitly rejected.  Can somebody please explain this to
> me?

Some examples, why const might not be enough.

Untested example code fragments:

<code>
class Foo
{
public:  // for simplicity
  mutable int data1; // only this one is used for comparision
  mutable int data2;

  void set(int d1, int d2) const { data1=d1; data2=d2; }

  Foo(int d1, int d2): data1(d1), data2(d2) {}
};

struct FooComp
{
  bool operator()(const Foo& d1, const Foo& d2)
   {
     return d1.data1 < d2.data1;
   }
};

std::set<Foo,FooComp> myset;
...
(*(myset.begin())).set(3,4);
</code>

Even if you try hard to specify how constant the objects in the
container are, it is still allowed to do things the compiler cannot
catch. I'm not sure if I liked something like: "The Strict Weak Ordering
used in set may not use mutable attributes to compare two elements". I'm
sure that it is a goal of the specification of those associative
containers to not prevent doing things with the containers' elements not
conflicting with the container itself.

Point 1. and 2. from above are too restrictive, and they cannot warrant
anything if mutable comes in. Programmers might be tempted to insert
mutables just to get something running.

Point 3. can be read as: You can do all with the key_type, but maintain
the ordering or the container will fail. This is the important point.
Perhaps it should be clarified like: "The key_type objects within the
container may be changed, but changing them in a way that during
container operations the comparision function produces other results
than during insertion gives UNDEFINED behaviour."

It seems like the most flexible requirements for the key_type in
combination with the comparision cannot be described easily with
language features. It remains to give a rough idea what must hold, and
this is Point 3. Any const anywhere here is just a kludge tempting
programmers to trick. If there is the problem that someone can shoot
himself, then it is better to warn him loudly, instead of trying to stop
him by (in this situation) obscure hindrances he is able to trick out.

Regards

Bernd Strieder

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

On Fri, 12 Jan 2001 09:43:02 GMT, "David Abrahams"
<abrahams@mediaone.net> wrote:

>   At the end of paragraph 5: "Keys in an associative container are
> immutable."

Sorry, I have trouble translating the word "immutable".  It is not
the word "const"; so, I guess that keys are not const.  Map value_type
is pair<Key const, T>, but I guess that the actual element type could
be pair<Key, T> with the Key part being immutable.  Is a key with a
mutable member immutable in an associative container?  What does that
mean?  There is only one occurance of immutable in the standard and
I do not claim to understand that use.

I would like the state to be that keys are not const and that there
is no non-const access path.  The access is a reference and const_cast
may be used to modify the key without any undefined behavior because of
removing const from an actually const object.

I thought that was the intent of the resolutions.  Maybe not.

John

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

On Thu, 11 Jan 2001 21:56:01 GMT, Scott Meyers <smeyers@aristeia.com>
wrote:

> What is a "constant iterator", and how does it differ from a
> const_iterator?

The first is a concept (21.1/4) and the second is an example type.

There are eight iterator concepts.  Input, output, forward, constant
forward, bidirectional, constant bidirectional, random_access, constant
random_access.  The difference between the usual and constant ones is
whether operator* returns a T& or a T const&.  A constant iterator may
not be used where an output iterator is required.  An input iterator is
not a constant iterator (operator* returns a convertable to T not a
T const&).

The following is what I think the intent of the issue resolutions is.
I am not a committee member and was not at any of the meetings where
this was discussed.  My conclusions are from unoffical discussions
including this newsgroup.

For most containers, iterator is a model of an iterator concept and
const_iterator is a model of a constant iterator concept.  For set
and multiset, both iterator and const_iterator are models of a
constant iterator concept.  They both return T const& from operator*
and T const* from operator->.  The elements of the container are not
const but all access paths are const.

This prevents modification of the element in the usual way which is
likely an error and will be detected at compile time.  It also allows
(un)reasonable modification of the element in a safe way with extra
effort.  The consistent over time key comparison requirements are
unenforceable but give rules of sane behavior.

Example:

struct S { int k; int v; };
bool operator< (S const& lhs, S const& rhs) { return lhs.k < rhs.k; }
void f () {
   S s1 = { 1, 20 }, s2 = { 3, 40 };
   set<S> s;
   s.insert(s1);
   s.insert(s2);
   set<S>::iterator i(s.begin());
   i->v = 10;                     // error, sane
   const_cast<int&>(i->v) = 10;   // valid, sane
   const_cast<int&>(i->k) = 2;    // valid, sane
   const_cast<int&>(i->k) = 3;    // valid, not sane
   }

Making the elements const would not allow these sane things because it
is undefined behavior to remove const from a const object.  It would
also not prevent other methods such as mutable members or indirection.

Some of the motives behind the issues:

It is not reasonable to make a member mutable just to put it in a set.
It is not reasonable to split a class to use a map.
It is not reasonable to allow simple modification of set keys.
It is not reasonable to make set unusable for many things.

I think the resolutions are reasonable if they say what I think they
say.  Those are some hard demands with no easy answers.

Any corrections appreciated.

John

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]