jpotter@falcon.lhup.edu (John Potter) wrote:

>
>On 27 Nov 99 07:44:42 GMT, sirwillard@my-deja.com wrote:
>
>:    mutable Task* task;  // Mutable is the key here for the proxy
>: };
>
>This is a mutable (Task*).  You may change the value of task in a
>const TaskProxy.
>
>It is not a (mutable Task)*.  You may not call a non-const Task
>member through this pointer.

Actually, you can call a non-const Task member through this pointer.
This pointer points to a non-const Task, whether or not the pointer
itself is const or mutable. The mutable keyword neither helps nor
hinders this ability.

>Mutable is a storage class specifier not a cv qualifier.  There is
>no such thing as pointer to mutable Task, nor, for that matter, a
>mutable Task to point to.  Been there, done that. :)

Right.

---------------------------------------------------------------
Pablo Halpern                              phalpern@newview.org
Check out my new book, The C++ Standard Library from Scratch at
http://www.halpernwightsoftware.com/stdlib-scratch
---
[ 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 <383a1561.29603635@news.csrlink.net>,
  jpotter@falcon.lhup.edu (John Potter) wrote:
> On 22 Nov 1999 17:48:30 GMT, Jean-Denis <jdmv@NEVERSPAMmail.com>
wrote:
>
> :
> : Thank you all for your many answers. I think I now understand the
issue
> : correctly: associative containers iterators are not mutable,
because if
> : they were, there would be no way to guaranty that the collection
stays
> : ordered correctly.
>
> Yes.
>
> : It remains, that there is a legitimate need for a programmer to be
able to
> : change objects in such a container by iterating over it, *provided*
the
> : ordering of the elements is not changed <see note below>.
>
> Agree.
>
> : In that case, declaring relevant members as mutable, and
corresponding
> : member functions as const is not satisfying, as the member object
> : semantic is altered even out of the context of the container.
>
> Agree.
>
> : Casting away const out of the iterator is not very satisfying
either.
>
> But it works and is your responsibility.  It clearly shows in your
> code that you are doing something dangerous.

My turn to agree.

> : The only solution left is to use two classes: they key in the
container,
> : with a pointer to the "mutable" part. The proxie idea belongs to
that
> : category.  The drawback is some loss of efficiency, which can become
> : significant in the case of lightweight elements.
>
> It also splits what is logically a unit into two parts.

Not if a proxy is used.  I think my original suggestion is being
misconstrued here, leading to confusion.

>  Map would give
> the same result.

I don't follow you here.

>  How does proxy fit here?

Like this:

class Task
{
public:
   Task(int order) : order(order) { }
   void Schedule() { ... }
   bool operator==(const Task&) const { ... }
   bool operator<(const Task&) const { ... }
   ...

private:
   int order;
   ...
};

Task can be placed in a set, but Schedule can't be called, because it's
a non-const method of Task.  So, we use a proxy instead:

class TaskProxy
{
public:
   TaskProxy(Task& task) : task(&task) { }
   void Schedule() const { task->Schedule(); }
   bool operator==(const TaskProxy& rhs) const {
      return task->operator==(*rhs.task);
   }
   bool operator!=(const TaskProxy& rhs) const {
      return task->operator!=(*rhs.task);
   }
   // Must also forward all other (relevant) Task methods
   ...

private:
   mutable Task* task;  // Mutable is the key here for the proxy
};

The code is incomplete, but illustrates how the Proxy pattern can add
or remove const qualifications from methods.  All we do now is declare
our set to contain TaskProxy's instead of Task's, and we can call
Schedule, "safe" in the knowledge that it modifies only the parts of
Task that are not part of the collation information.

However, this does add the overhead of another indirection.  Extra
function call overhead should be optimized out by inline code, but we
still have to dereference the task pointer.  I doubt that in most
situations this extra overhead will be significant, but I guess it's
the complaint here.

> You could also put the data in a list and put pointers (or list
> iterators) in the set.  One more level of indirection here also.
>
> [snip example of modifying key without changing order]
>
> : Anyway, in my case, I decided to drop multiset and use a vector. I
make
> : sure to sort the vector when necessary. In my case, that's no big
deal.
>
> That is an alternative to const_cast.  Now you are responsible again.

The difference being that the sorting will likely take a significantly
larger amount of time than any of the other alternatives.  It still may
be the proper choice, but for someone concerned with efficiency, it
sounds like it is probably a bad choice.

> : This really demonstrate the problem with associative containers:
they
> : might get more customers if they were just a tiny bit more
accomodating...
>
> Consider writing iterator::operator* to use a proxy which maintains
the
> order by throwing an exception when it is violated.  I think you will
> quickly conclude that it can not be done.

I won't say "can not".  In his implementation of String in More
Effective C++ Scott Meyers uses a Proxy class that with a little
adaptation could conceivably do just this.  However, it does have
enough problems and disadvantages that I don't think I'd care for this
approach in a "generic" container.  After all, this would result in
less efficiency then the hand coded Proxy I presented above, even if it
didn't lead to subtle programming errors.

> What is doable is to allow non-const iterators and give the
> responsibility to the user.  My preference is to take the
responsibility
> by using const_cast.  Reasonable people may disagree.

I'm not sure it's reasonable, but I guess the "experts" are arguing
this point as we speak.


Sent via Deja.com http://www.deja.com/
Before you buy.
---
[ 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 27 Nov 99 07:44:42 GMT, sirwillard@my-deja.com wrote:

: class Task
: {
: public:
:    Task(int order) : order(order) { }
:    void Schedule() { ... }
:    bool operator==(const Task&) const { ... }
:    bool operator<(const Task&) const { ... }
:    ...
:
: private:
:    int order;
:    ...
: };
:
: Task can be placed in a set, but Schedule can't be called, because it's
: a non-const method of Task.  So, we use a proxy instead:
:
: class TaskProxy
: {
: public:
:    TaskProxy(Task& task) : task(&task) { }
:    void Schedule() const { task->Schedule(); }
:    bool operator==(const TaskProxy& rhs) const {
:       return task->operator==(*rhs.task);
:    }
:    bool operator!=(const TaskProxy& rhs) const {
:       return task->operator!=(*rhs.task);
:    }
:    // Must also forward all other (relevant) Task methods
:    ...
:
: private:
:    mutable Task* task;  // Mutable is the key here for the proxy
: };

This is a mutable (Task*).  You may change the value of task in a
const TaskProxy.

It is not a (mutable Task)*.  You may not call a non-const Task
member through this pointer.

Mutable is a storage class specifier not a cv qualifier.  There is
no such thing as pointer to mutable Task, nor, for that matter, a
mutable Task to point to.  Been there, done that. :)

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              ]

sirwillard@my-deja.com wrote:

>class TaskProxy
>{
>public:
>   TaskProxy(Task& task) : task(&task) { }
>   void Schedule() const { task->Schedule(); }
>   bool operator==(const TaskProxy& rhs) const {
>      return task->operator==(*rhs.task);
>   }
>   bool operator!=(const TaskProxy& rhs) const {
>      return task->operator!=(*rhs.task);
>   }
>   // Must also forward all other (relevant) Task methods
>   ...
>
>private:
>   mutable Task* task;  // Mutable is the key here for the proxy
>};

As John Potter points out, mutable refers to the storage class of the
pointer, not the pointed-to task. It is, in fact both useless and
unnecessary here, since the task member is not a pointer-to-const to
begin with, even if the TaskProxy is const. Leave out mutable and this
code will still work.

>The code is incomplete, but illustrates how the Proxy pattern can add
>or remove const qualifications from methods.  All we do now is declare
>our set to contain TaskProxy's instead of Task's, and we can call
>Schedule, "safe" in the knowledge that it modifies only the parts of
>Task that are not part of the collation information.
>
>However, this does add the overhead of another indirection.  Extra
>function call overhead should be optimized out by inline code, but we
>still have to dereference the task pointer.  I doubt that in most
>situations this extra overhead will be significant, but I guess it's
>the complaint here.

Since you have the extra indirection, you can dispense with the Proxy
class entirely. E.g.:

  set<Task*> mytasks;
  for (set<Task*>::const_iterator iter = mytask.begin();
       iter != mytask.end(); ++iter)
    (*iter)->Schedule();

This code will work even if mytasks is const, since the (*iter) is a
pointer to a non-const Task object. The proxy would be a unnecessary
complication. You would get more bang for the buck by replacing the
proxy with a smart pointer (e.g. a reference counted pointer class).
Then at least you'd get garbage collection.

On the other hand, you could redesign your proxy to eliminate the
indirection as follows:

  class TaskProxy
  {
  public:
    TaskProxy(const Task& t) : task(t) { } // Requires copy constructor
    void Schedule() const { task.Schedule(); }

    // Make sure collation works:
    friend bool operator< (const TaskProxy& t1, const TaskProxy& t2)
      { return t1.task < t2.task; }

    // Must also forward all other (relevant) Task methods
    // ...

    // This conversion is optional:
    operator Task& () { return task; }
    operator const Task& () const { return task; }
  private:
    mutable Task task;  // Mutable is the key here for the proxy
  };

I assume Task has a valid copy constructor, since the original post
involved adding task *objects* to a set. (As I said, adding task
*pointers* to a set does not require a proxy.)

>> You could also put the data in a list and put pointers (or list
>> iterators) in the set.  One more level of indirection here also.

This at least fixes the garbage collection problem (the list destructor
destroyes all of the Task objects).

---------------------------------------------------------------
Pablo Halpern                              phalpern@newview.org
Check out my new book, The C++ Standard Library from Scratch at
http://www.halpernwightsoftware.com/stdlib-scratch


[ 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              ]

jpotter@falcon.lhup.edu (John Potter) wrote:

>
>: Casting away const out of the iterator is not very satisfying either.
>
>But it works and is your responsibility.  It clearly shows in your
>code that you are doing something dangerous.

As a "expert" in The C++ Library (see my .sig), I have found this
discusion to be one of the most enlightening in a while. Before reading
these posts, I was leaning in favor of resolving the current ambiguity
in the standard by having non-const iterators for set and multiset. I
now would advocate having all set and multset iterators be const.

Here's another point to consider: Until I read Matt Austern's post, the
argument I kept hearing for const-only iterators for set and multiset
was that it was necessary to prevent the user from modifying the sort
order. I found this to be a specious argument because the sort order is
use-defined and can be modified in several ways. For example:

 set<int*, indirect_less<int> > s1;
 s1.insert(new int(1));
 s1.insert(new int(2));
 // s1 now contains (&1, &2)
 **s1.begin() = 3; // Change value pointed to by first element
 // s1 now contains (&3, &2) and is invalid

[ Aside: indirect_less is a function object in my personal library that
returns true *arg1 < *arg2 ]
Thus, the restriction on directly modifying the element does not prevent
invalidating the container (although it does catch *some* potential
errors). The real problem is that non-application-specific generic
algorithms could wreak havoc on a container, as in the case of the
remove() algorithm. Matt's summary pointed this out beautifully. The
dilema to be solved is how to allow application-specific code to modify
the elements in a smart way (smart == without changing the sort order)
while preventing generic code from modifying the elements in a dumb way
(dumb == assigning values willy-nilly without regard to sort order). The
const_cast solution does exactly this. The const_cast must be applied on
a per-element basis, so there is no way to pass non-const iterators to a
generic function.

The only remaining problem I see is a psychological issue that I have
witnessed in this thread: some people get queazy at the sight of a
const_cast (or any cast). I don't happen to share this revulsion. The
new-style casts, especially const_cast and dynamic_cast are ways to get
exactly what you want without accidentally getting what you don't want.
(static_cast and reinterpret_cast are more dangerous, though.)

The set<T>::iterator *could*, I suppose, supply an unconst() member
function which would return a proxy pointer. E.g.:

 set<X>::iterator i = s.begin();
        *i.unconst() = X("abc");

It is vital that the value returned by unconst *NOT* act as an iterator
itself, or else one could then pass it to a generic algorithm and the
whole problem would come back. Personally, I think const_cast is
simpler, more direct, and requires fewer changes to the standard.

---------------------------------------------------------------
Pablo Halpern                              phalpern@newview.org
Check out my new book, The C++ Standard Library from Scratch at
http://www.halpernwightsoftware.com/stdlib-scratch


[ 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 22 Nov 1999 17:48:30 GMT, Jean-Denis <jdmv@NEVERSPAMmail.com> wrote:

:
: Thank you all for your many answers. I think I now understand the issue
: correctly: associative containers iterators are not mutable, because if
: they were, there would be no way to guaranty that the collection stays
: ordered correctly.

Yes.

: It remains, that there is a legitimate need for a programmer to be able to
: change objects in such a container by iterating over it, *provided* the
: ordering of the elements is not changed <see note below>.

Agree.

: In that case, declaring relevant members as mutable, and corresponding
: member functions as const is not satisfying, as the member object
: semantic is altered even out of the context of the container.

Agree.

: Casting away const out of the iterator is not very satisfying either.

But it works and is your responsibility.  It clearly shows in your
code that you are doing something dangerous.

: The only solution left is to use two classes: they key in the container,
: with a pointer to the "mutable" part. The proxie idea belongs to that
: category.  The drawback is some loss of efficiency, which can become
: significant in the case of lightweight elements.

It also splits what is logically a unit into two parts.  Map would give
the same result.  How does proxy fit here?

You could also put the data in a list and put pointers (or list
iterators) in the set.  One more level of indirection here also.

[snip example of modifying key without changing order]

: Anyway, in my case, I decided to drop multiset and use a vector. I make
: sure to sort the vector when necessary. In my case, that's no big deal.

That is an alternative to const_cast.  Now you are responsible again.

: This really demonstrate the problem with associative containers: they
: might get more customers if they were just a tiny bit more accomodating...

Consider writing iterator::operator* to use a proxy which maintains the
order by throwing an exception when it is violated.  I think you will
quickly conclude that it can not be done.

What is doable is to allow non-const iterators and give the
responsibility to the user.  My preference is to take the responsibility
by using const_cast.  Reasonable people may disagree.

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              ]

Thank you all for your many answers. I think I now understand the issue
correctly: associative containers iterators are not mutable, because if they
were, there would be no way to guaranty that the collection stays ordered
correctly.

It remains, that there is a legitimate need for a programmer to be able to
change objects in such a container by iterating over it, *provided* the
ordering of the elements is not changed <see note below>.

In that case, declaring relevant members as mutable, and corresponding member
functions as const is not satisfying, as the member object semantic is
altered even out of the context of the container.

Casting away const out of the iterator is not very satisfying either.

The only solution left is to use two classes: they key in the container, with
a pointer to the "mutable" part. The proxie idea belongs to that category.
The drawback is some loss of efficiency, which can become significant in the
case of lightweight elements.

<Note>: the most common way to make sure the element ordering is unaltered is
to avoid changing the element members that constitute the ordering key.
However this is not the only valid case. Here is a real-life example: in a
MIDI sequencer application, one might want to store all MIDI notes as
lightweight objects in a multiset. A MIDInote class would have three members:
time, pitch, duration. The ordering key is "time": the time at which the note
is supposed to start playing.

Now how does the sequencer implement the common "Quantize" command [quantize
means making sure all notes start (and end) at "whole" time values, such as
every beat, every quarter note, every eighth note- whatever]: the natural
idea is to iterate over the multiset and change the "time" member of each
note in turn, by rounding it. At the end of the iteration, all elements keys
have changed, and yet the ordering has not.

Anyway, in my case, I decided to drop multiset and use a vector. I make sure
to sort the vector when necessary. In my case, that's no big deal. This
really demonstrate the problem with associative containers: they might get
more customers if they were just a tiny bit more accomodating...

Jean-Denis


On Fri, 19 Nov 1999 23:35:03 +0100, sirwillard@my-deja.com wrote
(in message <814g8g$ama$1@nnrp1.deja.com>):

>
> In article <383447AC.5DB3DCC@physik.tu-muenchen.de>,
>   Christopher Eltschka <celtschk@physik.tu-muenchen.de> wrote:
>> Jean-Denis wrote:
>>> I stored objects representing tasks for a batch in a multiset, and I
>>> wanted
>>> to iterate over all tasks in the set to schedule them for execution. The
>>> problem is Task::Schedule is not const. And the compiler rightly
>>> complains.
>>
>> If Task::Schedule changes those attributes which are responsible
>> for the order, the compiler compains rightfully even from a logical
>> point of view.
>> Otherwise you've just hit a principal limitation: You cannot declare
>> part of the object as const.
>>



[ 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              ]

Jean-Denis wrote:
>
> Hi,
>
> I was hit by the fact that iterator in multiset (and set) is a const
> iterator. Why is that so? I kind of can understand it for set, as set
> discards element that are already in the set, but I don't understand why it
> is so in multiset? Even for set actually, why not let the programmer decide
> that he really wants to do it?

Because the set is ordered.
Assume you have the set (1, 2, 3), and iter points to 2. Now you do:

int& value = *iter;
value = 4;

Now the set looks like

(1, 4, 3)

that is, the order is destroyed.
Note that the set cannot intercept this code (the reference is there
to make this clear): The assignment is done outside of the set.
The only way to avoid that is preventing the user from changing the
object.

>
> I stored objects representing tasks for a batch in a multiset, and I wanted
> to iterate over all tasks in the set to schedule them for execution. The
> problem is Task::Schedule is not const. And the compiler rightly complains.

If Task::Schedule changes those attributes which are responsible
for the order, the compiler compains rightfully even from a logical
point of view.
Otherwise you've just hit a principal limitation: You cannot declare
part of the object as const.

A solution might be to split the object in two parts, one containing
those parts which are responsible for the sorting order, and one
containing those parts which get changed by scheduling.

Another possibility might be that Task::Shedule doesn't change the
logical state of the object. In that case, you can make the modified
members mutable and Task::Shedule const.


It would be nice to have a way to "parition" an object and
declare only a given partition as const. Say something like

class Foo
{
public:
  void modify_all() { a=3; b=6; }
  void modify() const<"order">
  {
    b=5; // Ok
    // a=5; would be error
  }
  void foo() const {} // may modify neither a nor b
private:
  int "order" a; // a has the attribute "order"
  int b;
};

bool operator<(Foo const& x, Foo const& y)
{
  return x.a < y.a;
}

void f1(Foo& c) { c.foo(); c.modify(); c.modify_all() }
void f2(Foo const<"order">& c) { c.foo(); c.modify(); }
void f3(Foo const& c) { c.foo(); }

int main()
{
  Foo x1;
  Foo const<"order"> x2;
  Foo const x3;

  // Now only the following calls are possible:
  f1(x1); f2(x1); f3(x1);
  f2(x2); f2(x3);
  f3(x3);
}
---
[ 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 <383447AC.5DB3DCC@physik.tu-muenchen.de>,
  Christopher Eltschka <celtschk@physik.tu-muenchen.de> wrote:
> Jean-Denis wrote:
> > I stored objects representing tasks for a batch in a multiset, and I wanted
> > to iterate over all tasks in the set to schedule them for execution. The
> > problem is Task::Schedule is not const. And the compiler rightly complains.
>
> If Task::Schedule changes those attributes which are responsible
> for the order, the compiler compains rightfully even from a logical
> point of view.
> Otherwise you've just hit a principal limitation: You cannot declare
> part of the object as const.
>
> A solution might be to split the object in two parts, one containing
> those parts which are responsible for the sorting order, and one
> containing those parts which get changed by scheduling.

This can be done with out a rearchitecture of the current classes
simply by using a proxy class.  Instead of storing Task objects in his
set he'll instead store TaskProxy objects.  The proxy will insure the
portions of Task responsible for collation within the set remain const
while the rest of the elements remain mutable.  The proxy's Schedule
can be safely declared const (deferring to the mutable Task object)
since we know Schedule won't modify the state required for collation
within the set.

> Another possibility might be that Task::Shedule doesn't change the
> logical state of the object. In that case, you can make the modified
> members mutable and Task::Shedule const.

It's not the state we're worried about here.  It's the collation
properties.  The state may well include properties not required by the
collation, thus preventing the possiblity of a const method yet
remaining safe within this particular context.  The proxy approach is
likely the best because of this.

> It would be nice to have a way to "parition" an object and
> declare only a given partition as const. Say something like
>
> class Foo
> {
> public:
>   void modify_all() { a=3; b=6; }
>   void modify() const<"order">
>   {
>     b=5; // Ok
>     // a=5; would be error
>   }
>   void foo() const {} // may modify neither a nor b
> private:
>   int "order" a; // a has the attribute "order"
>   int b;
> };
>
> bool operator<(Foo const& x, Foo const& y)
> {
>   return x.a < y.a;
> }
>
> void f1(Foo& c) { c.foo(); c.modify(); c.modify_all() }
> void f2(Foo const<"order">& c) { c.foo(); c.modify(); }
> void f3(Foo const& c) { c.foo(); }
>
> int main()
> {
>   Foo x1;
>   Foo const<"order"> x2;
>   Foo const x3;
>
>   // Now only the following calls are possible:
>   f1(x1); f2(x1); f3(x1);
>   f2(x2); f2(x3);
>   f3(x3);
> }

I'm not sure this would be so nice.  It seems problematic and kludgy,
and there are already known idioms for achieving the same thing with
out a language change.  First question the useage (in this case, I
still bet that set isn't the right container).  Second look for known
patterns to solve the problems inherant in the useage.  Only if you
fail in both of these should you then move on to dreaming about a
language change (which is folly any way, since there won't be one now
for some time to come).


Sent via Deja.com http://www.deja.com/
Before you buy.


[ 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              ]

Hi,

I was hit by the fact that iterator in multiset (and set) is a const
iterator. Why is that so? I kind of can understand it for set, as set
discards element that are already in the set, but I don't understand why it
is so in multiset? Even for set actually, why not let the programmer decide
that he really wants to do it?

I stored objects representing tasks for a batch in a multiset, and I wanted
to iterate over all tasks in the set to schedule them for execution. The
problem is Task::Schedule is not const. And the compiler rightly complains.

Thank you for your help.

Jean-Denis

(remove the obvious anti spam string to get my email address)



[ 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              ]

Jean-Denis <jdmv@NEVERSPAMmail.com> writes:

> Hi,
>
> I was hit by the fact that iterator in multiset (and set) is a const
> iterator. Why is that so? I kind of can understand it for set, as set
> discards element that are already in the set, but I don't understand why it
> is so in multiset? Even for set actually, why not let the programmer decide
> that he really wants to do it?

It's not clear whether set<>::iterator should be const or
mutable; the C++ standard is inconsistent in this respect.
The committee is aware of this issue, and is considering
it.  There are different opinions within the committee on
how to deal with the inconsistency.

Assuming for the moment that set<>::iterator really is to
be const, the reason is to prevent operations that would
change the ordering of set elements.  (Similarly, that's
why the value type of map<> is declared to be pair<const
Key, Data> rather than pair<Key, Data>.)  It is a class
invariant that the elements of set<> and map<> are always
arranged in ascending order by key, and operations that
violate that invariant would be a serious error.  If, for
example, the elements of a set<int> are 1, 2, 3, 4, 5, and
if the user performed an operation that changed the second
element from 2 to 7, then the set<> would no longer be
valid.  It would be in a corrupted state, it's quite likely
that performing any operations on it would result in a core
dump.

The argument in favor of making set<>::iterator a const
iterator is to prevent people from using algorithms like
std::remove() or std::reverse() on a set.  Something like
that is almost certainly an error, and it's nice to know
about errors at compile time rather than run time.  (It's
still possible for users to violate the set<> and map<>
ordering invariants if they cast away constness, but at
least that way it's obvious from the source code that
they're doing something dangerous.)

The argument in favor of making set<>::iterator a mutable
iterator is the one you've given above: sometimes you might
happen to know that you can safely call a non-const member
function without disturbing the set<>'s ordering relation,
and sometimes it's useful to do that.


[ 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              ]

Jean-Denis <jdmv@NEVERSPAMmail.com> writes:

> Hi,
>
> I was hit by the fact that iterator in multiset (and set) is a const
> iterator. Why is that so? I kind of can understand it for set, as set
> discards element that are already in the set, but I don't understand why it
> is so in multiset? Even for set actually, why not let the programmer decide
> that he really wants to do it?

It's not clear whether set<>::iterator should be const or
mutable; the C++ standard is inconsistent in this respect.
The committee is aware of this issue, and is considering
it.  There are different opinions within the committee on
how to deal with the inconsistency.

Assuming for the moment that set<>::iterator really is to
be const, the reason is to prevent operations that would
change the ordering of set elements.  (Similarly, that's
why the value type of map<> is declared to be pair<const
Key, Data> rather than pair<Key, Data>.)  It is a class
invariant that the elements of set<> and map<> are always
arranged in ascending order by key, and operations that
violate that invariant would be a serious error.  If, for
example, the elements of a set<int> are 1, 2, 3, 4, 5, and
if the user performed an operation that changed the second
element from 2 to 7, then the set<> would no longer be
valid.  It would be in a corrupted state, it's quite likely
that performing any operations on it would result in a core
dump.

The argument in favor of making set<>::iterator a const
iterator is to prevent people from using algorithms like
std::remove() or std::reverse() on a set.  Something like
that is almost certainly an error, and it's nice to know
about errors at compile time rather than run time.  (It's
still possible for users to violate the set<> and map<>
ordering invariants if they cast away constness, but at
least that way it's obvious from the source code that
they're doing something dangerous.)

The argument in favor of making set<>::iterator a mutable
iterator is the one you've given above: sometimes you might
happen to know that you can safely call a non-const member
function without disturbing the set<>'s ordering relation,
and sometimes it's useful to do that.


[ 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 <01HW.B459C5DB0010277E0992A58C@news.cybercable.fr>,
  jdmv@NEVERSPAMmail.com wrote:
>
> Hi,
>
> I was hit by the fact that iterator in multiset (and set) is a const
> iterator. Why is that so? I kind of can understand it for set, as set
> discards element that are already in the set, but I don't understand why it
> is so in multiset? Even for set actually, why not let the programmer decide
> that he really wants to do it?
>
> I stored objects representing tasks for a batch in a multiset, and I wanted
> to iterate over all tasks in the set to schedule them for execution.  The
> problem is Task::Schedule is not const. And the compiler rightly complains.
>
> Thank you for your help.
>
> Jean-Denis

The set elements are keys in an internal tree.  If the iterator were to
allow you to change the stored object (i.e. it wasn't a const_iterator)
then the change you make is likely to change the order in which the
element would be inserted in the tree, which would cause havoc on the
stability of the container.  The long and short of it is... it's
impossible to return anything but a const_iterator if the set (or
multiset) is to be gauranteed to remain valid.

It sounds like you've chosen the wrong container type.  If you
explained things a little more thoroughly someone could likely suggest
a better design.


Sent via Deja.com http://www.deja.com/
Before you buy.


[ 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 <fxtyabv4j3r.fsf@isolde.engr.sgi.com>,
  Matt Austern <austern@sgi.com> wrote:

> The argument in favor of making set<>::iterator a mutable
> iterator is the one you've given above: sometimes you might
> happen to know that you can safely call a non-const member
> function without disturbing the set<>'s ordering relation,
> and sometimes it's useful to do that.

There are numerous ways to do this without requiring removal of the
const_iterator idiom.  The simplest is to make the parts that can be
safely modified mutable.  For existing objects the same effect can be
achieved by using a proxy object.  Unless an efficient method can be
devised to insure the container validity, and to prevent calls to
algorithms which could corrupt the container, then I don't know why the
committee is even considering this (if they are).


Sent via Deja.com http://www.deja.com/
Before you buy.


[ 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 18 Nov 1999 20:49:26 GMT, Matt Austern <austern@sgi.com> wrote:

:
: Jean-Denis <jdmv@NEVERSPAMmail.com> writes:
:
: > Hi,
: >
: > I was hit by the fact that iterator in multiset (and set) is a const
: > iterator. Why is that so? I kind of can understand it for set, as set
: > discards element that are already in the set, but I don't understand why it
: > is so in multiset? Even for set actually, why not let the programmer decide
: > that he really wants to do it?
:
: It's not clear whether set<>::iterator should be const or
: mutable; the C++ standard is inconsistent in this respect.
: The committee is aware of this issue, and is considering
: it.  There are different opinions within the committee on
: how to deal with the inconsistency.

[snip good descriptions of the views]

I have followed this problem for several years.  I think there
is a basic conflict between the containers desired and the
containers provided.

Set<> provides a very reasonable "set".  Everything is very
sensible when viewed as a set of elements from a universe.  A
const iterator fits.

Map<> provides a very reasonable association between a const
key and variable attributes.

When the element is a physical record with key field(s), an
ordered collection of records with the ability to modify all
fields except the key(s) is desired.

Using set<> requires const_cast to modify the non-key fields.

Using map<> requires duplication of the key field(s) or splitting
the record into two pieces.

It is fairly easy to modify set<> to meet these needs.  If insert
does a copy when there is a match, the non-key fields are
modified as desired.  Extending this to iterators, however, is not
that simple and violates the general rules of iterators.  It would
require a proxy class to decide read/write and some decision in
what to do with an unequal write.

IMHO, set<> and map<> are both well designed for the intended
applications.  An ordered collection is simply not in the standard,
and trying to force the others creates the problems.

I use a "ReplacementSet" which has replace on insert and const
iterators.  I do not miss the ability to modify through an iterator
because I find that modifications are of the form find/change.  I
see changes as coming from outside information rather than a
traversal of the contents.  YMMV.  OTOH, if the traversal is a
for loop with the set available, insert can still be used with the
iterator.

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              ]