gdr@cs.tamu.edu (Gabriel Dos Reis) writes:

> pjp@dinkumware.com ("P.J. Plauger") writes:
>
> [...]
>
> | I agree that the brush is broad, and that clever users can operate
> | the machinery with the safety panels removed. But it's *so* easy to
> | sidestep const -- with type casts and mutable members -- that I hardly
> | see where an excess of constness gets in the way of the clever and/or
> | daring programmer.
>
> Mutating elements in a set has nothing to do with being clever.  And
> no, spreading casts, made necessary only by a very fanatical idea of
> const, is not something my book describes as "so easy".

Surely the casts can be nicely localized to a single function?  I
don't think Bill's view of const is fanatical; it seems quite
conservative to me.  And don't forget he also mentioned the use of
mutable.  Every time we discuss this I find myself having forgotten
that argument and it always seems to convince me.  We have a difficult
choice here: either leave the door wide open for the data structure's
invariants to be broken, or make it slightly inconvenient and ugly to
modify them when you know what you're doing.  There's no perfect
answer and I'm not inclined to label any position in the spectrum of
approaches we've discussed as radical.


--
Dave Abrahams
Boost Consulting
www.boost-consulting.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

dave@boost-consulting.com (David Abrahams) writes:

| gdr@cs.tamu.edu (Gabriel Dos Reis) writes:
|
| > pjp@dinkumware.com ("P.J. Plauger") writes:
| >
| > [...]
| >
| > | I agree that the brush is broad, and that clever users can operate
| > | the machinery with the safety panels removed. But it's *so* easy to
| > | sidestep const -- with type casts and mutable members -- that I hardly
| > | see where an excess of constness gets in the way of the clever and/or
| > | daring programmer.
| >
| > Mutating elements in a set has nothing to do with being clever.  And
| > no, spreading casts, made necessary only by a very fanatical idea of
| > const, is not something my book describes as "so easy".
|
| Surely the casts can be nicely localized to a single function?  I

Write out the details and you'll see how that localization does
actually spread through every use.  It is no localization.

| don't think Bill's view of const is fanatical; it seems quite
| conservative to me.  And don't forget he also mentioned the use of
| mutable.

Yes, that in my opinion, is a perverted use of mutable; just of
because that immutability of the iterator.  To see why, just try to
write out how you would use that mutable.  If the datatype (say
std::pair<T,U>) is not defined with mutable hardwired in the declaration,
his suggestion is no relevance.  And in case one gets that foresight,
it implies that on other occasion whether an object of type T is
declared const -- because it really is from a logical point of -- the
type system can no longer enforce that.  It is a relic of that old,
Simula, way of writing container: one can put an object in a container
only is it is derived from a universal base class Link.  Largely very
un-STL -- impossible to combine separately developed abstractions.

|  Every time we discuss this I find myself having forgotten
| that argument and it always seems to convince me.  We have a difficult
| choice here: either leave the door wide open for the data structure's
| invariants to be broken, or make it slightly inconvenient and ugly to

when in doubt, trust the programmer.

| modify them when you know what you're doing.  There's no perfect
| answer and I'm not inclined to label any position in the spectrum of
| approaches we've discussed as radical.

It has been proposed to make std::set<const T> work.  It does not
require spreading casts over the places.  And in a sense, it says it
all.

--
                                                        Gabriel Dos Reis
                                                         gdr@cs.tamu.edu
 Texas A&M University -- Department of Computer Science
 301, Bright Building -- College Station, TX 77843-3112

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

David Abrahams wrote:
> gdr@cs.tamu.edu (Gabriel Dos Reis) writes:

> > pjp@dinkumware.com ("P.J. Plauger") writes:

> > [...]

> > | I agree that the brush is broad, and that clever users can
> > | operate the machinery with the safety panels removed. But
> > | it's *so* easy to sidestep const -- with type casts and
> > | mutable members -- that I hardly see where an excess of
> > | constness gets in the way of the clever and/or daring
> > | programmer.

> > Mutating elements in a set has nothing to do with being
> > clever. And no, spreading casts, made necessary only by a
> > very fanatical idea of const, is not something my book
> > describes as "so easy".

> Surely the casts can be nicely localized to a single function?
> I don't think Bill's view of const is fanatical; it seems
> quite conservative to me. And don't forget he also mentioned
> the use of mutable. Every time we discuss this I find myself
> having forgotten that argument and it always seems to convince
> me. We have a difficult choice here: either leave the door
> wide open for the data structure's invariants to be broken, or
> make it slightly inconvenient and ugly to modify them when you
> know what you're doing. There's no perfect answer and I'm not
> inclined to label any position in the spectrum of approaches
> we've discussed as radical.

I agree with Plauger's position: we have a safe default, and the
means are there to do whatever you really want if the default
isn't what you want.  But I don't buy the mutable argument.
It's really only valid if the object is designed expressedly for
use in this set; in more general cases, you don't want to go
around declaring everything mutable just because the object
might end up in a set where that particular field is not part of
the key.  (In my last application, one type of object ended up
in six different sets at different times.  With a different key,
depending on the set.)

--
James Kanze           GABI Software         http://www.gabi-soft.fr
Conseils en informatique orient   e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

kanze@gabi-soft.fr writes:

> David Abrahams wrote:
>
>> Surely the casts can be nicely localized to a single function?
>> I don't think Bill's view of const is fanatical; it seems
>> quite conservative to me. And don't forget he also mentioned
>> the use of mutable. Every time we discuss this I find myself
>> having forgotten that argument and it always seems to convince
>> me.
...
>
> I agree with Plauger's position: we have a safe default, and the
> means are there to do whatever you really want if the default
> isn't what you want.  But I don't buy the mutable argument.

Sorry, when I said "forgotten that argument" I was referring to the
possibility of const_cast, not mutable.  I realize it isn't clear from
my posting.

--
Dave Abrahams
Boost Consulting
www.boost-consulting.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

kanze@gabi-soft.fr writes:

| David Abrahams wrote:
| > gdr@cs.tamu.edu (Gabriel Dos Reis) writes:
|
| > > pjp@dinkumware.com ("P.J. Plauger") writes:
|
| > > [...]
|
| > > | I agree that the brush is broad, and that clever users can
| > > | operate the machinery with the safety panels removed. But
| > > | it's *so* easy to sidestep const -- with type casts and
| > > | mutable members -- that I hardly see where an excess of
| > > | constness gets in the way of the clever and/or daring
| > > | programmer.
|
| > > Mutating elements in a set has nothing to do with being
| > > clever. And no, spreading casts, made necessary only by a
| > > very fanatical idea of const, is not something my book
| > > describes as "so easy".
|
| > Surely the casts can be nicely localized to a single function?
| > I don't think Bill's view of const is fanatical; it seems
| > quite conservative to me. And don't forget he also mentioned
| > the use of mutable. Every time we discuss this I find myself
| > having forgotten that argument and it always seems to convince
| > me. We have a difficult choice here: either leave the door
| > wide open for the data structure's invariants to be broken, or
| > make it slightly inconvenient and ugly to modify them when you
| > know what you're doing. There's no perfect answer and I'm not
| > inclined to label any position in the spectrum of approaches
| > we've discussed as radical.
|
| I agree with Plauger's position: we have a safe default,

It is not a default.  It is something one cannot count
on changing.

|                                                          and the
| means are there to do whatever you really want if the default
| isn't what you want.

And what are those means?

  (1) "mutable" is a non-starter.

  (2) "const_cast" a non-starter too: Nothing in the standard
       guarantees modifying the object designed by the iterator,
       after const_cast<> is defined behaviour.  In fact, I cannot see
       any wording in the standard that prevent an implementation from
       storing the data as const objects.


--
                                                        Gabriel Dos Reis
                                                         gdr@cs.tamu.edu
 Texas A&M University -- Department of Computer Science
 301, Bright Building -- College Station, TX 77843-3112

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Gabriel Dos Reis" <gdr@cs.tamu.edu> wrote in message
news:m3zmzapj1l.fsf@merlin.cs.tamu.edu...
| nesotto@cs.auc.dk ("Thorsten Ottosen") writes:
|
|| "Gabriel Dos Reis" <gdr@cs.tamu.edu> wrote in message
|| news:m3651zqp5q.fsf@merlin.cs.tamu.edu...
|| | pjp@dinkumware.com ("P.J. Plauger") writes:
|| |
|| |
|| | [...]
|| |
|| || I forget how we (WG21 library committee) resolved the DR, but I'm pretty
|| || sure the consensus now is that set elements should not be alterable
|| || through set iterators. Since we've offered both const and non-const set
|| || iterators over the years, we now provide a compile-time choice of
|| || behaviors.
|| ||
|| || FWIW, I have always opposed allowing set elements to change, but we
|| || (Dinkumware) have tried to do what we think the C++ Standard says over
|| || the years, even when we disagree.
||
|| maybe we should allow std::set<const T> to work?
|
| for what?

so those who don't want mutability can say and enforce that.

|| | relative ordering are preserved*.  In most practical situations where
|| | I need a "set", std::set proves itself to be perfectly useless. I just
|| | end up rollong my own.
|| |
|| | You mentioned an example very close to std::map; in situations where I
|| | had to roll my own set, most of them were like that. But using std::map,
|| | ended up duplicating the key -- which can be very large (e.g. a string).
||
|| Can you outline the major differences besides mutability of such a set?
|
| mutability is already important.
|
| The other difference is that the comparator is not explicit hard coded
| into the type, but is used as argument to find(), insert(), etc.
| The values for those parameters are OK, *as far as they preserve the
| relative ordering*.

there is something I don't get. Do you sort the set before each
call to find()?

-Thorsten


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Boost IndexedSet is just the old name for Boost Multi-index.

This is for all considerations in this discussion equivalent to a set,
the only difference is that it allows more indices and some syntactic
sugar for the necessary const_cast.

Note that Multi-index have lots of other nice features but this isn't
one of them. To be honest I have wondered why they went down into this
trap.

For this discussion I think stl_tree fits what is needed much better.
Why wasn't that included in the standard?

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

nesotto@cs.auc.dk ("Thorsten Ottosen") writes:

[...]

| | The other difference is that the comparator is not explicit hard coded
| | into the type, but is used as argument to find(), insert(), etc.
| | The values for those parameters are OK, *as far as they preserve the
| | relative ordering*.
|
| there is something I don't get. Do you sort the set before each
| call to find()?

No; I don't have to.  std::set internally sorts its elements.

--
                                                        Gabriel Dos Reis
                                                         gdr@cs.tamu.edu
 Texas A&M University -- Department of Computer Science
 301, Bright Building -- College Station, TX 77843-3112

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

pjp@dinkumware.com ("P.J. Plauger") writes:

| "Gabriel Dos Reis" <gdr@cs.tamu.edu> wrote in message
| news:m3651zqp5q.fsf@merlin.cs.tamu.edu...
|
| > | FWIW, I have always opposed allowing set elements to change, but we
| > | (Dinkumware) have tried to do what we think the C++ Standard says over
| > | the years, even when we disagree.
| >
| > I've always found that restriction about alteration of set is rather
| > artificial.  I can see the arguments; but they look more theoretical
| > than pratical to me.  If a user modifies the set in a way that the
| > ordering is broken, then it is broken. Period.  The corollary is that,
| > the standard library should have allowed alteration *as long as the
| > relative ordering are preserved*.  In most practical situations where
| > I need a "set", std::set proves itself to be perfectly useless. I just
| > end up rollong my own.
|
| This is a reductio ad absurdum argument against *every* use of
| const, IMO.

Why?

| Since you can always defeat a const qualifier, why
| bother to use it at all?

That misses the entire point, and that is unfortunate.

| But we do in fact use const, and we use
| it a lot, because it keeps us from making the worst kinds of
| mistakes.

when that is sensible and useful.

The issue is not whether const qualifier, in abstract, can be useful
or not.  Of course it can.

The issue is whether the insistance of making the std::set<T>::iterator
immutable make std::set that useful in practice.  I can see how useful
it is in purely theoretical arguments; in pratice I can see the large
extent of its uselessness.

std::set<T> is over-abstracted.  For purely abstract reasons.

| You have to go out of your way to defeat const and,
| perhaps, destroy the internal integrity of a complex structure
| (such as a set). That, to me, is the compelling argument for
| disallowing easy alteration of a set key.

By that argument you should also disallow std::vector from returning a
reference to its internal element because you can easily invalidate
them by simple operations, e.g. push_back().

--
                                                        Gabriel Dos Reis
                                                         gdr@cs.tamu.edu
 Texas A&M University -- Department of Computer Science
 301, Bright Building -- College Station, TX 77843-3112

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

magfr@comp.std.cpp.magfr.user.lysator.liu.se (Magnus Fromreide) writes:

| Boost IndexedSet is just the old name for Boost Multi-index.
|
| This is for all considerations in this discussion equivalent to a set,
| the only difference is that it allows more indices and some syntactic
| sugar for the necessary const_cast.
|
| Note that Multi-index have lots of other nice features but this isn't
| one of them. To be honest I have wondered why they went down into this
| trap.
|
| For this discussion I think stl_tree fits what is needed much better.

Oh yes, std::set and variants are just *adaptors* over a tree-node; they
could be parametrized in various ways.  See for example, the work of
Matt Austern et al.

--
                                                        Gabriel Dos Reis
                                                         gdr@cs.tamu.edu
 Texas A&M University -- Department of Computer Science
 301, Bright Building -- College Station, TX 77843-3112

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Gabriel Dos Reis" <gdr@cs.tamu.edu> wrote in message
news:m3acr9p95w.fsf@merlin.cs.tamu.edu...
| nesotto@cs.auc.dk ("Thorsten Ottosen") writes:
|
| [...]
|
|| | The other difference is that the comparator is not explicit hard coded
|| | into the type, but is used as argument to find(), insert(), etc.
|| | The values for those parameters are OK, *as far as they preserve the
|| | relative ordering*.
||
|| there is something I don't get. Do you sort the set before each
|| call to find()?
|
| No; I don't have to.  std::set internally sorts its elements.

yes, std::set does. But if you are going to have a set sorted by <
and then provide find with a > predicate, then I don't get it.

What I'm I missing? What is the advantage of having
find take a predicate if it can only accept one predicate?

-Thorsten


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

nesotto@cs.auc.dk ("Thorsten Ottosen") writes:

| "Gabriel Dos Reis" <gdr@cs.tamu.edu> wrote in message
| news:m3acr9p95w.fsf@merlin.cs.tamu.edu...
| | nesotto@cs.auc.dk ("Thorsten Ottosen") writes:
| |
| | [...]
| |
| || | The other difference is that the comparator is not explicit hard coded
| || | into the type, but is used as argument to find(), insert(), etc.
| || | The values for those parameters are OK, *as far as they preserve the
| || | relative ordering*.
| ||
| || there is something I don't get. Do you sort the set before each
| || call to find()?
| |
| | No; I don't have to.  std::set internally sorts its elements.
|
| yes, std::set does. But if you are going to have a set sorted by <
| and then provide find with a > predicate, then I don't get it.

I don't understand what you mean.

| What I'm I missing?

I don't know.  I just don't understand what you're saying.

--
                                                        Gabriel Dos Reis
                                                         gdr@cs.tamu.edu
 Texas A&M University -- Department of Computer Science
 301, Bright Building -- College Station, TX 77843-3112

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Magnus Fromreide wrote:
> Boost IndexedSet is just the old name for Boost Multi-index.
> This is for all considerations in this discussion equivalent to a
set,
> the only difference is that it allows more indices and some syntactic
> sugar for the necessary const_cast.

Boost.MultiIndex provides an alternative to the use of
const_cast for modifying an element, but I wouldn't call
it syntactic sugar, since the methods provided do actually
perform internal resorting if needed:

Basically, you can modify an element by one of two methods
(apart from resorting to const_cast, of course):

1. The memfun replace() accepts a new value for a
given element and does the replacement if allowed by
the uniqueness constraints of the container, in any case
preserving the iterator and reference validity of the element:

some_set s; // a set-like container defined with Boost.MultiIndex
some_set::iterator it=...
some_set::value_type new_value;
s.replace(it,new_value); // returns true if replacing took place

2. The memfun modify() accepts a user-provided functor
taking a reference to the to-be-modified element: after the
functor executes, any required resorting is internally
performed. If the element violates uniqueness constraints
then it is erased, otherwise iterator and reference
validity is preserved.

struct modifying_functor
{
bool operator()(some_set::value_type&)
{
// modify the element
}
};

some_set s;
some_set::iterator it=...
s.modify(it,modifying_functor()); // if it returns false,
// then the element pointed to by it is erased.

replace() and modify() do provide different guarantees
(basically, replace() keeps the original value on
unsunccessful modification) at the expense of different
run-time overheads (modify() is cheaper.)
So, I don't think modify() and replace() can be regarded
as syntactic sugar to const_casting away an element,
as these operations *cannot* be implemented externally
with a std::set: whether std::set should provide
something like replace() and/or modify(), that's
maybe a good question for the standard folks.

Best,
Joaqu   n M L   pez Mu   oz
Telef   nica, Investigaci   n y Desarrollo


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Gabriel Dos Reis" <gdr@cs.tamu.edu> wrote in message
news:m3vf9xnfff.fsf@merlin.cs.tamu.edu...
| nesotto@cs.auc.dk ("Thorsten Ottosen") writes:
|
|| "Gabriel Dos Reis" <gdr@cs.tamu.edu> wrote in message
|| news:m3acr9p95w.fsf@merlin.cs.tamu.edu...
|| | nesotto@cs.auc.dk ("Thorsten Ottosen") writes:
|| |
|| | [...]
|| |
|| || | The other difference is that the comparator is not explicit hard coded
|| || | into the type, but is used as argument to find(), insert(), etc.
                                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|| || | The values for those parameters are OK, *as far as they preserve the
|| || | relative ordering*.

maybe I misunderstood what you mean by "those parameters". Can you give
an example?

|| || there is something I don't get. Do you sort the set before each
|| || call to find()?
|| |
|| | No; I don't have to.  std::set internally sorts its elements.
||
|| yes, std::set does. But if you are going to have a set sorted by <
|| and then provide find with a > predicate, then I don't get it.
|
| I don't understand what you mean.
|
|| What I'm I missing?
|
| I don't know.  I just don't understand what you're saying.

Communication is hard :-)

Ok, you said that your hand-roled set had a find() function somthing like this

template< class T, class BinPred >
T& set<T>::find( const T&, BinPred );
...
set<int> my_set;
..
my_set.find( 4, std::less_than<int>() );
..
my_set.find( 5, std::greater_than<int>() );

If you're not going to use more than one predicate for the search,
then why are you not just hardcoding the comparator in the type?

If you use more than one predicate, don't you have to resort the set
before searching?

Hope it helps

-Thorsten




---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

nesotto@cs.auc.dk ("Thorsten Ottosen") writes:

| "Gabriel Dos Reis" <gdr@cs.tamu.edu> wrote in message
| news:m3vf9xnfff.fsf@merlin.cs.tamu.edu...
| | nesotto@cs.auc.dk ("Thorsten Ottosen") writes:
| |
| || "Gabriel Dos Reis" <gdr@cs.tamu.edu> wrote in message
| || news:m3acr9p95w.fsf@merlin.cs.tamu.edu...
| || | nesotto@cs.auc.dk ("Thorsten Ottosen") writes:
| || |
| || | [...]
| || |
| || || | The other difference is that the comparator is not explicit hard coded
| || || | into the type, but is used as argument to find(), insert(), etc.
|                                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
| || || | The values for those parameters are OK, *as far as they preserve the
| || || | relative ordering*.
|
| maybe I misunderstood what you mean by "those parameters". Can you give
| an example?
|
| || || there is something I don't get. Do you sort the set before each
| || || call to find()?
| || |
| || | No; I don't have to.  std::set internally sorts its elements.
| ||
| || yes, std::set does. But if you are going to have a set sorted by <
| || and then provide find with a > predicate, then I don't get it.
| |
| | I don't understand what you mean.
| |
| || What I'm I missing?
| |
| | I don't know.  I just don't understand what you're saying.
|
| Communication is hard :-)
|
| Ok, you said that your hand-roled set had a find() function somthing like this
|
| template< class T, class BinPred >
| T& set<T>::find( const T&, BinPred );
| ...

yes.

| set<int> my_set;
| ..
| my_set.find( 4, std::less_than<int>() );
| ..
| my_set.find( 5, std::greater_than<int>() );

I also said with emphasis:

  *as far as they preserve the relative ordering*

I don't see the above two as satisfying the assumption.

You can freely use ComparatorB in place of ComparatorA as far as one
has the following condition:

   ComparatorA(x, y) == ComparatorB(x, y)

Or, even weaken the condition to

   ComparatorA(x, y) == v implies ComparatorB(x, y) == v

(e.g. ComparatorB is a refinement of ComparatorA).  So one can
insert() with ComparatorA() et find() with ComparatorB().

| If you're not going to use more than one predicate for the search,
| then why are you not just hardcoding the comparator in the type?

I just said the contrary.

| If you use more than one predicate, don't you have to resort the set
| before searching?

No, I don't have too.  See above.  The essence of std::set is not to
sort, but to store elements uniquely.

--
                                                        Gabriel Dos Reis
                                                         gdr@cs.tamu.edu
 Texas A&M University -- Department of Computer Science
 301, Bright Building -- College Station, TX 77843-3112

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

pjp@dinkumware.com ("P.J. Plauger") writes:

> "Gabriel Dos Reis" <gdr@cs.tamu.edu> wrote in message
> news:m3651zqp5q.fsf@merlin.cs.tamu.edu...
>
>> | FWIW, I have always opposed allowing set elements to change, but we
>> | (Dinkumware) have tried to do what we think the C++ Standard says over
>> | the years, even when we disagree.
>>
>> I've always found that restriction about alteration of set is rather
>> artificial.  I can see the arguments; but they look more theoretical
>> than pratical to me.  If a user modifies the set in a way that the
>> ordering is broken, then it is broken. Period.  The corollary is that,
>> the standard library should have allowed alteration *as long as the
>> relative ordering are preserved*.  In most practical situations where
>> I need a "set", std::set proves itself to be perfectly useless. I just
>> end up rollong my own.
>
> This is a reductio ad absurdum argument against *every* use of
> const, IMO. Since you can always defeat a const qualifier, why
> bother to use it at all? But we do in fact use const, and we use
> it a lot, because it keeps us from making the worst kinds of
> mistakes. You have to go out of your way to defeat const and,
> perhaps, destroy the internal integrity of a complex structure
> (such as a set). That, to me, is the compelling argument for
> disallowing easy alteration of a set key.

Do you really find const very useful in maintaining invariants?
If so, could you give some non-set examples?

In my code, const is almost invariably used to distinguish those
operations that are meant to modify the state of a structure from
those that aren't, but there's generally no way to leverage it to
preserve invariants.  Usually, that job is left entirely up to
encapsulation, by which I mean access control (the use of
public/private/protected).

The difference with set is that there's a large class of
integrity-preserving modifications that can only be known by the
person who supplied the comparison function and/or the element type,
which is to say the user.  const paints with a very wide brush in this
case, and I can understand the argument that it's too wide.  I guess
I've wished for set element mutability maybe 30% of the time I use it.

It might be interesting to explore making set elements const when some
appropriate compile-time predicate is satisfied by the element and/or
comparison function, but that gets complicated.  I'm starting to think
an additional template parameter that makes a set mutable is a better
approach.

--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"David Abrahams" <dave@boost-consulting.com> wrote in message
news:uu0pfrs02.fsf@boost-consulting.com...

>> This is a reductio ad absurdum argument against *every* use of
>> const, IMO. Since you can always defeat a const qualifier, why
>> bother to use it at all? But we do in fact use const, and we use
>> it a lot, because it keeps us from making the worst kinds of
>> mistakes. You have to go out of your way to defeat const and,
>> perhaps, destroy the internal integrity of a complex structure
>> (such as a set). That, to me, is the compelling argument for
>> disallowing easy alteration of a set key.
>
> Do you really find const very useful in maintaining invariants?

Yes.

> If so, could you give some non-set examples?

How 'bout priority_queue::top(), for one? Any time you want to make
visible elements whose value must preserve some invariant, you'd
better make 'em const.

> In my code, const is almost invariably used to distinguish those
> operations that are meant to modify the state of a structure from
> those that aren't, but there's generally no way to leverage it to
> preserve invariants.  Usually, that job is left entirely up to
> encapsulation, by which I mean access control (the use of
> public/private/protected).

That works too, and so do accessors. But there's still good
reasons to provide const references sometimes too.

> The difference with set is that there's a large class of
> integrity-preserving modifications that can only be known by the
> person who supplied the comparison function and/or the element type,
> which is to say the user.  const paints with a very wide brush in this
> case, and I can understand the argument that it's too wide.  I guess
> I've wished for set element mutability maybe 30% of the time I use it.

I agree that the brush is broad, and that clever users can operate
the machinery with the safety panels removed. But it's *so* easy to
sidestep const -- with type casts and mutable members -- that I hardly
see where an excess of constness gets in the way of the clever and/or
daring programmer. OTOH, I see numerous occasions where programmers
take for granted that if you're permitted to alter a stored value then
it must be okay to do so. (And I don't mind being protected from my
own forgetfulness and stupidity either. I write a *lot* of code every
year.)

> It might be interesting to explore making set elements const when some
> appropriate compile-time predicate is satisfied by the element and/or
> comparison function, but that gets complicated.  I'm starting to think
> an additional template parameter that makes a set mutable is a better
> approach.

Yep, you can make a case for adding one or more template parameters
to every function and class in STL. You have to ask whether the
added complexity is worth whatever gain you get in usefulness.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

pjp@dinkumware.com ("P.J. Plauger") writes:

[...]

| I agree that the brush is broad, and that clever users can operate
| the machinery with the safety panels removed. But it's *so* easy to
| sidestep const -- with type casts and mutable members -- that I hardly
| see where an excess of constness gets in the way of the clever and/or
| daring programmer.

Mutating elements in a set has nothing to do with being clever.  And
no, spreading casts, made necessary only by a very fanatical idea of
const, is not something my book describes as "so easy".

--
                                                        Gabriel Dos Reis
                                                         gdr@cs.tamu.edu
 Texas A&M University -- Department of Computer Science
 301, Bright Building -- College Station, TX 77843-3112

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

A recent discussion in comp.lang.c++ discussed changing elements of a
std::set. I can't see any previous comments or defect reports about
this, so I thought I would ask for some comments / clarification.

The problem revolves around the fact that it is possible to get a
non-const iterator to a std::set, and therefore change the elements of
the set. However, this will break the relative order of the elements.

I thought perhaps 23.1.2/9 and 23.1.2/10 were trying to enforce the
condition that the set must both be ordered, and remain ordered despite
any alterations any user may make. However if it is supposed to say
that, it really isn't worded very well.

After a few moments thought, it seems very strange to provide non-const
iterators, as there doesn't seem to be any sensible way of implementing
set where the elements can be changed.

What is the symantics supposed to be if users change elements of a set?
(and this applies to other containers as well.) Does the implementation
have to somehow detect this and resort the set? Can it crash if elements
are changed so the set is no longer in order? Is there any chance that
non-const iterators could be withdrawn? (I imagine not now...)

Chris

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

chris wrote:
> A recent discussion in comp.lang.c++ discussed changing elements of a
> std::set. I can't see any previous comments or defect reports about this,
> so I thought I would ask for some comments / clarification.

You didn't search long enough. There were many discussions in the past
both here and on comp.lang.c++.moderated and there's also a DR:

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#103

> The problem revolves around the fact that it is possible to get a
> non-const iterator to a std::set, and therefore change the elements of
> the set. However, this will break the relative order of the elements.
>
> I thought perhaps 23.1.2/9 and 23.1.2/10 were trying to enforce the
> condition that the set must both be ordered, and remain ordered despite
> any alterations any user may make. However if it is supposed to say
> that, it really isn't worded very well.

Those two statements describe the fundamental properties of iterator
traversal and so are not trying to say anything more. About the
statement "remain ordered despite any alterations any user may make"
it's not said explicitly because it's not "true" in the sense the user
is simply not allowed to make any alteration.

> After a few moments thought, it seems very strange to provide non-const
> iterators, as there doesn't seem to be any sensible way of implementing
> set where the elements can be changed.

The rationale for having both set::iterator and set::const_iterator as
two different types is described in issue #103. Please notice that, in
the current standard, iterator can be used for insert() and erase()
while const_iterator can't. Whether this is a good thing or not, you decide.

> What is the symantics supposed to be if users change elements of a set?
> (and this applies to other containers as well.) Does the implementation
> have to somehow detect this and resort the set? Can it crash if elements
> are changed so the set is no longer in order?

It's undefined behaviour. So it may crash or resort the container or
format your HD. The implementation has no obligation to handle such a
case in any defined way.

> ... Is there any chance that
> non-const iterators could be withdrawn? (I imagine not now...)

Don't think so, the rationale is in issue #103. However, have a look at
issue #180 also:
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#180

Alberto

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"chris" <caj@cs.york.ac.uk> wrote in message
news:cs661i$2du$1@pump1.york.ac.uk...

>A recent discussion in comp.lang.c++ discussed changing elements of a
>std::set. I can't see any previous comments or defect reports about this,
>so I thought I would ask for some comments / clarification.

There have been DRs on this topic.

> The problem revolves around the fact that it is possible to get a
> non-const iterator to a std::set, and therefore change the elements of the
> set. However, this will break the relative order of the elements.

Not necessarily. Depends on the ordering rule and the nature of the
set elements. You could, for instance, have a key that is a pair
ordered on its first member. Altering the second member causes no
harm. (Yes, I know this is what a map does for you, but it's still
a valid example.)

> I thought perhaps 23.1.2/9 and 23.1.2/10 were trying to enforce the
> condition that the set must both be ordered, and remain ordered despite
> any alterations any user may make. However if it is supposed to say that,
> it really isn't worded very well.

Indeed. It has been unclear from the start whether a non-const set
iterator can or should be usable to alter the value of an element.

> After a few moments thought, it seems very strange to provide non-const
> iterators, as there doesn't seem to be any sensible way of implementing
> set where the elements can be changed.

There's no sensible way to implement a set when the ordering of an element
relative to others can change, yes.

> What is the symantics supposed to be if users change elements of a set?
> (and this applies to other containers as well.) Does the implementation
> have to somehow detect this and resort the set? Can it crash if elements
> are changed so the set is no longer in order?

Altering the ordering yields undefined behavior, IMO. Which means that
anything can happen, but probably nothing good.

>                                              Is there any chance that
> non-const iterators could be withdrawn? (I imagine not now...)

I forget how we (WG21 library committee) resolved the DR, but I'm pretty
sure the consensus now is that set elements should not be alterable
through set iterators. Since we've offered both const and non-const set
iterators over the years, we now provide a compile-time choice of
behaviors.

FWIW, I have always opposed allowing set elements to change, but we
(Dinkumware) have tried to do what we think the C++ Standard says over
the years, even when we disagree.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"chris" <caj@cs.york.ac.uk> wrote in message
news:cs661i$2du$1@pump1.york.ac.uk...
|A recent discussion in comp.lang.c++ discussed changing elements of a
| std::set. I can't see any previous comments or defect reports about
| this, so I thought I would ask for some comments / clarification.
|
| The problem revolves around the fact that it is possible to get a
| non-const iterator to a std::set, and therefore change the elements of
| the set. However, this will break the relative order of the elements.

Well, it doesn't have t break the order. And I guess that is the whole point
of mutable iterators: you need them if you want to change part of the objects'
state that does not involve
the ordering. Why should we disallow that?

br

Thorsten


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Alberto Barbati" <AlbertoBarbati@libero.it> wrote in message
news:c2NFd.3449$GU.105698@twister1.libero.it...

> Those two statements describe the fundamental properties of iterator
> traversal and so are not trying to say anything more. About the statement
> "remain ordered despite any alterations any user may make" it's not said
> explicitly because it's not "true" in the sense the user is simply not
> allowed to make any alteration.

It's easy to change the ordering of a sequence without changing the values
of its elements.
The simplest example is if the sequence consists of pointers, with the
comparison operation being defined as comparing the values of the objects to
which the pointers 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

pjp@dinkumware.com ("P.J. Plauger") writes:


[...]

| I forget how we (WG21 library committee) resolved the DR, but I'm pretty
| sure the consensus now is that set elements should not be alterable
| through set iterators. Since we've offered both const and non-const set
| iterators over the years, we now provide a compile-time choice of
| behaviors.
|
| FWIW, I have always opposed allowing set elements to change, but we
| (Dinkumware) have tried to do what we think the C++ Standard says over
| the years, even when we disagree.

I've always found that restriction about alteration of set is rather
artificial.  I can see the arguments; but they look more theoretical
than pratical to me.  If a user modifies the set in a way that the
ordering is broken, then it is broken. Period.  The corollary is that,
the standard library should have allowed alteration *as long as the
relative ordering are preserved*.  In most practical situations where
I need a "set", std::set proves itself to be perfectly useless. I just
end up rollong my own.

You mentioned an example very close to std::map; in situations where I
had to roll my own set, most of them were like that. But using std::map,
ended up duplicating the key -- which can be very large (e.g. a string).

--
                                                        Gabriel Dos Reis
                                                         gdr@cs.tamu.edu
 Texas A&M University -- Department of Computer Science
 301, Bright Building -- College Station, TX 77843-3112

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Gabriel Dos Reis" <gdr@cs.tamu.edu> wrote in message
news:m3651zqp5q.fsf@merlin.cs.tamu.edu...
| pjp@dinkumware.com ("P.J. Plauger") writes:
|
|
| [...]
|
|| I forget how we (WG21 library committee) resolved the DR, but I'm pretty
|| sure the consensus now is that set elements should not be alterable
|| through set iterators. Since we've offered both const and non-const set
|| iterators over the years, we now provide a compile-time choice of
|| behaviors.
||
|| FWIW, I have always opposed allowing set elements to change, but we
|| (Dinkumware) have tried to do what we think the C++ Standard says over
|| the years, even when we disagree.

maybe we should allow std::set<const T> to work?

| relative ordering are preserved*.  In most practical situations where
| I need a "set", std::set proves itself to be perfectly useless. I just
| end up rollong my own.
|
| You mentioned an example very close to std::map; in situations where I
| had to roll my own set, most of them were like that. But using std::map,
| ended up duplicating the key -- which can be very large (e.g. a string).

Can you outline the major differences besides mutability of such a set?

Thanks

Thorsten


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

nesotto@cs.auc.dk ("Thorsten Ottosen") writes:

| "Gabriel Dos Reis" <gdr@cs.tamu.edu> wrote in message
| news:m3651zqp5q.fsf@merlin.cs.tamu.edu...
| | pjp@dinkumware.com ("P.J. Plauger") writes:
| |
| |
| | [...]
| |
| || I forget how we (WG21 library committee) resolved the DR, but I'm pretty
| || sure the consensus now is that set elements should not be alterable
| || through set iterators. Since we've offered both const and non-const set
| || iterators over the years, we now provide a compile-time choice of
| || behaviors.
| ||
| || FWIW, I have always opposed allowing set elements to change, but we
| || (Dinkumware) have tried to do what we think the C++ Standard says over
| || the years, even when we disagree.
|
| maybe we should allow std::set<const T> to work?

for what?

| | relative ordering are preserved*.  In most practical situations where
| | I need a "set", std::set proves itself to be perfectly useless. I just
| | end up rollong my own.
| |
| | You mentioned an example very close to std::map; in situations where I
| | had to roll my own set, most of them were like that. But using std::map,
| | ended up duplicating the key -- which can be very large (e.g. a string).
|
| Can you outline the major differences besides mutability of such a set?

mutability is already important.

The other difference is that the comparator is not explicit hard coded
into the type, but is used as argument to find(), insert(), etc.
The values for those parameters are OK, *as far as they preserve the
relative ordering*.
Ah, yes the comparator returns a value that is
  * zero if both arguments are equal;
  * negative when the first argument is less the second;
  * positive when the second argument is greater.
That way, the comparator is not called twice just to decide which
branch to take when traversing the nodes.

My own sets are just adaptors over the fundamental red-black-tree node
(these could be something else). That is just a basic version of more
advanced work done by Matt Austern et al. see

  http://www3.interscience.wiley.com/cgi-bin/abstract/106558112/ABSTRACT


(even though Matt would claim that varying of comparators was not part
of their work, I believe it is already there, it is not just made
explicit ;-))

--
                                                        Gabriel Dos Reis
                                                         gdr@cs.tamu.edu
 Texas A&M University -- Department of Computer Science
 301, Bright Building -- College Station, TX 77843-3112

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Gabriel Dos Reis wrote:
> [...]
> You mentioned an example very close to std::map; in situations where I
> had to roll my own set, most of them were like that. But using std::map,
> ended up duplicating the key -- which can be very large (e.g. a string).

Which is exactly why the committee should consider Boost.IndexedSet,
which allows you to have a map with a key embedded in the value type.

Dave

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Gabriel Dos Reis" <gdr@cs.tamu.edu> wrote in message
news:m3651zqp5q.fsf@merlin.cs.tamu.edu...

> | FWIW, I have always opposed allowing set elements to change, but we
> | (Dinkumware) have tried to do what we think the C++ Standard says over
> | the years, even when we disagree.
>
> I've always found that restriction about alteration of set is rather
> artificial.  I can see the arguments; but they look more theoretical
> than pratical to me.  If a user modifies the set in a way that the
> ordering is broken, then it is broken. Period.  The corollary is that,
> the standard library should have allowed alteration *as long as the
> relative ordering are preserved*.  In most practical situations where
> I need a "set", std::set proves itself to be perfectly useless. I just
> end up rollong my own.

This is a reductio ad absurdum argument against *every* use of
const, IMO. Since you can always defeat a const qualifier, why
bother to use it at all? But we do in fact use const, and we use
it a lot, because it keeps us from making the worst kinds of
mistakes. You have to go out of your way to defeat const and,
perhaps, destroy the internal integrity of a complex structure
(such as a set). That, to me, is the compelling argument for
disallowing easy alteration of a set key.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]