Gabriel Dos Reis <dosreis@cmla.ens-cachan.fr> writes:

|>  "Ross Smith" <ross.s@ihug.co.nz> writes:

|>  | There's a point here that everyone seems to be missing (I mentioned it
|>  | in an earlier post, but nobody followed it up): while we're all
|>  | discussing the semantics of set::iterator, nobody seems to have noticed
|>  | that map::iterator has the same problem.

|>  | The container requirements say that value_type must be assignable, but
|>  | map::value_type is pair<const Key, T>, which is not assignable. I
|>  | suspect that even those who favour making set elements mutable would
|>  | balk at doing the same with map keys.

|>  Perhaps, either the container requirements should be fixed or set<>
|>  and map<> should be declared not to be containers.

It's interesting to note that in Java, Map isn't a Collection (Java
containers).  In STL, it is really only a container because it has an
unexpected value_type.  (Unexpected, that is, because it is not what I
would intuitively expect from a map -- it is the only possible
value_type if map is to be a container in the STL sense of the word.)

--
James Kanze                               mailto:kanze@gabi-soft.de
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
Ziegelh   ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Tue, 29 Feb 2000 03:39:05 CST, Herb Sutter <hsutter@peerdirect.com>
wrote:

: On Mon, 28 Feb 2000 20:14:26 CST, jpotter@falcon.lhup.edu (John Potter)
: wrote:
: >On Fri, 25 Feb 2000 21:43:19 CST, "Ross Smith" <ross.s@ihug.co.nz>
: >wrote:
: >: I suspect that even those who favour making set elements mutable would
: >: balk at doing the same with map keys.
: >
: >I don't have your confidence. :)
:
: I'm probably who John means, and he's right. :-)

I wasn't thinking of an element, but of the set.  (pun acceptable :)

: I haven't cast my opinion on this in stone, but: a) I do think set keys
: should be mutable (principally because it's the least change to the
: standard to make it consistent); and b) I do think set and map should
: have the same semantics (principle of least surprise).

This is quite logical and I can agree with point b).  I expect that the
sets of those who advocate one being const without the other would have
cardinality zero.  After all, the two (non)containers are just adapters
of a common implementation.

set<string> mutable_advocates;
mutable_advocates.insert("Herb Sutter");
mutable_advocates.begin()->replace(6, 5, "*hi**t");

Herb knows that there is no insult intended here.  For others :) :)

It does show that modifying an element of a set may be undesirable.
Yes, we can always do it anyway, but it shouldn't be that easy.

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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

kanze@gabi-soft.de writes:

| Gabriel Dos Reis <dosreis@cmla.ens-cachan.fr> writes:
|
| |>  "Ross Smith" <ross.s@ihug.co.nz> writes:
|
| |>  | There's a point here that everyone seems to be missing (I mentioned it
| |>  | in an earlier post, but nobody followed it up): while we're all
| |>  | discussing the semantics of set::iterator, nobody seems to have noticed
| |>  | that map::iterator has the same problem.
|
| |>  | The container requirements say that value_type must be assignable, but
| |>  | map::value_type is pair<const Key, T>, which is not assignable. I
| |>  | suspect that even those who favour making set elements mutable would
| |>  | balk at doing the same with map keys.
|
| |>  Perhaps, either the container requirements should be fixed or set<>
| |>  and map<> should be declared not to be containers.
|
| It's interesting to note that in Java, Map isn't a Collection (Java
| containers).  In STL, it is really only a container because it has an
| unexpected value_type.  (Unexpected, that is, because it is not what I
| would intuitively expect from a map -- it is the only possible
| value_type if map is to be a container in the STL sense of the word.)

I'm wondering:  what is the real benefits of insisting that map<>
should be a container? We've discovered that (by accident or not) it
doesn't fulfill the container requirements.  Should we insist?

In Mathematics there is a recipe to solve an appearently unsolvable
problem.  It consists in saying that "the problem is the solution".
(for example, that is how one constructs the field of rational numbers
as "solutions" of the problems 'ax = b', or the complex number i as one
solution of the problem 'x^2+1=0').
I'm sure that recipe is applicable in engineering.

Instead of trying to relax the container requirements (which one may
consider as risky experiments), there is the possibily of introducing
a concept of "weak container" with ad hoc "weak container requirements"
worded in such a way that set<> and map<> would be weak containers but
not containers.  Doing so should match existing practice.

(Don't tell me that is an infamous hack, I know :-)

--
Gabriel Dos Reis, dosreis@cmla.ens-cachan.fr

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

John Potter wrote :
> With constant iterators, set<> provides an interface which is clearly
> a set.  All of the usual set things are provided by members and the
> algorithms.  I understand this.

I agree. Although keep in mind it is the name "set" that gives you
this idea. The algorithm are not meant to be used only with
set, but with any ordered collection. If the name was only
"ordered_collection" then the discussion would probably be less
difficult.

> With a mutable iterator, we get something other than a set.  It seems
> to be an ordered collection with no protection.  The interface presents
> an ordered collection and the ability to destroy the order with no
> special effort.  Map<> provides a safe ordered collection; however, it
> requires tearing the object apart or duplicating the key part.

I'm working on a wrapper to std::map to get a "no duplication"
map. It's not easy to get right with a nice interface...

> The ordered collection is of considerable interest.  I have tried
> several interfaces over the years and none of them were completely
> satisfying.  I can't accept an ordered collection which presents self
> destruction as a standard interface.

Well, nothing in the standard prevents us from putting a mutable
member that would break even map keys. To self destruct a set you
would have to break some standard rules if it said that the
relative order of the value in the set must not be changed (I
think this is Herb's point of view, he said it better than me).
You can argue that it is easier to break set that map right
now as the standard is written, but not if your implementation
uses an all const approach to set iterators!

> The simplest change is to make the inserts always succeed by doing a
> write when a match is found.  This gives a safe modification but
> involves creating an entire object to modify only a part.  It saves
> the restructuring time of a delete/insert.  It does not generalize
> to multiset.

I like the idea. I think that theorically set and multiset are very
different (is there a multiset theory in mathematics?), so this
is not a problem.

> A safe mutable iterator can be supplied with a proxy object, but this
> violates all of the standard requirements.  Not as bad as vector<bool>.
> Both of these can be done as wrappers to std::set with not much effort.
> The hard part was done in the rb-tree.

Yep. That's why my guess is "what we need is not precisions about
set(although that would be nice), but whole new container(s)
and/or adapters" with, possibly, completly different requirements.

As I'm trying to see what I should use from the standard library
when I need an ordered collection without duplication of keys,
I am always trying to modify the actual collection normal
usage. Be it a vector, a map, a set or a list, there's always
something missing or annoying. That's why I was so "happy"
when Herb said that the set were mutable... I've modify my
std::set header to fit its description, used it for a while...
it's not perfect. I tried using map, but I don't like the
fact that my code becomes littered with ".second" because
the iterators are on pairs...

> Herb mentioned the architecture.  It has been stated that the
> architecture of the associative containers is all wrong anyway.  The
> containers should have been the rb_tree, avl_tree, and hash_table.
> Set, multiset, map, and multimap would then be adapters just like
> stack, queue, etc. for the sequences.  It should be interesting to

I couldn't agree more. But the standard does not require that there
be red-black trees under sets and maps. My guess is the standard
committee didn't want to commit itself to a particular data
structure, because this would preclude using the new (better) one
that could appear some day. (That's why we have std::sort and
std::stable_sort instead of std::quicksort and std::heapsort,
isn't it?)

> get the interface right for trees which do not do any tree things.
> Maybe it would be the desired collections.  I understand that this is
> not an option for the standard now, nor likely in the future.

I don't know about the future, but for now you're probably right.

> It should be clear that I favor the const iterator.  I am also
> interested in the other view.  What will the standard say is the
> interesting question, I'm sure how to say it will work out.

I would favor... a clear decision as soon as possible :-)

--
Michel Michaud (micm19@removethis.mail2.cstjean.qc.ca)
http://www3.sympatico.ca/michel.michaud

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

There's a point here that everyone seems to be missing (I mentioned it
in an earlier post, but nobody followed it up): while we're all
discussing the semantics of set::iterator, nobody seems to have noticed
that map::iterator has the same problem.

The container requirements say that value_type must be assignable, but
map::value_type is pair<const Key, T>, which is not assignable. I
suspect that even those who favour making set elements mutable would
balk at doing the same with map keys.

It looks to me as though, regardless of how the set issue is resolved,
the "value type must be assignable" rule *can't* be rescued without
breaking map.

--
Ross Smith <ross.s@ihug.co.nz> The Internet Group, Auckland, New Zealand
========================================================================
   "So that's 2 T-1s and a newsfeed ... would you like clues with that?"
                                                       -- Peter Da Silva


---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Fri, 25 Feb 2000 21:43:19 CST, "Ross Smith" <ross.s@ihug.co.nz>
wrote:

: There's a point here that everyone seems to be missing (I mentioned it
: in an earlier post, but nobody followed it up): while we're all
: discussing the semantics of set::iterator, nobody seems to have noticed
: that map::iterator has the same problem.

Not quite, since map has const and non-const iterators for sure.

: The container requirements say that value_type must be assignable, but
: map::value_type is pair<const Key, T>, which is not assignable.

Take a look at the issues list.  It's broken but NAD as I remember.
The set issue is open.

: I suspect that even those who favour making set elements mutable would
: balk at doing the same with map keys.

I don't have your confidence. :)

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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Mon, 28 Feb 2000 20:14:26 CST, jpotter@falcon.lhup.edu (John Potter)
wrote:
>On Fri, 25 Feb 2000 21:43:19 CST, "Ross Smith" <ross.s@ihug.co.nz>
>wrote:
>: I suspect that even those who favour making set elements mutable would
>: balk at doing the same with map keys.
>
>I don't have your confidence. :)

I'm probably who John means, and he's right. :-)

I haven't cast my opinion on this in stone, but: a) I do think set keys
should be mutable (principally because it's the least change to the
standard to make it consistent); and b) I do think set and map should
have the same semantics (principle of least surprise). In my October
1999 C++ Report column, which incidentally sparked this thread, I
concluded:

  "So what rule should we follow to ensure that we're using
  associative containers correctly [in terms of keys]?
  Although it would be nice to codify more specific
  discipline, const alone won't do it (and, at any rate,
  set and map have inconsistent 'key constness' policies),
  and simple coding rules alone won't do it. So we can't
  really be much more specific than to simply state the
  requirement and add: 'You have to know what you're doing.'

    "The Associative Container 'Key Rule':
    "Once a key has been inserted into an associative
    container, that key must never change its relative
    position in the container."

(Note that you can always change a map key anyway using a const_cast,
and that in many cases you can change a map key anyway even without a
const_cast. See the article and the prior parts of this thread for
examples; I don't have time to get dragged into this discussion again at
the moment, but maybe in a couple of months I'll have cycles again if
this thread is still active.)

To the above guideline, I would now add the footnote that several
implementations do not even allow you to change the key, but I would
still state the core advice the same way because IMO it (with that
footnote) best documents the status quo.

Herb

---
Herb Sutter (mailto:hsutter@peerdirect.com)

CTO, PeerDirect Inc. (http://www.peerdirect.com)
Chair, ANSI H2 Ad-Hoc for SQL Part 12: SQL/Replication
  (Replication working group, ANSI SQL committee)
Editor-in-Chief, C++ Report (http://www.creport.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Ross Smith" <ross.s@ihug.co.nz> writes:

| There's a point here that everyone seems to be missing (I mentioned it
| in an earlier post, but nobody followed it up): while we're all
| discussing the semantics of set::iterator, nobody seems to have noticed
| that map::iterator has the same problem.
|
| The container requirements say that value_type must be assignable, but
| map::value_type is pair<const Key, T>, which is not assignable. I
| suspect that even those who favour making set elements mutable would
| balk at doing the same with map keys.

Perhaps, either the container requirements should be fixed or set<>
and map<> should be declared not to be containers.

--
Gabriel Dos Reis, dosreis@cmla.ens-cachan.fr

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

kanze@gabi-soft.de wrote:
>
> Herb Sutter <hsutter@peerdirect.com> writes:
....
> If it were a technical question, you'd be right.  It is, however, a
> political question: how will the LWG (and the committee) vote.  And if
> influent members of the LWG (and I suppose Matt Austen would count as
> one) say that they are not sure how the vote would go, then one must
> suppose that it is not certain how the vote would go, regardless of the
> technical reasons.
>
> Note here that under technical reasons, I don't mean just programming
> technical reasons, but also procedural technical reasons.  You indicate
> several reasons why you are sure that the original intent is what you
> claim -- in the end, however, what counts is not the actual original
> intent (which, strictly speaking, can't really be known anyway without
> being able to read minds), but what the people actually voting on the
> issue think the original intent was.
>
> I think Michel's point is really well taken.  You've given a number of
> technical reasons why a committee member *should* vote the way you
> claim.  You haven't given the slightest evidence that any of the
> committee members actually agree with your reasons.  What I think Michel
> was looking for was something more along the lines of: I conducted a
> poll of the members at the last meeting, and 95% were in favor of
> solution x.

The only thing worth doing a poll for is to get the final decision. The
thing that's actually worth talking about is the reasons for the votes.
If there are in fact people who would vote differently than Herb
expects, presumably they have a reason for doing so. The thing worth
discussing is not "how many people will vote against this", but "why do
those people want to vote against it". Can you give those reasons, or
identify who they are and ask them to give their reasons?
I'm not arguing for or against Herb's position. I can see enough of the
points for both sides that I haven't made up my mind on this one yet.
I'm just saying that some of the responses he's received haven't been to
the point.

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper <kuyper@wizard.net> writes:

> > I think Michel's point is really well taken.  You've given a number of
> > technical reasons why a committee member *should* vote the way you
> > claim.  You haven't given the slightest evidence that any of the
> > committee members actually agree with your reasons.  What I think Michel
> > was looking for was something more along the lines of: I conducted a
> > poll of the members at the last meeting, and 95% were in favor of
> > solution x.
>
> The only thing worth doing a poll for is to get the final decision. The
> thing that's actually worth talking about is the reasons for the votes.
> If there are in fact people who would vote differently than Herb
> expects, presumably they have a reason for doing so. The thing worth
> discussing is not "how many people will vote against this", but "why do
> those people want to vote against it". Can you give those reasons, or
> identify who they are and ask them to give their reasons?
> I'm not arguing for or against Herb's position. I can see enough of the
> points for both sides that I haven't made up my mind on this one yet.
> I'm just saying that some of the responses he's received haven't been to
> the point.

Depends on what the point is!  If the question is whether this issue
has already been settled, then the short answer is no.  All you need
is someone who was there at the Santa Cruz library working group
meeting where we discussed this: some people strongly favored changing
the text in the container requirements to make it clear that
C::iterator is not necessarily a modifiable iterator, others strongly
favored changing the std::set signatures so that they would make sense
even if set<>::iterator and set<>::const_iterator are two distinct
types where set<>::iterator is a modifiable iterator and
set<>::const_iterator is not.  People on both sides of the discussion
(and I include myself here) were, I think, surprised to find that
there was anyone who disagreed with them.  I'm sure that's why this
problem was overlooked for so long: everyone thought their position
was "obviously" true.

How will the library working group resolve this?  In the short term,
it probably won't.  The committee tries very hard to make decisions
that everyone agrees to be right, or at least that everyone can live
with.  It won't be resolved just by taking a vote and adopting
whatever position wins by 51%.

Speaking in some generality here, what we've got is a contradiction
between the most obvious reading of the container requirements and the
most obvious reading of the set<> member function signatures.  The
committee could in principle change one, either, neither (if it
decides that there isn't a contradiction, that the existing words are
consistent when properly interpreted), or both.

Some of the things that the library working group tends to think about:
 (1) What would be the smallest change to the text of the standard?
 (2) What was the original intent?  Which of these things was really
     meant?  This has several subpieces:
     (a) What was the original intent in the HP STL?  What did the words
          and the code actually say?
     (b) What did the committee think it was voting on?
     (c) Was there ever an explicit decision on the matter on the part
         of the committee?  Did anyone ever vote to change what was
         there before?
 (3) What do existing implementations do?
 (4) Which answer is technically best?  If we were starting from
     scratch, would we want set<> to have modifiable iterators?

The problem is that none of those questions have very clear answers.
I personally think it is better design for set<>::iterator not to be
modifiable, becuase I want errors like "std::reverse(s.begin(),
s.end())" and "std::remove(s.begin(), s.end(), 7)" to be caught at
compile time.  Not everyone agrees with me that this is technically
the best answer, though, and even if everyone did, it's only one of
the factors that the committee will consider.

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Thu, 24 Feb 2000 21:48:56 CST, Matt Austern <austern@sgi.com> wrote:

: Some of the things that the library working group tends to think about:

Thank you for bringing this discussion back to the standard issue.

:  (1) What would be the smallest change to the text of the standard?

Ouch.  Those of us who only observe, forget about this.  We need that
reminder.

:  (2) What was the original intent?  Which of these things was really
:      meant?  This has several subpieces:
:      (a) What was the original intent in the HP STL?  What did the words
:           and the code actually say?

I went back to the 1994 HP docs and found, to my surprise, that it does
state the contradiction more clearly than the standard. :)  It says
that container::iterator points to X::reference,
container::const_iterator points to X::const_reference and that
set::const_iterator is set::iterator.  The code is clear since it does
not state requirements.  No conclusion, just some data for those who
may be interested.

:      (b) What did the committee think it was voting on?
:      (c) Was there ever an explicit decision on the matter on the part
:          of the committee?  Did anyone ever vote to change what was
:          there before?
:  (3) What do existing implementations do?
:  (4) Which answer is technically best?  If we were starting from
:      scratch, would we want set<> to have modifiable iterators?

As a user, this is my interest.

With constant iterators, set<> provides an interface which is clearly
a set.  All of the usual set things are provided by members and the
algorithms.  I understand this.

With a mutable iterator, we get something other than a set.  It seems
to be an ordered collection with no protection.  The interface presents
an ordered collection and the ability to destroy the order with no
special effort.  Map<> provides a safe ordered collection; however, it
requires tearing the object apart or duplicating the key part.

The ordered collection is of considerable interest.  I have tried
several interfaces over the years and none of them were completely
satisfying.  I can't accept an ordered collection which presents self
destruction as a standard interface.

The simplest change is to make the inserts always succeed by doing a
write when a match is found.  This gives a safe modification but
involves creating an entire object to modify only a part.  It saves
the restructuring time of a delete/insert.  It does not generalize
to multiset.

A safe mutable iterator can be supplied with a proxy object, but this
violates all of the standard requirements.  Not as bad as vector<bool>.

Both of these can be done as wrappers to std::set with not much effort.
The hard part was done in the rb-tree.

Herb mentioned the architecture.  It has been stated that the
architecture of the associative containers is all wrong anyway.  The
containers should have been the rb_tree, avl_tree, and hash_table.
Set, multiset, map, and multimap would then be adapters just like
stack, queue, etc. for the sequences.  It should be interesting to
get the interface right for trees which do not do any tree things.
Maybe it would be the desired collections.  I understand that this is
not an option for the standard now, nor likely in the future.

It should be clear that I favor the const iterator.  I am also
interested in the other view.  What will the standard say is the
interesting question, I'm sure how to say it will work out.

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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Mon, 14 Feb 2000 23:49:03 CST, Michiel Salters <salters@lucent.com>
wrote:
>Would it be legal for a set to calculate a hash of the bits of each T,
>and try to use that as a shortcut - falling back to a red-black tree
>if it doesn't work due to collisions?
>In general, this is a very dangerous path, the set wouldn't be able to
>create a good hash for many T's. But only trying shouldn't hurt, and
>might be faster on average.

A hash_set is a possible additional container, but I don't think set can
be implemented using an underlying hash table structure if that's what
you mean -- not even as an optimization.

For one thing, set is required to use the provided comparator (or
less<>), not a hash. This is a visible difference to the user because it
changes the iterator traversal ordering. Even if you used a hash somehow
as an optimization, the iterator traversal ordering must continue to use
the provided comparator ordering (or less<>) and meet all the usual set
complexity requirements.

>I don't think this scheme is actually in existence. Then again,
>I don't think there are C++ compilers with CHAR_BIT unequal to
>1<<N, but disallowing them because they don't exist is also not
>done.
>
>Considering the fact that the STL was designed to be extended, I'd
>personally consider to solve this with YACC (Yet Another C++
>Container :)

Right. There are implementations of hash_set and hash_map that will
(almost surely) someday appear in the standard, but they must be
different from set and map because I think they cannot meet the set and
map requirements, and they have some minor operational/interface
differences besides.

Cheers,

Herb

---
Herb Sutter (mailto:hsutter@peerdirect.com)

CTO, PeerDirect Inc. (http://www.peerdirect.com)
Chair, ANSI H2 Ad-Hoc for SQL Part 12: SQL/Replication
  (Replication working group, ANSI SQL committee)
Editor-in-Chief, C++ Report (http://www.creport.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Mon, 14 Feb 2000 23:48:58 CST, "Ross Smith" <ross.s@ihug.co.nz>
wrote:
>Perhaps the issues list has been updated since you last looked at it.
>The current version has three proposed resolutions, one of which would
>make set elements immutable. (Did you mean to imply that you considered
>that one unreasonable?)

Yes. The issue itself contains not just one but two notes that Option B
probably is not a good idea and definitely does not solve the problem.
AFAICS the only currently-listed options that appear reasonable (and
appear to have a reasonable chance of being adopted) are A and C.

Herb

---
Herb Sutter (mailto:hsutter@peerdirect.com)

CTO, PeerDirect Inc. (http://www.peerdirect.com)
Chair, ANSI H2 Ad-Hoc for SQL Part 12: SQL/Replication
  (Replication working group, ANSI SQL committee)
Editor-in-Chief, C++ Report (http://www.creport.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <2afras49jfhij237etmpvs5qhbli3j7568@4ax.com>,
hsutter@peerdirect.com says...

[ ... ]

> Second (minor), I wonder whether you can have any confidence that you're
> actually implementing an optimization without changing the set interface
> to let the user supply a hash operation. After all, in general you can't
> pick a well-performing hash function that will be good for all data (you
> could pick a cryptographically secure hash -- message digest -- which
> among its other properties will guarantee even distribution of hash
> values regardless of input, but such a digest is much more expensive to
> compute than a typical hash).

This still wouldn't work -- along with ensuring an even distribution
of different values, the hash function would be responsible for
ensuring the equal values were treated as identical.  For an obvious
example, if 1's complement is in use, +0 and -0 should be equal, but
have different bit patterns, so they'll hash entirely differently.
For integers, two's complement is common enough that most people can
probably afford to ignore other possibilities, but for floating-point,
other representations are fairly common.

--
    Later,
    Jerry.

The universe is a figment of its own imagination.

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Jerry Coffin <jcoffin@taeus.com> writes:

|>  In article <2afras49jfhij237etmpvs5qhbli3j7568@4ax.com>,
|>  hsutter@peerdirect.com says...
|>
|>  [ ... ]
|>
|>  > Second (minor), I wonder whether you can have any confidence that you're
|>  > actually implementing an optimization without changing the set interface
|>  > to let the user supply a hash operation. After all, in general you can't
|>  > pick a well-performing hash function that will be good for all data (you
|>  > could pick a cryptographically secure hash -- message digest -- which
|>  > among its other properties will guarantee even distribution of hash
|>  > values regardless of input, but such a digest is much more expensive to
|>  > compute than a typical hash).
|>
|>  This still wouldn't work -- along with ensuring an even distribution
|>  of different values, the hash function would be responsible for
|>  ensuring the equal values were treated as identical.  For an obvious
|>  example, if 1's complement is in use, +0 and -0 should be equal, but
|>  have different bit patterns, so they'll hash entirely differently.
|>  For integers, two's complement is common enough that most people can
|>  probably afford to ignore other possibilities, but for floating-point,
|>  other representations are fairly common.

On the other hand, we're talking about an optimization that the compiler
might only want to make in certain cases, like when profiling
information showed intensive use of find.  The profiling information,
combined with the compilers knowledge of the machine types, could permit
a particularly sophisticated compiler to derive a good hash function,
and forgo the hashing when it couldn't.

Speaking about sophisticated compilers, however, even given the advanced
state of compiler technology today, I really don't expect to see
anything like this in my lifetime, so the argument is really standard
sophistry.

--
James Kanze                               mailto:kanze@gabi-soft.de
Conseils en informatique orientie objet/
                   Beratung in objektorientierter Datenverarbeitung
Ziegelh|ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Herb Sutter wrote:

> On Sat, 19 Feb 2000 04:30:49 CST, Michiel Salters <salters@lucent.com>
> wrote:
> >I'm aware of the hash_set as provided by SGI's STL extension. I was refering
> >to a hypothetical compiler which - on determining that in a given program
> >sets were often searched using find - would add part of a hash_set to the
> >internals of set, besides (not i.s.o ) the red-black tree. When an element
> >was found, you'd be home early, but if not, you'd need to search somewhat
> >longer.

> Ah, now I see: You want to keep a set as-is, but also under the covers
> maintain a hash table for find(). That should be cool, and it's a neat
> idea, but I have two reservations (purely related to standards
> conformance, not to whether this could be a good optimization or not):

> First (major), as I mentioned in the last post, I still wonder whether
> this can be done and still maintain set's complexity requirements. For
> example, I don't think you can guarantee O(log N) insertion into a hash
> table. For example, what if you hit a condition where you have to grow?
> Or even if you don't have to grow, what if your hash function happens to
> be bad for the data and you go linear? So I think you can provide such
> an optimization under the covers and meet set's interface requirements,
> but not its complexity requirements.

The fact that the hash is used purely as an optimalization, coupled with the
fact that compiler magic is allowed, means that O( log N ) insertion is not
required for the hash table. Remember, we can't rely on the hash table to be
perfect - equivalence classes can't be distinguished - so we don't need to
update it right away. On a multi-threading system we can stuff all the
hashtable updates into a low-priority queue.

I'd base the hash function on the bits actually used in the comparison, which
would eliminate one source of bad hash performance. Again, this requires
compiler magic, but it can eliminate some big members.

The hashtable would be purely opportunistic, but IIRC hashtables have some
(minor) advantages when multiple processors can jointly search them.

Michiel Salters

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Herb Sutter <hsutter@peerdirect.com> writes:

|>  On Sat, 12 Feb 2000 07:14:53 CST, Michel Michaud
|>  <micm19@gest-netware.cstjean.qc.ca> wrote:
|>  >But thank you for making your arguments known. I think this
|>  >is what you should have put in C++ Report in the first place
|>  >but better late than never.
|>
|>  You are, of course, welcome to your opinion, and I'm sorry to have
|>  disappointed any reader. I know you keep saying the above, but I don't
|>  yet accept it. Let me try to explain one last time.
|>
|>  To me, the above says: "But thank you for all those detailed reasons you
|>  just gave to show why your belief is accurate and doesn't rely on
|>  anything controversial/undecided. That's nice, Herb, but instead of
|>  addressing any of them I'll just repeat vaguely that some people
|>  disagree."
|>
|>  I don't think that's good enough -- WHY do they disagree, and with what?

If it were a technical question, you'd be right.  It is, however, a
political question: how will the LWG (and the committee) vote.  And if
influent members of the LWG (and I suppose Matt Austen would count as
one) say that they are not sure how the vote would go, then one must
suppose that it is not certain how the vote would go, regardless of the
technical reasons.

Note here that under technical reasons, I don't mean just programming
technical reasons, but also procedural technical reasons.  You indicate
several reasons why you are sure that the original intent is what you
claim -- in the end, however, what counts is not the actual original
intent (which, strictly speaking, can't really be known anyway without
being able to read minds), but what the people actually voting on the
issue think the original intent was.

I think Michel's point is really well taken.  You've given a number of
technical reasons why a committee member *should* vote the way you
claim.  You haven't given the slightest evidence that any of the
committee members actually agree with your reasons.  What I think Michel
was looking for was something more along the lines of: I conducted a
poll of the members at the last meeting, and 95% were in favor of
solution x.

--
James Kanze                               mailto:kanze@gabi-soft.de
Conseils en informatique orientie objet/
                   Beratung in objektorientierter Datenverarbeitung
Ziegelh|ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Sun, 20 Feb 2000 07:15:07 CST, Jerry Coffin <jcoffin@taeus.com>
wrote:
>In article <2afras49jfhij237etmpvs5qhbli3j7568@4ax.com>,
>hsutter@peerdirect.com says...
>> First (major), as I mentioned in the last post, I still wonder whether
>> this can be done and still maintain set's complexity requirements. For
>> example, I don't think you can guarantee O(log N) insertion into a hash
>> table. For example, what if you hit a condition where you have to grow?
>> Or even if you don't have to grow, what if your hash function happens to
>> be bad for the data and you go linear? So I think you can provide such
>> an optimization under the covers and meet set's interface requirements,
>> but not its complexity requirements.
>
>I think this part is pretty easy to handle: instead of using linked
>lists for hash collision, you can use balanced trees.  When you insert
>a new object into the set, you never have to expand the hash table
>itself at all.  Instead, you can insert the object into the tree.
>Your overall complexity should be something like O(1)+O(log N/n) where
>N is the total number of items, and n is the number of trees in the
>table.  The O(1) is normally ignored, so I don't see a problem with
>meeting the complexity requirements.

This may help with bad hash functions where you end up linear (although
I have to question why we're bothering with the hash table then in the
first place), but how does it help if you have to grow the hash table?
Insertion can't be O(logN) then, can it? (I know there are some
implementations that can grow without rehashing everything, but I don't
offhand remember whether they're O(logN). If they can, that would
satisfy this point.)

Herb

---
Herb Sutter (mailto:hsutter@peerdirect.com)

CTO, PeerDirect Inc. (http://www.peerdirect.com)
Chair, ANSI H2 Ad-Hoc for SQL Part 12: SQL/Replication
  (Replication working group, ANSI SQL committee)
Editor-in-Chief, C++ Report (http://www.creport.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <bba0bs8rf1sbs04gug8m0j1bb0prcq6054@4ax.com>,
hsutter@peerdirect.com says...

[ using balanced trees to resolve hash collisions ]

> This may help with bad hash functions where you end up linear (although
> I have to question why we're bothering with the hash table then in the
> first place), but how does it help if you have to grow the hash table?

They help by simply avoiding the problem: if you resolve collisions
in trees, you can simply ignore the possibility of growing the hash
table at all.  Obviously to be of much good, you have to have at
least a _somewhat_ reasonable estimate of the amount of data you're
going to store, or you end up with most tree-like characteristics
instead of the trees only being an insurance against really bad
performance.

> Insertion can't be O(logN) then, can it? (I know there are some
> implementations that can grow without rehashing everything, but I don't
> offhand remember whether they're O(logN). If they can, that would
> satisfy this point.)

That was part of the point of my later question: if you grew the
table by a constant factor, you should be able to achieve amortized
constant time, though an individual insertion might be slower than
that.  I'm pretty sure this wouldn't meet the requirements _exactly_
as they're currently written, but I think the requirements could be
rewritten to allow it without significantly affecting current usage.

--
    Later,
    Jerry.

The universe is a figment of its own imagination.

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <38AF013F.C5B8FB5@acm.org>, petebecker@acm.org says...

[ ... ]

> But with insetions and lookups running in O(N) you've lost the benefit
> of using a hash table, which does insertions and lookups in constant
> time. All you accomplish with this technique is to reduce the
> multiplier.

Yes and no -- keep in mind that a hash table is only O(1) as long as
you can estimate the size needed well enough to ensure that the table
is as large as the data.  Using the common method of resolving
collisions by using linked lists, this theoretically breaks down
linear time if you overfill the table badly enough and/or use a
terrible hash function that happens to produce lots of collisions.

Using a table of trees, you reduce the breakdown from linear to
logarithmic.  If you estimate your size to at least a reasonable
degree of accuracy, you can get the benefit of expected constant-time
lookup combined with a worst-case lookup in logarithmic time.

Thinking about it, that brings up an interesting question: would
amortized constant time be considered to meet the requirements for
logarithmic time?  In the long term it should never be greater than
logarithmic, but for an individual insertion it might be substantially
longer.

If this was allowed, you could use a table with gradual resizing...

--
    Later,
    Jerry.

The universe is a figment of its own imagination.

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"John Potter" <jpotter@falcon.lhup.edu> wrote in message
news:38a54296.10924559@news.csrlink.net...
>
> You missed the point.  It says if you modify the key, nothing bad will
> happen.  You did not modify the key.

Yes, I did. Read the code again.

--
Ross Smith <ross.s@ihug.co.nz> The Internet Group, Auckland, New Zealand
========================================================================
    "Be careful about using the following code -- I've only proven
    that it works, I haven't tested it."           -- Donald Knuth


---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Thanks John, this was very helpful.

On Sun, 13 Feb 2000 10:45:23 CST, jpotter@falcon.lhup.edu (John Potter)
wrote:
>: Q1: Can you modify a set's contents through set::iterator?
>:
>: A1: Yes. The container requirements specify that container::iterator be
>: an "iterator type pointing to (non-const) T."
>
>The container requirements are wrong.

Aha! Okay, this is the kind of opinion I needed to know existed.

With this statement, plus a similar one in a simultaneous email from
Matt, I now understand that some people actually do want to change the
(associative) container requirements. That's cool, and I will be
following with interest the discussion about that both here and within
the committee. Because this would be a large change with many
ramifications, I think there are some issues that need to be ironed out
-- such as what happens if we declare that "an associative container is
not a container" and possible impact on map and on existing user code --
but I think that this could be doable.

In my article I was merely trying to document what the standard does
today, in a way that would also include the proposed changes in issue
103 (note that changing the container requirements hasn't been one of
the proposed resolutions to date).

>The 1994 STL documentation (and I think CD1) contained:
>   typedef iterator const_iterator;
>and it was implemented.

Thanks for the background. I used to have a copy of the HP STL and I've
been meaning to get another for comparison.

>Alternatively, the committee forgot that set was a set when changing the
>requirements.  Keeping the contianers self consistent while factoring
>out requirements is not an easy task.

Could be, and absolutely, respectively.

>: Does the above sound reasonable? What parts are wrong or misinformed or
>: misguided? Comments, corrections, and whacks upside the head are
>: welcome.
>
>Sounds reasonable and only slightly irrational.

Fair enough. :-)

>There is a great desire for a table<> in the standard which acts like
>a relational database table.  Map<> is close, but it forces breaking
>the entity into key and attribute pairs.  Set<> keeps them together, but
>has no update capabilities.  Neither of them was designed to be table<>.
>
>IMO, the set iterator issue is a halfbaked attempt to make a table from
>set.  It will not hurt set, but it will also not produce table.

This is an interesting way of looking at it.

>I think those who find your arguements a problem are thinking about
>the set not some patch to make the standard consistent.  I've ignored
>the real need for the standard to say something which is consistent.
>It doesn't need to please anyone and whatever is done will not please
>everyone.

Okay, granted. Of course I'm the opposite, in that I have always
approached this (and all other issues since Nov97) from the
standards-consistency point of view: "What does the standard say clearly
and unambiguously? If anything is inconsistent, what is the least
possible reasonable change to make the standard consistent?"

Coming from that point of view, I have so far concluded the following:
First, if possible, assume that the container requirements are correct;
after all, the container requirements are an architectural decision and
therefore changing them is a greater change than changing a function
signature. Then the standard is entirely self-consistent, with the
exception that set::find() and the three others do not conform to the
associative container requirements, and the straightforward fix is to
make them like map's.

(Note that the alternative, namely changing the container requirements,
is a far more sweeping change: If you change the associative container
requirements, you need to change map similarly, and you declare that an
associative container is not a container. You might also break user code
that relied on old requirements that are no longer guaranteed, but if
all existing implementations have ignored the standard and done it the
other way, this risk goes away. This alternative, though a greater
change, might indeed better reflect existing practice; but I've seen no
paper or issues list entry proposing anything like this yet, and await
such a proposal with interest and welcome.)

Unless you call into question the container requirements, then, the
current standard does say clearly and unambiguously that set::iterator
must point to non-const T, that set::const_iterator must point to const
T, and therefore that they cannot be the same thing. Now, that's the way
it is, but I accept that it may not be what the committee intended, and
indeed it looks like maybe it isn't and that some implementations are
not implementing this detail of the standard and instead hewing to what
may have been intended.

Coming back to my Oct99 article, I feel I do have to publish at least
one amplification: My saying that set::iterator points to non-const T,
while supported in the standard, actually does NOT reflect many popular
implementations and books and may actually not have been intended by the
committee. That's certainly worth noting. Thanks to (in alpha order)
John, Matt, Michel, Nico, and any others I've missed, for helping me to
better understand the state of the compiler market. Given that caveat
about what implementers are actually doing, I still think that the
current standard itself, and all reasonable proposed changes that now
exist in committee documents, are accurately reflected in what I wrote
in Oct99 -- but either implementations have to conform, or the standard
has to change, and if the latter then as soon as more fundamental
changes (such as changing the container requirements) are proposed via
an issue on the issues list or a paper, then I need to report those,
too.

Does that go far enough? Did I miss anything?

Thanks,

Herb

---
Herb Sutter (mailto:hsutter@peerdirect.com)

CTO, PeerDirect Inc. (http://www.peerdirect.com)
Chair, ANSI H2 Ad-Hoc for SQL Part 12: SQL/Replication
  (Replication working group, ANSI SQL committee)
Editor-in-Chief, C++ Report (http://www.creport.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Ross Smith wrote:

> "John Potter" <jpotter@falcon.lhup.edu> wrote in message
> news:38a54296.10924559@news.csrlink.net...

> > You missed the point.  It says if you modify the key, nothing bad will
> > happen.  You did not modify the key.

> Yes, I did. Read the code again.

You tried to modify the key, but failed:

with std::set<Foo>::iterator i;

i->b = 1; // fails

Try:

const_cast<Foo>(*i).b = 1; // This will work.

The question raised was, "does this break set."

Therefore g++ falls in the big category of "Could work
with minor modifications". The algorithm of std::set
continues to work, there are just minor syntactic issues.

Michiel Salters

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Herb Sutter" <hsutter@peerdirect.com> wrote in message
news:sihcask99n6rrocskdc9ihp1lh305j4bbu@4ax.com...
>
> >In your column on set and map in C++ Report
> >(vol.11 no 9), you seem very sure that
> >set::iterator are not supposed to be the same
> >as a const_iterator. That std::iterator should
> >allow you to modify the value in the set.
>
> The standard's container requirements are clear that this should be
so.
> What I didn't know (and isn't yet reflected in any active issues list)
> is that some people think the container requirements are wrong -- this
> is a major thing, because the container requirements are an
> architectural issue.

Well, the containers section of the standard is definitely wrong
somewhere, because the description of the map<> template doesn't meet
the container requirements (value_type is not assignable).

> I think the correct characterization is: The current standard is
clear,
> and the open issue (#103) has two reasonable proposed resolutions both
> of which would add text to bless this explicitly -- but I now know
there
> are people who think the standard should be changed in this respect
and
> who I think will be writing up new related issues with different and
> more sweeping proposed resolutions.

Perhaps the issues list has been updated since you last looked at it.
The current version has three proposed resolutions, one of which would
make set elements immutable. (Did you mean to imply that you considered
that one unreasonable?)

It's always seemed clear to me that set elements should be immutable.
That's the way sets originally worked in the HP STL (and the way they
still work in the SGI STL), and is consistent with the way maps work,
and with the concepts behind the set. As I pointed out above, the
standard map semantics (which everyone seems to agree on) are
inconsistent with the standard container requirements anyway. If set
keys are allowed to be mutable when map keys are not, associative
containers become a rather fuzzy and blurred concept.

--
Ross Smith <ross.s@ihug.co.nz> The Internet Group, Auckland, New Zealand
========================================================================
    "Be careful about using the following code -- I've only proven
    that it works, I haven't tested it."           -- Donald Knuth


---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Herb Sutter wrote:
>
> On Fri, 11 Feb 2000 04:10:29 CST, Michel Michaud
> <micm19@gest-netware.cstjean.qc.ca> wrote:
> >This is what you said in C++ Report. This is what I'd like. This
> >is what all other posters (here and in another newsgroup) aren't
> >so sure.

> Then let me see if I can inject some clarity here. I'll lay it out point
> by point, and hopefully when people knock me down I will be able to see
> exactly what is being disagreed with. Fair enough? (Please read all five
> questions and answers before you start to reply, because I believe I am
> addressing all the points raised so far in this thread.)

> The two main questions are:

> Q1: Can you modify a set's contents through set::iterator?

> A1: Yes. The container requirements specify that container::iterator be
> an "iterator type pointing to (non-const) T."

> Q2: If you do modify a key in a set (whether through an iterator or in
> some other way), is it okay to change it in any old way as long as you
> don't change its ordering relative to all other keys in the container?

> A2: Yes. Today, this rule pragmatically will work on all implementations
> I know of or can imagine (to shoot this belief down, you need only show
> or describe a single counterexample). Tomorrow, this answer is
> compatible with all feasible proposed resolutions currently being
> considered for library issue 103 (to shoot this part down, you need only
> describe why it's incompatible with Option A or Option C).

Would it be legal for a set to calculate a hash of the bits of each T,
and try to use that as a shortcut - falling back to a red-black tree
if it doesn't work due to collisions?
In general, this is a very dangerous path, the set wouldn't be able to
create a good hash for many T's. But only trying shouldn't hurt, and
might be faster on average.

However, such an implementation would suffer from changes to
non-significant bits. This is currently disallowed; which is
essential to the scheme I proposed.

I'm not sure if the scheme is smart; in particular with user
defined equality. I.e. there may be an infinite number of objects
equal to some set member, only one of which hashes to the set
member. On the other hand, since std::set is part of the
implementation much trickery is allowed (creating a custom hash
 function using dereferenced pointers in T is allowed, even if
 that would potentially induce undefined behavior on other
 compilers).

I don't think this scheme is actually in existence. Then again,
I don't think there are C++ compilers with CHAR_BIT unequal to
1<<N, but disallowing them because they don't exist is also not
done.

Considering the fact that the STL was designed to be extended, I'd
personally consider to solve this with YACC (Yet Another C++
Container :) or by requiring the T's to make the non-relevant
parts mutable, so all possible modifying functions can still be
const. The latter may sound extreme, but consider: If the object
before and after the operation still sorts to the same place, has
it really changed? I can imagine many places where this holds.
Unfortunately I know some cases in which this breaks: If we want
a collection of objects stored in two sets, each sorted according
to a different criterium.



> Finally, note that everything stated in this article about set/map
> applies to multiset/multimap, too.
> Herb


I think that my proposal is only suited for std::set, I haven't
considered the issues with std::multiset. Basically it seems my
prposal would be grossly inefficient for multiset, since
multiset is more likely to be used with type having equivalence
classed with more than one member (Why else would you store
multiple equivalent/identical objects in a multiset? I can imagine
some rare cases.)

--
Michiel Salters

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Francis Glassborow wrote <9E4aNRBCwXp4EwmX@robinton.demon.co.uk>...
>In article <38A46123.B98E00F6@mail2.cstjean.qc.ca>, Michel Michaud
><micm19@gest-netware.cstjean.qc.ca> writes
>>(For example, I just received "C & C++ Code Capsules" and,
>>although it may be a good book, I find it amazing it was reviewed
>>by well known people, proclaims 100% ISO C++ compatibility and
>>still uses "main()" without int throughout).
>
>If that was the worst fault you could find with it I would not wish to

I've now read about two third of the book and peeked at the rest.
And no, it is not the worst fault! This now seems very minor in
fact... I am not going to start book reviews in this newsgroup,
but this is, IMHO, "not a good" book (bad structure, unexistent
target audience, errors, misconceptions, etc.). I may changed
my mind to "bad" book after I finish reading it...

>clutter a review with such trivia.  Actually when I reviewed it I
>strongly objected to its title (the C in the title is, IMO, completely
>misleading)

A big problem of this book, is probably that there is too much
C-ism (and just plain C) for a C++ programmer. So I think the title
would be worst without the reference to C. Or maybe every book about
C should put C++ somewhere in their title (or exclusively) because
most C programs can be compiled under a C++ compiler...

>Had the author used void main() you can be certain that I would have
>been commenting in a review but...

Well, this is very interesting point of view. I think there are
many more C++ compilers that will object to implicit int, than would
to void main. In either cases, it's not proper C++, so why should
you accept one and reject the other? Many authors (some good) used
the void main thing at one time, so maybe it is "fresher" to use
another bad way to declare main ? :-)

(For the record, the author knows the "no implicit int" rule of C++,
he says so in his chapter on the differences between C and C++!)


--
Michel Michaud (micm19@removethis.mail2.cstjean.qc.ca)
http://www3.sympatico.ca/michel.michaud

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Mon, 14 Feb 2000 13:37:57 CST, Herb Sutter <hsutter@peerdirect.com>
wrote:

: >: Does the above sound reasonable? What parts are wrong or misinformed or
: >: misguided? Comments, corrections, and whacks upside the head are
: >: welcome.
: >
: >Sounds reasonable and only slightly irrational.
:
: Fair enough. :-)

Thanks for noting my invisible smiley.

: >There is a great desire for a table<> in the standard which acts like
: >a relational database table.  Map<> is close, but it forces breaking
: >the entity into key and attribute pairs.  Set<> keeps them together, but
: >has no update capabilities.  Neither of them was designed to be table<>.
: >
: >IMO, the set iterator issue is a halfbaked attempt to make a table from
: >set.  It will not hurt set, but it will also not produce table.
:
: This is an interesting way of looking at it.

It comes from the many questions over the last several years in clc++m
which reduced to getting a nice ordered collection from either set or
map.  The usual complaint about map was needing to duplicate the key
in the pair, while set did not allow modification unless non-key
members were made mutable which violated other uses.  I am being a
practitioner not a standard producer.

: Okay, granted. Of course I'm the opposite, in that I have always
: approached this (and all other issues since Nov97) from the
: standards-consistency point of view: "What does the standard say clearly
: and unambiguously? If anything is inconsistent, what is the least
: possible reasonable change to make the standard consistent?"

In case there is any doubt on the part of others, I understood where
you were coming from.  Your opinions were honest based on your facts.

: Does that go far enough?

Plenty and then some.  The hard copy supports your statements.  The
other views have not been formalized.

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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In his Nov.1999 column in C++ Report, Herb Sutter said
that set::iterator let user modify the data in the
set (and this is all right as long as the key part
is not modified...).

On the other hand, there is a defect report on this,
because the standard seems to say that set::iterator
is the same as the const_iterator (for example, there
is only find function, a const one, but it returns
an iterator, not a const_iterator). So as it is
the standard prohibits modification (that can be
achieved by other means, but not as directly).

The AFNOR, that presented the DR, proposed some
resolutions, but it is not clear (to me at least)
that the standard will be modified to fit Mr. Sutter
view.

Was that DR resolved? Does Mr. Sutter know something
I don't? Maybe he is trying to force the issue :-)

--
Michel Michaud (micm19@removethis.mail2.cstjean.qc.ca)
http://www3.sympatico.ca/michel.michaud

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Michel Michaud <micm19@gest-netware.cstjean.qc.ca> writes:

> In his Nov.1999 column in C++ Report, Herb Sutter said
> that set::iterator let user modify the data in the
> set (and this is all right as long as the key part
> is not modified...).
>
> On the other hand, there is a defect report on this,
> because the standard seems to say that set::iterator
> is the same as the const_iterator (for example, there
> is only find function, a const one, but it returns
> an iterator, not a const_iterator). So as it is
> the standard prohibits modification (that can be
> achieved by other means, but not as directly).
>
> The AFNOR, that presented the DR, proposed some
> resolutions, but it is not clear (to me at least)
> that the standard will be modified to fit Mr. Sutter
> view.
>
> Was that DR resolved? Does Mr. Sutter know something
> I don't? Maybe he is trying to force the issue :-)

I think Herb could reasonably say that the standard as written already
supports his view.  On the other hand, I think I could also reasonably
say that the standard already supports my view (which is that
set::iterator should have the same behavior as set::const_iterator,
and might even be the same type).  The standard at present is
defective.

Everyone agrees that the standard is buggy and needs to be fixed, but
I don't know what the fix will be.  There is a difference of opinion
about this within the committee, and it hasn't been resolved yet.
Everyone agrees that (with all issues, not just this) we should be
very cautious not to come up with a "fix" that makes things worse.
The last thing anyone wants is to have to fix our fixes.

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Matt Austern wrote :
> Michel Michaud <micm19@gest-netware.cstjean.qc.ca> writes:
>
> > In his Nov.1999 column in C++ Report, Herb Sutter said
> > that set::iterator let user modify the data in the
> > set (and this is all right as long as the key part
> > is not modified...).
> >
> > On the other hand, there is a defect report on this,
> > because the standard seems to say that set::iterator
> > is the same as the const_iterator (for example, there

> I think Herb could reasonably say that the standard as written already
> supports his view.  On the other hand, I think I could also reasonably
> say that the standard already supports my view (which is that
> set::iterator should have the same behavior as set::const_iterator,
> and might even be the same type).  The standard at present is
> defective.
>
> Everyone agrees that the standard is buggy and needs to be fixed,

So you agree with me, he was forcing the issue, and we should not do
as he proposed, in case the standard is fixed and disagree. This
is surprising from him and C++ Report! By the way, is there some
implementation that does permit modification thru iterators? (There
is one, because I fixed mine to test Herb's proposition, but
I mean "is there a commercial one"). Because that one would need
two find (and two of lower_bound, etc.) function, something clearly
different from the standard... (So Mr. Sutter point of view needs
modification to the standard).

--
Michel Michaud (micm19@removethis.mail2.cstjean.qc.ca)
http://www3.sympatico.ca/michel.michaud

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Michel Michaud <micm19@gest-netware.cstjean.qc.ca> writes:

> Matt Austern wrote :
> > Michel Michaud <micm19@gest-netware.cstjean.qc.ca> writes:
> >
> > > In his Nov.1999 column in C++ Report, Herb Sutter said
> > > that set::iterator let user modify the data in the
> > > set (and this is all right as long as the key part
> > > is not modified...).
> > >
> > > On the other hand, there is a defect report on this,
> > > because the standard seems to say that set::iterator
> > > is the same as the const_iterator (for example, there
>
> > I think Herb could reasonably say that the standard as written already
> > supports his view.  On the other hand, I think I could also reasonably
> > say that the standard already supports my view (which is that
> > set::iterator should have the same behavior as set::const_iterator,
> > and might even be the same type).  The standard at present is
> > defective.
> >
> > Everyone agrees that the standard is buggy and needs to be fixed,
>
> So you agree with me, he was forcing the issue, and we should not do
> as he proposed, in case the standard is fixed and disagree. This
> is surprising from him and C++ Report! By the way, is there some
> implementation that does permit modification thru iterators? (There
> is one, because I fixed mine to test Herb's proposition, but
> I mean "is there a commercial one"). Because that one would need
> two find (and two of lower_bound, etc.) function, something clearly
> different from the standard... (So Mr. Sutter point of view needs
> modification to the standard).

Bear in mind that either point of view requires the standard to be
modified!

I'm sure Herb can speak for himself, but it's quite possible that at
the time he wrote that article he just hadn't yet noticed that this
part of the standard was broken.  I didn't notice it either until
fairly recently.  The whole reason we're having this discussion is
that nobody on the committee noticed this bug before the standard was
released.

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Matt Austern wrote:
[...about whether or not set should permit direct modifications]
> Bear in mind that either point of view requires the standard to be
> modified!

OK then, maybe you could give me the most likely resolution. I
believe this could be useful for many. Because at this moment,
there is (almost) no real reason to use std::set. My opinion
is that if the iterators of set are indeed like const_iterators,
most people will prefer to use const_cast, instead of the
remove, modify, reinsert "algorithm". This is not what I expect
from something in standard C++.

On the other hand, maybe sets should not be considered general
containers. So only ADT set operation should be apply to it,
and values should then be clearly and logically non modifiable.
This is supported by the current standard that state that there
are only keys in sets, but not by most other descriptions.

Then however we would need another mecanism, say a new kind of
map, to build ordered group of values, where part of the values
is the key, clearly a classic case in CS for many years. Obviously
this can be done using map and some work, but everyone will
build their own variation... not a good thing, if that
means sets and maps are rarely use as is (and don't
forget standard containers are not built to be derive from).
Maybe what we need is standard adapter for that (like stack,
queue, etc.) that would use map...

> I'm sure Herb can speak for himself, but it's quite possible that at
> the time he wrote that article he just hadn't yet noticed that this
> part of the standard was broken.  I didn't notice it either until
> fairly recently.

That's possible but the DR report was submitted by AFNOR in
Oct. 1998... (not 1999).

--
Michel Michaud (micm19@removethis.mail2.cstjean.qc.ca)
http://www3.sympatico.ca/michel.michaud

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Michel Michaud <micm19@gest-netware.cstjean.qc.ca> writes:

| Matt Austern wrote:
| [...about whether or not set should permit direct modifications]
| > Bear in mind that either point of view requires the standard to be
| > modified!
|
| OK then, maybe you could give me the most likely resolution.

[...]

I think Matt was quite explicit: there is currently no consensus on
what could constitute the committee resolution.  There are at least
two reasonable resolutions.

--
Gabriel Dos Reis, dosreis@cmla.ens-cachan.fr

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Michel Michaud wrote:
> In his Nov.1999 column in C++ Report, Herb Sutter said
> that set::iterator let user modify the data in the
> set (and this is all right as long as the key part
> is not modified...).

Short answer: I believe this is true today for both pragmatic and
language-legalese reasons, and will almost certainly be true in the
future because it's compatible with all proposed resolutions that are
considered feasible. Of course, I've been wrong before and am open to
correction if I'm wrong now, but I don't think I'm wrong -- famous last
words.

Longer answer follows:

> On the other hand, there is a defect report on this,
[...]
> The AFNOR, that presented the DR, proposed some
> resolutions,

Just a couple of nits:

First, Library issue #103 shouldn't be called a "DR" (defect report) yet
because it's still listed as Open.

Second, the "proposed resolutions" section isn't necessarily written by
the submitter; it's usually written by the library working group.
Indeed, most issues we get are accompanied by no proposed resolution at
all (a source of annoyance, that!). In this case, I don't think AFNOR
proposed any resolutions, and I'm nearly certain that at least two
proposed resolutions came from within the committee because I think I
wrote Option C and I think Matt proposed Option A.

To recap, you are asking two distinct questions:

First:
> Sutter said that set::iterator let user modify the data in the set

Right, this is required by the standard because container::iterator is
required to be an "iterator type pointing to T."

Second:
> (and this is all right as long as the key part is not modified...).
[in such a way as to change its relative ordering in the container]

Right, and I think that's pragmatic advice that works using all
implementations. I do not know of any current or planned implementation
that does not work as I described in that article, and indeed I cannot
readily imagine one (of course, this does not mean that someone else
couldn't imagine one). Of course, it could be that I could have been
clearer in saying so. It could also be that I'm wrong, and I welcome
correction.

Note that though the article you're asking about appeared in Nov99, I
wrote it in April 1999. That's significant because I believe I wrote it
as a result of some discussion at the Dublin meeting that same month,
and I think we were discussing issue 103 at the time, so it would have
been fresh in my mind. Upon rereading issue 103, I think that I was the
one who wrote up the wording for Option C, after Andy pointed out the
filename example.

> but it is not clear (to me at least)
> that the standard will be modified to fit Mr. Sutter
> view.

Note that there are only three proposed resolutions; that Options A and
C are consistent with what I wrote in the Nov99 column; and that Option
B is both onerous and insufficient and therefore unlikely to be accepted
(see the Rationale). I therefore think that what I wrote is reasonable
in that it reflects the status quo and it is explicitly compatible with
both of the reasonable proposed resolutions -- i.e., what I wrote should
be true both if we decide to do "no change" and if we decide to make one
of the proposed changes.

I welcome correction if I am misunderstanding and thereby
misrepresenting the status quo or issue 103; perhaps Matt or someone
else in the LWG would like to dissect what I write in this article and
point out any flaws or misapprehensions under which I might be laboring.

> Maybe he is trying to force the issue :-)

I sometimes do that, but if so I come right out and say it. :-) For
example, see my May99 column ranting about what vector<bool> is versus
what I think it should be, or my Jul/Aug99 discussion about whether
vectors are contiguous and why I think it should be safe to assume that
they are.

Herb

---
Herb Sutter (mailto:hsutter@peerdirect.com)

CTO, PeerDirect Inc. (http://www.peerdirect.com)
Chair, ANSI H2 Ad-Hoc for SQL Part 12: SQL/Replication
  (Replication working group, ANSI SQL committee)
Editor-in-Chief, C++ Report (http://www.creport.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Thu, 10 Feb 2000 08:46:07 CST, Michel Michaud
<micm19@gest-netware.cstjean.qc.ca> wrote:
>believe this could be useful for many. Because at this moment,
>there is (almost) no real reason to use std::set.

Funny you should say that... you've now touched on the very topic of
Matt's article in the April 2000 issue of C++ Report (although for
different reasons).

Herb

---
Herb Sutter (mailto:hsutter@peerdirect.com)

CTO, PeerDirect Inc. (http://www.peerdirect.com)
Chair, ANSI H2 Ad-Hoc for SQL Part 12: SQL/Replication
  (Replication working group, ANSI SQL committee)
Editor-in-Chief, C++ Report (http://www.creport.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Wed, 9 Feb 2000 08:48:38 CST, Michel Michaud
<micm19@gest-netware.cstjean.qc.ca> wrote:
>So you agree with me, he was forcing the issue, and we should not do
>as he proposed, in case the standard is fixed and disagree. This
>is surprising from him and C++ Report!

Please don't jump to conclusions. See my other post in this thread of a
few minutes ago.

Cheers,

Herb

---
Herb Sutter (mailto:hsutter@peerdirect.com)

CTO, PeerDirect Inc. (http://www.peerdirect.com)
Chair, ANSI H2 Ad-Hoc for SQL Part 12: SQL/Replication
  (Replication working group, ANSI SQL committee)
Editor-in-Chief, C++ Report (http://www.creport.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Herb Sutter wrote:
>
> Michel Michaud wrote:
> > In his Nov.1999 column in C++ Report, Herb Sutter said
> > that set::iterator let user modify the data in the
> > set (and this is all right as long as the key part
> > is not modified...).
>
> Short answer: I believe this is true today for both pragmatic and
> language-legalese reasons, and will almost certainly be true in the
> future because it's compatible with all proposed resolutions that are
> considered feasible. Of course, I've been wrong before and am open to
> correction if I'm wrong now, but I don't think I'm wrong -- famous last
> words.

This is what you said in C++ Report. This is what I'd like. This
is what all other posters (here and in another newsgroup) aren't
so sure. You use "certainly be true", but Matt Austern and Gabriel
Dos Reis are sure it is still unclear what will be the final
resolution.

> Right, and I think that's pragmatic advice that works using all
> implementations. I do not know of any current or planned implementation
> that does not work as I described in that article, and indeed I cannot
> readily imagine one (of course, this does not mean that someone else

VC5 at least has iterator===const_iterator. And I believe this
was true in the original STL as well. So I probably don't
understand what you are saying...

> couldn't imagine one). Of course, it could be that I could have been
> clearer in saying so. It could also be that I'm wrong, and I welcome
> correction.

Well that's probably what I would have prefered: that in the
article you say that this is not exactly decided. You seemed pretty
sure there (and you still are), and I believe you :-) (probably
because this is the option I prefer...)

> > Maybe he is trying to force the issue :-)
>
> I sometimes do that, but if so I come right out and say it. :-) For
> example, see my May99 column ranting about what vector<bool> is versus
> what I think it should be, or my Jul/Aug99 discussion about whether
> vectors are contiguous and why I think it should be safe to assume that
> they are.

These article showed how well you knew what's going on. That is
what made your opinion on set::iterator so "real". See, now you
have a responsability to your reader, to say the truth, only
the truth, all the truth. Thank you god :-)

--
Michel Michaud (micm19@removethis.mail2.cstjean.qc.ca)
http://www3.sympatico.ca/michel.michaud

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Fri, 11 Feb 2000 04:10:29 CST, Michel Michaud
<micm19@gest-netware.cstjean.qc.ca> wrote:
>This is what you said in C++ Report. This is what I'd like. This
>is what all other posters (here and in another newsgroup) aren't
>so sure.

Then let me see if I can inject some clarity here. I'll lay it out point
by point, and hopefully when people knock me down I will be able to see
exactly what is being disagreed with. Fair enough? (Please read all five
questions and answers before you start to reply, because I believe I am
addressing all the points raised so far in this thread.)

The two main questions are:


Q1: Can you modify a set's contents through set::iterator?

A1: Yes. The container requirements specify that container::iterator be
an "iterator type pointing to (non-const) T."


Q2: If you do modify a key in a set (whether through an iterator or in
some other way), is it okay to change it in any old way as long as you
don't change its ordering relative to all other keys in the container?

A2: Yes. Today, this rule pragmatically will work on all implementations
I know of or can imagine (to shoot this belief down, you need only show
or describe a single counterexample). Tomorrow, this answer is
compatible with all feasible proposed resolutions currently being
considered for library issue 103 (to shoot this part down, you need only
describe why it's incompatible with Option A or Option C).


There are two secondary questions I have seen raised:


Q3: I have seen claims (in implementations' code and in print by
multiple reputable experts) that set::iterator is const/immutable, and
may be the same as const_iterator. Is that right?

A3: No, I can't see how either could be true. Maybe I just don't get it,
but it seems to me that both claims contradict the container
requirements: First, iterator must point to T (not const T). Second, I
can't see how iterator and const_iterator could ever be the same when
one is required to point to non-const T and the other to const T.


Q4: set::find(), set::lower_bound(), set::upper_bound(), and
set::equal_range() are all const yet all return set::iterator. Is that
right?

A4: No, and I think what we have here is a fossil.

First, why it's wrong: set::find() et al. don't meet the associative
container requirements, which require that find() et al. return iterator
for non-const set objects and const_iterator for const set objects. The
correct resolution is to specify set::find() et al. like map::find() et
al. -- pairs of functions, one const and returning const_iterator, the
other non-const and returning iterator. (This should be obviously
correct in its own right, but the next paragraph will attempt to give
additional historical justification by arguing that this may in fact
have been intended but just forgotten.)

Second, why it's a fossil: I think this artifact is a holdover from the
original HP STL, based on my reading of [GLASS 96] which was written way
back when only the HP STL (and two of its direct derivatives, Modena and
ObjectSpace) existed, and before the committee had started making
serious changes. [GLASS 96] documents set::find(), set::lower_bound(),
and set::upper_bound() as "iterator func(...) const" the way they still
exist in the standard today.

  - Interesting Note #1: Note that [GLASS 96] similarly documents
    map::find() as "iterator func(...) const", but this was changed
    during standardization to the current const/non-const pair of
    map::find() functions. This was clearly a deliberate change.

  - Interesting Note #2: Note that [GLASS 96] similarly documents
    set::begin() and set::end() as "iterator func() const", which
    as we know also changed during standardization so that today
    we have all those const/non-const function pairs for begin()
    and end().

All of this makes me suspect that the currently specified set::find() et
al. may be fossils or thinkos -- it looks like the committee just forgot
about find() et al. when they changed the associative container
requirements and so the functions got out of sync with the requirements.
That's my working hypothesis, anyway, without going back and looking at
the HP STL and interviewing LWG members who were there before my time.
If I'm wrong, I'm sure LWG oldtimers will respond and correct me.


Q5: map::iterator points to a pair<const Key, Value>. To be consistent
with set, shouldn't that be pair<Key, Value> to allow changes to keys?
After all, the only reason for const keys is to discourage users from
changing keys, and this method is insufficient because users can still
change keys (by const_cast, or by changing the key contents in other
ways such as through pointers to key data).

A5: Right, but we can live happily with what's there now. Personally, I
think the const key requirement is useless because it's insufficient for
its purpose, I think it would make sense to make map keys non-const, I
think that doing so would not break any user code that I know of, and I
alluded to this in my Oct99 C++ Report column... but map's having const
keys is not a defect, it doesn't affect map's adherence to associative
container requirements, and I haven't analyzed the impact thoroughly, so
I'm not going to push for it.


Finally, note that everything stated in this article about set/map
applies to multiset/multimap, too.

Does the above sound reasonable? What parts are wrong or misinformed or
misguided? Comments, corrections, and whacks upside the head are
welcome.

Herb


[GLASS 96] Glass and Schuchert. "The STL<Primer>" (Prentice-Hall, 1996).


P.S.: You wrote:

>> Right, and I think that's pragmatic advice that works using all
>> implementations. I do not know of any current or planned implementation
>> that does not work as I described in that article, and indeed I cannot
>> readily imagine one (of course, this does not mean that someone else
>
>VC5 at least has iterator===const_iterator. And I believe this
>was true in the original STL as well. So I probably don't
>understand what you are saying...

No, you took the above quote out of context... I was not talking about
whether iterator and const_iterator could be the same. I was talking
about the other part of the question, namely that if you DID change a
key (directly or indirectly) then as long as its relative order didn't
change you'd be okay in all respects. I still do not know of any current
or planned implementation that does not work that way, and I still
cannot readily imagine one.

---
Herb Sutter (mailto:hsutter@peerdirect.com)

CTO, PeerDirect Inc. (http://www.peerdirect.com)
Chair, ANSI H2 Ad-Hoc for SQL Part 12: SQL/Replication
  (Replication working group, ANSI SQL committee)
Editor-in-Chief, C++ Report (http://www.creport.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <38A2C90A.43287E66@mail2.cstjean.qc.ca>, Michel Michaud
<micm19@gest-netware.cstjean.qc.ca> writes
>These article showed how well you knew what's going on. That is
>what made your opinion on set::iterator so "real". See, now you
>have a responsability to your reader, to say the truth, only
>the truth, all the truth. Thank you god :-)

Under that constraint I do not think any of us could offer anything for
publication.  Being put on a pedestal is very confining:)


Francis Glassborow      Journal Editor, Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Herb Sutter wrote:
> On Fri, 11 Feb 2000 04:10:29 CST, Michel Michaud
> <micm19@gest-netware.cstjean.qc.ca> wrote:
> >This is what you said in C++ Report. This is what I'd like. This
> >is what all other posters (here and in another newsgroup) aren't
> >so sure.
>
> Then let me see if I can inject some clarity here. I'll lay it out point
> by point, and hopefully when people knock me down I will be able to see
> exactly what is being disagreed with. Fair enough? (Please read all five
> questions and answers before you start to reply, because I believe I am
> addressing all the points raised so far in this thread.)

I read all your points. If you've read my other posts, you'll understand
that I agree with your conclusion. BUT... if it was so simple, the
LWG would have a very simple job with item 103...

I am not going to give you a point by point analysis to the contrary
argument, but believe me I could and I am sure someone will.

So the problem is not what you or I think. It this what the LWG will
decide. You seem to be sure they will agree with you, but other (well
informed) posters are definitively not sure. I don't want to start
a Matt vs Herb battle, but surely you can understand that most
people will see both of you as being trustworthy. Matt only say
he doesn't know what will happen, although he stated clearly he is
in favor of non mutable -- well maybe he is pushing for that
because his book already say so, without nuances as you did in
your article :-) --. So I guess his advice is "don't do something
that possibly won't work when the LWG decides". Yours is "go
ahead, trust me I know what they'll decide".

I am not sure what is the safest route...

But thank you for making your arguments known. I think this
is what you should have put in C++ Report in the first place
but better late than never.

Now let's see other people arguments.

--
Michel Michaud (micm19@removethis.mail2.cstjean.qc.ca)
http://www3.sympatico.ca/michel.michaud

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Francis Glassborow wrote:
> In article <38A2C90A.43287E66@mail2.cstjean.qc.ca>, Michel Michaud
> <micm19@gest-netware.cstjean.qc.ca> writes
> >These article showed how well you knew what's going on. That is
> >what made your opinion on set::iterator so "real". See, now you
> >have a responsability to your reader, to say the truth, only
> >the truth, all the truth. Thank you god :-)
>
> Under that constraint I do not think any of us could offer anything for
> publication.  Being put on a pedestal is very confining:)

My emphasis would be on "all the truth". The problem is not so much
as making mistakes in books, mines have a fine errata :-), it is
when something you know is not certain, and you do as if it is.

Maybe Herb didn't know this particular issue was in the "issues
list", I have no problem with that, but now I would have to
verify everything he says to confirm it is not in that list...
I prefer to think he knew but decided not to talk about it...
(although I don't think it was a good decision).

By the way, I do think authors have a responsability to the
truth. If as an author, you say something wrong because you
did not check "carefully", expect to be criticize. But if there
is enough "good" in your book (or article), people should buy it
anyway. (For example, I just received "C & C++ Code Capsules" and,
although it may be a good book, I find it amazing it was reviewed
by well known people, proclaims 100% ISO C++ compatibility and
still uses "main()" without int throughout).

--
Michel Michaud (micm19@removethis.mail2.cstjean.qc.ca)
http://www3.sympatico.ca/michel.michaud

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Herb Sutter" <hsutter@peerdirect.com> wrote in message
news:kfp6aski1ccqj4v7kv8ec2r6qe4sf18m6e@4ax.com...
>
> Q2: If you do modify a key in a set (whether through an iterator or in
> some other way), is it okay to change it in any old way as long as you
> don't change its ordering relative to all other keys in the container?
>
> A2: Yes. Today, this rule pragmatically will work on all
implementations
> I know of or can imagine (to shoot this belief down, you need only
show
> or describe a single counterexample).

I can show you a counterexample:

    #include <set>
    struct Foo {
      int a;
      int b;
      bool operator<(const Foo& rhs) const { return a < rhs.a; }
    };
    int main() {
      std::set<Foo> bar;
      bar.insert(Foo());
      std::set<Foo>::iterator i(bar.begin());
      i->b = 1;
      return 0;
    }

GCC 2.95.2 rejects this ("assignment of member `Foo::b' in read-only
structure").

--
Ross Smith <ross.s@ihug.co.nz> The Internet Group, Auckland, New Zealand
========================================================================
    "Be careful about using the following code -- I've only proven
    that it works, I haven't tested it."           -- Donald Knuth


---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Sat, 12 Feb 2000 09:22:46 CST, "Ross Smith" <ross.s@ihug.co.nz>
wrote:

: "Herb Sutter" <hsutter@peerdirect.com> wrote in message
: news:kfp6aski1ccqj4v7kv8ec2r6qe4sf18m6e@4ax.com...
: >
: > Q2: If you do modify a key in a set (whether through an iterator or in
--------^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
: > some other way), is it okay to change it in any old way as long as you
: > don't change its ordering relative to all other keys in the container?
: >
: > A2: Yes. Today, this rule pragmatically will work on all
: implementations
: > I know of or can imagine (to shoot this belief down, you need only
: show
: > or describe a single counterexample).
:
: I can show you a counterexample:

You missed the point.  It says if you modify the key, nothing bad will
happen.  You did not modify the key.

With the gnu implementation, const_cast is needed to make modifications.

You have an example of an implementation which does not agree with Q/A1.

A counter example would be to modify the key without changing its
order, which you attempted, and show that the set selfdestructed.

The whole issue is whether set::iterator and set::const_iterator may
be the same type.  Herb says that set::iterator should be a mutable
iterator and if it were, there would be no harm doing the above.  You
can do those things today with const_cast.

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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <38A46123.B98E00F6@mail2.cstjean.qc.ca>, Michel Michaud
<micm19@gest-netware.cstjean.qc.ca> writes
>(For example, I just received "C & C++ Code Capsules" and,
>although it may be a good book, I find it amazing it was reviewed
>by well known people, proclaims 100% ISO C++ compatibility and
>still uses "main()" without int throughout).

If that was the worst fault you could find with it I would not wish to
clutter a review with such trivia.  Actually when I reviewed it I
strongly objected to its title (the C in the title is, IMO, completely
misleading)

Had the author used void main() you can be certain that I would have
been commenting in a review but...


Francis Glassborow      Journal Editor, Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation

---
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Sat, 12 Feb 2000 07:14:53 CST, Michel Michaud
<micm19@gest-netware.cstjean.qc.ca> wrote:
>But thank you for making your arguments known. I think this
>is what you should have put in C++ Report in the first place
>but better late than never.

You are, of course, welcome to your opinion, and I'm sorry to have
disappointed any reader. I know you keep saying the above, but I don't
yet accept it. Let me try to explain one last time.

To me, the above says: "But thank you for all those detailed reasons you
just gave to show why your belief is accurate and doesn't rely on
anything controversial/undecided. That's nice, Herb, but instead of
addressing any of them I'll just repeat vaguely that some people
disagree."

I don't think that's good enough -- WHY do they disagree, and with what?
I just showed in detail why I believe what I wrote is correct and
noncontroversial both under today's standard and under any viable
proposed change to the standard, and I want someone, anyone, to show me
which detail in what I wrote is wrong and why, and then I will be happy
to have learned and happy to immediately run, not walk, to write a mea
culpa in print. Would someone please do me the favor of showing me
specifically where I'm wrong so that I can spread the word more
correctly?

Herb

---
Herb Sutter (mailto:hsutter@peerdirect.com)

CTO, PeerDirect Inc. (http://www.peerdirect.com)
Chair, ANSI H2 Ad-Hoc for SQL Part 12: SQL/Replication
  (Replication working group, ANSI SQL committee)
Editor-in-Chief, C++ Report (http://www.creport.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Sat, 12 Feb 2000 04:44:40 CST, Herb Sutter <hsutter@peerdirect.com>
wrote:

: Then let me see if I can inject some clarity here. I'll lay it out point
: by point, and hopefully when people knock me down I will be able to see
: exactly what is being disagreed with. Fair enough? (Please read all five
: questions and answers before you start to reply, because I believe I am
: addressing all the points raised so far in this thread.)

Terse responses, logic at end.

: Q1: Can you modify a set's contents through set::iterator?
:
: A1: Yes. The container requirements specify that container::iterator be
: an "iterator type pointing to (non-const) T."

The container requirements are wrong.

: Q2: If you do modify a key in a set (whether through an iterator or in
: some other way), is it okay to change it in any old way as long as you
: don't change its ordering relative to all other keys in the container?
:
: A2: Yes. Today, this rule pragmatically will work on all implementations
: I know of or can imagine (to shoot this belief down, you need only show
: or describe a single counterexample). Tomorrow, this answer is
: compatible with all feasible proposed resolutions currently being
: considered for library issue 103 (to shoot this part down, you need only
: describe why it's incompatible with Option A or Option C).

So what?  Today it requires const_cast on many implementations.

: Q3: I have seen claims (in implementations' code and in print by
: multiple reputable experts) that set::iterator is const/immutable, and
: may be the same as const_iterator. Is that right?
:
: A3: No, I can't see how either could be true. Maybe I just don't get it,
: but it seems to me that both claims contradict the container
: requirements: First, iterator must point to T (not const T). Second, I
: can't see how iterator and const_iterator could ever be the same when
: one is required to point to non-const T and the other to const T.

The 1994 STL documentation (and I think CD1) contained:
   typedef iterator const_iterator;
and it was implemented.

: Q4: set::find(), set::lower_bound(), set::upper_bound(), and
: set::equal_range() are all const yet all return set::iterator. Is that
: right?
:
: A4: No, and I think what we have here is a fossil.

That agrees with the above.

: All of this makes me suspect that the currently specified set::find() et
: al. may be fossils or thinkos -- it looks like the committee just forgot
: about find() et al. when they changed the associative container
: requirements and so the functions got out of sync with the requirements.

Alternatively, the committee forgot that set was a set when changing the
requirements.  Keeping the contianers self consistent while factoring
out requirements is not an easy task.

: Does the above sound reasonable? What parts are wrong or misinformed or
: misguided? Comments, corrections, and whacks upside the head are
: welcome.

Sounds reasonable and only slightly irrational.

The original STL contained a set.  It has all of the operations needed
for a set plus the pleasant ability to iterate through the contents.
It contains no members for modifying elements. It makes perfect sense
for the iterator to be const.  It makes perfect sense for the insert
operation to do nothing when a match is found.  It would even make
sense for find to return T by value.

There is a great desire for a table<> in the standard which acts like
a relational database table.  Map<> is close, but it forces breaking
the entity into key and attribute pairs.  Set<> keeps them together, but
has no update capabilities.  Neither of them was designed to be table<>.

IMO, the set iterator issue is a halfbaked attempt to make a table from
set.  It will not hurt set, but it will also not produce table.  The
constness of set elements is a protection for Murphy consistent with
other protections to prevent surprise.  Since the standard does not
say that the element is const, we do not get undefined behavior by
casting away the constness of the iterator.  If we modify the key in
such a way as to destroy the order, we get undefined behavior and a
non-const iterator only makes it easier for Murphy.  Wow, it would
even be possible to sort the set on a different comparer. :)

Where is the change for insert(T) which will overwrite the matching
element?  Where is the change for insert(iter, T) which will allow
changing the key of the element found?  Where is the equivalent of
at() which will throw when changing a key will destroy the order?
Where is the change of name to something like
unsafe_table_usable_as_set?  Maybe there is no real use for set and
it should never have been in the standard.  Just change it to table
and get it right.  Oops, that would not be a defect.

I think those who find your arguements a problem are thinking about
the set not some patch to make the standard consistent.  I've ignored
the real need for the standard to say something which is consistent.
It doesn't need to please anyone and whatever is done will not please
everyone.

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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On Sat, 12 Feb 2000 09:22:46 CST, "Ross Smith" <ross.s@ihug.co.nz>
wrote:
>"Herb Sutter" <hsutter@peerdirect.com> wrote in message
>news:kfp6aski1ccqj4v7kv8ec2r6qe4sf18m6e@4ax.com...
>>
>> Q2: If you do modify a key in a set (whether through an iterator or in
>> some other way), is it okay to change it in any old way as long as you
>> don't change its ordering relative to all other keys in the container?
>>
>> A2: Yes. Today, this rule pragmatically will work on all implementations
>> I know of or can imagine (to shoot this belief down, you need only show
>> or describe a single counterexample).
>
>I can show you a counterexample:

No, no, no. I understand what you mean, but this is just an example of
Q3; it is not a counterexample to Q2. See below.

>    #include <set>
>    struct Foo {
>      int a;
>      int b;
>      bool operator<(const Foo& rhs) const { return a < rhs.a; }
>    };
>    int main() {
>      std::set<Foo> bar;
>      bar.insert(Foo());
>      std::set<Foo>::iterator i(bar.begin());
>      i->b = 1;
>      return 0;
>    }
>
>GCC 2.95.2 rejects this ("assignment of member `Foo::b' in read-only
>structure").

I know that there are implementations that use immutable set::iterators;
so does mine (MSVC5.x). I said so in question Q3 of the article you
quoted, and in both Q1 and Q3 argued why I believe those implementations
are clearly nonconforming.

But Q2, which you quote above, says that "IF you do modify a key"
(either through a set::iterator if yours allows that, or otherwise such
as in the example below) THEN as long as you don't change its ordering
everything will work correctly. I still cannot imagine an implementation
that would violate this assumption.

I claim this regardless whether the implementation has an immutable
set::iterator or not. Consider:

    #include <set>
    #include <string>

    struct Foo {
      std::string* name_;
      Foo( std::string* name ) : name_( name ) { }
      bool operator<(const Foo& rhs) const
                               { return *name_ < *rhs.name_; }
    };

    int main() {
      std::set<Foo> bar;
      std::string aaa( "AAA" );
      std::string ppp( "PPP" );
      bar.insert(Foo( &aaa ));
      bar.insert(Foo( &ppp ));

      aaa = "HHH";
      // *** MY CLAIM IN A2: I cannot imagine an implementation where
      //     it is not true that all further use of bar is still valid
      //     (because "HHH" still compares as less than "PPP"), even
      //     though a key indeed most certainly has been modified. ***

      return 0;
    }

Herb

---
Herb Sutter (mailto:hsutter@peerdirect.com)

CTO, PeerDirect Inc. (http://www.peerdirect.com)
Chair, ANSI H2 Ad-Hoc for SQL Part 12: SQL/Replication
  (Replication working group, ANSI SQL committee)
Editor-in-Chief, C++ Report (http://www.creport.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]

For the group's information, Michel and I have also been corresponding
privately, and here is a copy of an email I sent Michel today
summarizing what I perceive to be the end result (so far). Forwarded
with Michel's permission.


-----8<---------------

OK, now I finally believe I understand the status quo (both standardese
and compilers) enough give a solid reply! Thanks for making me look at
this in more detail. Here are my responses to your questions based on my
current understanding:

>In your column on set and map in C++ Report
>(vol.11 no 9), you seem very sure that
>set::iterator are not supposed to be the same
>as a const_iterator. That std::iterator should
>allow you to modify the value in the set.

The standard's container requirements are clear that this should be so.
What I didn't know (and isn't yet reflected in any active issues list)
is that some people think the container requirements are wrong -- this
is a major thing, because the container requirements are an
architectural issue.

>Although I agree this is probably what it should
>be, you're certainly aware the standard is not
>so clear about it. There is a defect report on
>this, but to my knowledge, it was not resolved
>at the time you wrote the article. Is it now?

I think the correct characterization is: The current standard is clear,
and the open issue (#103) has two reasonable proposed resolutions both
of which would add text to bless this explicitly -- but I now know there
are people who think the standard should be changed in this respect and
who I think will be writing up new related issues with different and
more sweeping proposed resolutions. Because those issues don't yet
exist, will take time to discuss and decide, and probably won't be in
time to get into the Technical Corrigendum planned for October of this
year, I would say that the chances are very high that there will be
either no change or one of the two existing reasonable proposed
resolutions will be adopted in that TC. If there is this kind of
uncertainty, though, I'd even say it's highly probable that the status
quo will remain unchanged in the TC, which would mean it would stay
unchanged officially for at least three more years.

>(In oct 99, Matt Austern wrote this in a newsgroup:
>>[...] Existing implementations differ.)

This is indeed a key point (pun not intended).

>I am a teacher and I am teaching this right now. My choice at
>the moment would be to const_cast the iterator (because on
>my compiler it is a const_iterator) or use a remove/add when
>I need to modify the value (and I don't want a map). I
>don't like either solution in general. If you can assure
>me, it is now a valid thing to modify using the iterator
>(I know I should not modify what constitute the key part),
>I will do as I always do : modify the header files to get
>a more conforming one!

Ah, teaching is a delicate thing! I agree it requires care (and a
magazine article is really the same thing). I have reread my Oct99
article and stand by what it says -- I think it is good advice, that I
would give when teaching -- except that now I am aware that some popular
implementions have set::iterator pointing to const T and I feel the need
to amplify that this is the case. In harmony with that, if it were me, I
would now teach the following:

- Set isn't as useful as most people think, so often you should use a
different data structure anyway. (See Matt's column in the April 2000
issue.)

If you do use set:

- In practice, don't get into the habit of relying on the ability to
modify set entries using iterators. Today, some implementations don't
allow it. There are smart people who think it's wrong that the standard
allows this and who may create proposals to change the standard to
disallow this.

- If you need to change a value in set, erase the old one and reinsert
the new one. (Maybe it's ugly, but oh well.)

- Remember that it's possible to change keys in sets indirectly, without
using iterators or const_cast. For example, you can do it if any data
that affects comparison is available indirectly, such as if the key is a
disk filename and the comparison is of file contents, or if the key has
a string member that can be modified externally, etc. FOR INTRO
STUDENTS: Don't do this. FOR MORE ADVANCED STUDENTS: If you do this, do
not change the key's ordering relative to other keys in the container.

I need to add a note about this pragmatic change in a future column.

>Thank you for your time. Continue the good work and
>have a nice day.

Thanks for the kind words, and for raising the question! Best wishes,

Herb

---
Herb Sutter (mailto:hsutter@peerdirect.com)

CTO, PeerDirect Inc. (http://www.peerdirect.com)
Chair, ANSI H2 Ad-Hoc for SQL Part 12: SQL/Replication
  (Replication working group, ANSI SQL committee)
Editor-in-Chief, C++ Report (http://www.creport.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://reality.sgi.com/austern_mti/std-c++/faq.html              ]