Rich Hickey wrote:
>
> The HP STL did not allow for mutable iteration on sets, i.e. it
> explicitly specified that for sets iterator == const_iterator.
>
> What is the position of the standard on this?

The only thing I can see is from 32.1.2 Associative Containers:

8 The fundamental property of iterators  of  associative  containers  is
  that  they  iterate through the containers in the non-descending order
  of keys where non-descending is defined by  the  comparison  that  was
  used to construct them.

This suggests that if mutating sequence operations were allowed on
associative containers, that the entire container would have to be
resorted, leaving open the question of what happens to the current
iterator.

Consider:

set<int, less<int> > myIntSet;
void main()
{
 myIntSet.insert(1);
 myIntSet.insert(2);
 for (set<int, less<int> >::iterator it = myIntSet.begin();
  it!=myIntSet.end();
  it++)
 {
  (*it)++;
 }
}

If mutating sequence operators are allowed, the above code creates (at
least) two problems.

First, when (*it)++ is first invoked, myIntSet would now contain two
instances of 2, which is not allowed.

Second, would this sequence ever terminate?  Since every (*it)++ would
push the end iterator one position away.

If you replace (*it)++ with (*it)+=2, then the sequence would surely
never terminate.  myIntSet would look like this on each pass:

1,2
2,3
3,4
4,5 etc.

I think these cases present reason enough not to allow mutating
sequences.
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Jason Shankel <no_spam.shankel@crl.com> wrote:

>Rich Hickey wrote:
>>
>> The HP STL did not allow for mutable iteration on sets, i.e. it
>> explicitly specified that for sets iterator == const_iterator.
>>
>> What is the position of the standard on this?

>The only thing I can see is from 32.1.2 Associative Containers:

>... Omitted - quote

>This suggests that if mutating sequence operations were allowed on
>associative containers, that the entire container would have to be
>resorted

>... Omitted - an example of when modifying an element in a set would be a
>problem

>I think these cases present reason enough not to allow mutating
>sequences.

I disagree. While it is possible to cause trouble by modifying an
element in a set, it is not a given. Here are several reasons why
mutable iteration on sets ought to be allowed:

A) Modifying elements in sets can be safe and useful. (*1)

B) Commercial C++ libraries have long allowed for modification of
elements in internally-keyed containers. (*2)

C) Providing only const iteration is an over-protection. (*3)

D) Users desiring the protection of their key by const iteration can
easily do so by exclusively using the (already provided)
const_iterator.

E) sets, being one of the privileged few standard containers, should
not be subject to a needless constraint. (*4)

F) This is C++ for goodness sake.

In any case, the question stands - what does the standard say? I think
your conclusion that it suggests that mutating iteration is not
allowed is unsupported by the text of the draft.

Here's how I read it:

23.1 Table 66 Container requirements states that X::iterator is an
expression of iterator type pointing to T . This is distinct from its
description of X::const_iterator as expression of iterator type
pointing to const T. It also indicates that a.begin() returns type
iterator for non-constant a.

23.1.2 Table 70 states associative container requirements (in addition
to container). This implies associative containers are subject to
table 66.

23.3.3 shows set's non-const begin() returning type iterator, in
apparent compliance with the generic description of the container
requirements in table 66.

************************************
*1) Consider:

class X{
public:
 string key1;
 int key2;
 Y key3;
 int data1,data2,data3;
 //etc
};

It is legal and useful to define a set of X and a Compare function
that only uses key1,key2,key3 as a key. Iterating over the set  and
modifying data1, data2 etc would be perfectly safe. In fact, I'd
hazard a guess that programmers have been able to modify data records
without accidentally modifying their keys for years.

It is often suggested at this point that the programmer use map, but
map is a poor solution to this problem:

A) It requires creation of a new data type to represent key1, key2,
key3.

B) It becomes a hassle for the user to add things to the container, as
they will have to create an instance of this new data type.

C) It is storage inefficient (compared to set), since this new data
type will also have to be stored.

D) It is not really equivalent anyway since we no longer have a
logical collection of X. Because of the way map was written (another
topic entirely), it is logically a collection of pairs - iteration
over a map yields pairs, not X's.

sets are for internal keys, maps are for external keys.

*2) All with the caveat that any modifications not alter the result of
the key-finding-function (compare(), hash()). See IBM Open Class,
formerly ICLCC, Rogue Wave tools.h++, Booch Components etc.

*3) The simple fact is that the elements contained in the sets are
_not_ keys ( and the template parameter is incorrectly named IMO).
That portion of the element that is relevant to the Compare function
is the key. Since the container cannot know what the key is, it should
not be in the business of trying to protect against its modification,
since in doing so it may in fact be prohibiting modification of things
that are not the key.

*4) It is a mistake to (mis)apply some abstract notion of set (by
assuming atomic values and whole-value comparison) and ignore the fact
that sets can be used by developers to hold multi-valued objects,
keyed on only a subset of those values. In addition adding a
const-iteration-only constraint on sets introduces inconsistency
between sets and the other element containers. sets are the only
internally keyed containers provided by the standard, let's make them
as useful as possible.
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Rich Hickey wrote:
>
> I disagree. While it is possible to cause trouble by modifying an
> element in a set, it is not a given. Here are several reasons why
> mutable iteration on sets ought to be allowed:
>
> A) Modifying elements in sets can be safe and useful. (*1)

This is undoubtedly true.

> B) Commercial C++ libraries have long allowed for modification of
> elements in internally-keyed containers. (*2)
>
> C) Providing only const iteration is an over-protection. (*3)

This is more debatable. When I have to muck about with keys, I use a
const_cast, which forces me to think "Do I know what I am doing?" If you
make key-changing easy people might think it's safe, and it isn't.
You can use mutable data members although that might be a bit extreme.

> D) Users desiring the protection of their key by const iteration can
> easily do so by exclusively using the (already provided)
> const_iterator.

Not really, because begin() returns type iterator (as you pointed out),
and so this code:

set<int> setInt;

generate(setInt.begin(),setInt.end(),some_op());

will compile if mutable iteration is the default and probably knacker
the set.

You might argue for const_begin & const_end functions as well, but then
that would make set unique again (something you complained about
somewhere in a clipped portion).

> E) sets, being one of the privileged few standard containers, should
> not be subject to a needless constraint. (*4)

It's not needless, it's needed so you don't accidentally mess up the
ordering of the set.
When you're writing STL code, don't you ever find yourself writing code
that does not depend on what container the iterators are from? If you,
or someone else, later comes along and changes these iterators to be
set<...>::iterator, it will not compile and the person responible can go
"duh!" and do something about it.
If mutable iteration is what you get by default, then it will compile
and strange bugs will surface.

> F) This is C++ for goodness sake.

Your point? We already have countless interesting and entertaining ways
of committing suicide - do we really need more?

One of the points of the original STL was type safety. Should we ignore
all other sorts of safety too?

--
Regards,
    Michael Hudson

Please don't email this address - it's not mine.
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Michael Hudson <sorry.no.email@nowhere.com> wrote:

>Rich Hickey wrote:

>> C) Providing only const iteration is an over-protection. (*3)

>This is more debatable. When I have to muck about with keys, I use a
>const_cast, which forces me to think "Do I know what I am doing?" If you
>make key-changing easy people might think it's safe, and it isn't.

That doesn't really scale. Consider I have a domain specific data type
Person, one of whose members will serve as a key. I need to build a
library of functions for manipulating Persons, many of these functions
will modify the Person, none will change its key. To be as flexible as
possible I will make these template functions taking some T where T is
assumed to be some Iterator<Person>. Do I really want to write a
parallel library for set iterators that uses a const_cast? No. I
certainly don't want to use const_cast throughout the library proper
as that will provide no protection whatsoever.

The bottom line is that I will have to be careful about modifying
Person's key throughout my code - no matter what kinds of container I
keep them in.

>> D) Users desiring the protection of their key by const iteration can
>> easily do so by exclusively using the (already provided)
>> const_iterator.

>Not really, because begin() returns type iterator (as you pointed out),
>and so this code:

>set<int> setInt;

>generate(setInt.begin(),setInt.end(),some_op());

>will compile if mutable iteration is the default and probably knacker
>the set.

This is a problem with the parameterized nature of STL algorithm
interfaces - constness is delivered via promise, not signature.
If you are passing any iterators into any algorithm and want to ensure
that your data will not be modified (for whatever reason) you must
pass const_iterators. This is a general problem not limited to sets.

>You might argue for const_begin & const_end functions as well, but then
>that would make set unique again (something you complained about
>somewhere in a clipped portion).

This is a general problem with a general solution:

template <class T>
inline const T &constize(const T &x)
{return x;}

untrusted(constize(setInt).begin(),constize(setInt).end(),some_op());

will now fail, presumably at instantiation time.
And this supports the tranparent swapping of container/iterator types
quite nicely.

>> F) This is C++ for goodness sake.

>Your point? We already have countless interesting and entertaining ways
>of committing suicide - do we really need more?

I think the case for the chance of suicide is overstated. In any case
it is easily avoided as per above. I think the programmer should be in
charge.
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

The HP STL did not allow for mutable iteration on sets, i.e. it
explicitly specified that for sets iterator == const_iterator.

What is the position of the standard on this?

In reading the latest public review draft I don't see support for this
policy, in fact I think the standard implies that sets do support
mutable iteration, i.e. begin() on a non-const set yields an iterator
on non-const T.

Or did I miss something?
---
[ 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         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]