std::set iterators
Sergey P. Derevyago
the same types? If not, then the definition of std::set is incorrect.
BTW SGI STL documentation (http://www.sgi.com/tech/stl/set.html) clearly says
so (for the obvious reasons).
--
With all respect, Sergey. http://cpp3.virtualave.net/
mailto : ders at skeptik.net
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std...@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Matthew Austern
> Does the standard say that std::set::iterator and std::set::const_iterator are
> the same types?
No. It doesn't say one way or the other.
> If not, then the definition of std::set is incorrect.
It is known to be incorrect, and there is a defect report on it. The
resolution chosen by the LWG isn't quite to say that std::set::iterator
and std::set::const_iterator must be the same type. It's to say that
std::set::iterator is a constant iterator, and that it's unspecified
whether or not the two iterators are the same type.
Vahan Margaryan
>
> It is known to be incorrect, and there is a defect report on it. The
> resolution chosen by the LWG isn't quite to say that std::set::iterator
> and std::set::const_iterator must be the same type. It's to say that
> std::set::iterator is a constant iterator, and that it's unspecified
> whether or not the two iterators are the same type.
Unfortunately, before the resolution was chosen, implementors made
their choices :) There is at least one implementation (Dinkum's),
where std::set::iterator is not constant.
Since the standard didn't take a stand on this, we felt safe to use
set iterators as non-constant. It makes sense, in situations like
this:
class Person {
public:
explicit Person(const string& s) : name_(s), age_(0){}
const string& name()const;
bool operator<(const Person& rhs)const { return name_ < rhs.name_; }
void age(int i);
int age()const;
private:
const string name_; //name is constant, so operator< is always
consistent
int age_; //changing age doesn't hurt set
};
set<Person> people;
Now, lots of code has to be rewritten (even though it's conceptually
safe, like the one above).
Might there be a better solution than to ban non-constant access
completely? Doesn't this hurt the usability of set? Maybe a
customizable solution could be suggested, where the user gets a safe
set by default, but can go unsafe at his own risk?
Regards,
-Vahan
P.J. Plauger
> Unfortunately, before the resolution was chosen, implementors made
> their choices :) There is at least one implementation (Dinkum's),
> where std::set::iterator is not constant.
True enough. Nevertheless, we favor making set elements immutable,
so the casual user can't destroy the integrity of set order.
> Might there be a better solution than to ban non-constant access
> completely? Doesn't this hurt the usability of set? Maybe a
> customizable solution could be suggested, where the user gets a safe
> set by default, but can go unsafe at his own risk?
We've changed our implementation to permit either mutable or immutable
set elements, because of this mixed prior art.
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
Andrew Koenig
Vahan> Since the standard didn't take a stand on this, we felt safe to
Vahan> use set iterators as non-constant. It makes sense, in
Vahan> situations like this:
Vahan> class Person {
Vahan> public:
Vahan> explicit Person(const string& s) : name_(s), age_(0){}
Vahan> const string& name()const;
Vahan> bool operator<(const Person& rhs)const { return name_ < rhs.name_; }
Vahan> void age(int i);
Vahan> int age()const;
Vahan> private:
Vahan> const string name_; //name is constant, so operator< is always consistent
Vahan> int age_; //changing age doesn't hurt set
Vahan> };
Vahan> set<Person> people;
Vahan> Now, lots of code has to be rewritten (even though it's
Vahan> conceptually safe, like the one above).
Lots of code? Why not just define age_ as mutable?
--
Andrew Koenig, a...@research.att.com, http://www.research.att.com/info/ark
John Potter
wrote:
> Vahan> set<Person> people;
>
> Vahan> Now, lots of code has to be rewritten (even though it's
> Vahan> conceptually safe, like the one above).
>
> Lots of code? Why not just define age_ as mutable?
Because it does not make sense for a Person const to have a mutable
age? Why break everything else to make set work? The set iterator
provides a const access only and const_cast works.
John
John Potter
wrote:
> Since the standard didn't take a stand on this, we felt safe to use
> set iterators as non-constant. It makes sense, in situations like
> this:
> class Person {
> public:
> explicit Person(const string& s) : name_(s), age_(0){}
> const string& name()const;
>
> bool operator<(const Person& rhs)const { return name_ < rhs.name_; }
>
> void age(int i);
> int age()const;
> private:
> const string name_; //name is constant, so operator< is always
> consistent
Watch out for concept checking versions of the library. The value_type
is not assignable and that is a requirement for all standard containers.
> int age_; //changing age doesn't hurt set
> };
>
> set<Person> people;
>
> Now, lots of code has to be rewritten (even though it's conceptually
> safe, like the one above).
const_cast<Person&>(people.begin()).age(42);
A constant iterator returns a const T&, not a convertable to T. The
cast must work and you know that it is safe.
You may find the boost::projection iterator useful to hide the cast.
I think it is a bit of an overkill.
Yes, I understand your problem. Just offering a work around. I think
the const_cast is the accepted way to make set useful for something
more like a relational database than a set. No, I would not even
think of suggesting that you split your class to use a map.
John
Andrew Koenig
John> Because it does not make sense for a Person const to have a mutable
John> age? Why break everything else to make set work? The set iterator
John> provides a const access only and const_cast works.
Of course it makes sense. You're saying that changing age_ does not
change the value of the object, because two objects that differ only
in age_ are considered equal.
--
Andrew Koenig, a...@research.att.com, http://www.research.att.com/info/ark
---
John Potter
wrote:
> >> Lots of code? Why not just define age_ as mutable?
>
> John> Because it does not make sense for a Person const to have a mutable
> John> age? Why break everything else to make set work? The set iterator
> John> provides a const access only and const_cast works.
>
> Of course it makes sense. You're saying that changing age_ does not
> change the value of the object, because two objects that differ only
> in age_ are considered equal.
No. He is saying that name is the key for the set and that it is ok
to change the age of a Person in the set. You are saying that it is
ok to change the age of a Person const anywhere in this or other
applications which use the Person class. Two very different things.
John
Vahan Margaryan
> On Fri, 8 Mar 2002 20:19:01 GMT, Andrew Koenig <a...@research.att.com>
> wrote:
>
> > >> Lots of code? Why not just define age_ as mutable?
> >
> > Of course it makes sense. You're saying that changing age_ does not
> > change the value of the object, because two objects that differ only
> > in age_ are considered equal.
>
> No. He is saying that name is the key for the set and that it is ok
> to change the age of a Person in the set. You are saying that it is
> ok to change the age of a Person const anywhere in this or other
> applications which use the Person class. Two very different things.
Yes, you are right, that's what I meant. Making age mutable breaks the
security of Person in general.
-Vahan
Vahan Margaryan
>
> A constant iterator returns a const T&, not a convertable to T. The
> cast must work and you know that it is safe.
>
> You may find the boost::projection iterator useful to hide the cast.
> I think it is a bit of an overkill.
>
> Yes, I understand your problem. Just offering a work around. I think
> the const_cast is the accepted way to make set useful for something
> more like a relational database than a set. No, I would not even
> think of suggesting that you split your class to use a map.
>
> John
Using a projection_iterator is probably really the best way to handle
this. We could mechanically change all set iterators to an appropriate
projection iterator, and thus immediately ensure portability. Writing
out dozens of const_casts is both harder and uglier... Thanks!
Still, it seems sad to me that what appears (to me) a common use of a
container isn't reflected in the standard in any way. Even a hidden
const_cast causes a sting of conscience about breaking the
standard-endorsed safety system :)
-Vahan.
Matthew Austern
> Still, it seems sad to me that what appears (to me) a common use of a
> container isn't reflected in the standard in any way. Even a hidden
> const_cast causes a sting of conscience about breaking the
> standard-endorsed safety system :)
The committee was aware that this decision made usages like that more
inconvenient. The trouble is, it's something that you really want to
be at least a little bit inconvenient. An error like
std::set<X> s;
...
std::reverse(s.begin(), s.end());
is the moral equivalent of a type error, and it should be caught at
compile time. So that suggests that users should be forced to do
*something* special if they want to modify a set element through a set
iterator.
Perhaps there should be a middle ground between the total lack of
safety that you get from std::set::iterator being mutable and the
inconvenience that you get now from having no provided mechanism other
than const_cast<>. I'm not sure what that middle ground might look
like, but, if someone provides one that's upward compatible with what
we've got now, I'm sure the committee will consider it.
Sergey P. Derevyago
> > Does the standard say that std::set::iterator and std::set::const_iterator are
> > the same types?
> No. It doesn't say one way or the other.
> > If not, then the definition of std::set is incorrect.
> It is known to be incorrect, and there is a defect report on it.
modification of keys" issue, isn't it?
> The
> resolution chosen by the LWG isn't quite to say that std::set::iterator
> and std::set::const_iterator must be the same type. It's to say that
> std::set::iterator is a constant iterator, and that it's unspecified
> whether or not the two iterators are the same type.
This resolution requires "214. set::find() missing const overload" issue.
While "std::set::iterator is std::set::const_iterator" does not.
So it seems like it was decided to patch the original STL design which has
only
iterator find(const key_type& x) const;
set member because set::iterator and set::const_iterator are the same types.
BTW from the conceptual point of view, set is map without mapped_type. But
map::value_type is pair<const Key, T> while set::value_type is just Key. IMHO
const Key as set::value_type would be more consistent.
Are there any reasons to define it as (plain) Key?
--
With all respect, Sergey. http://cpp3.virtualave.net/
mailto : ders at skeptik.net
---
Louis Lavery
John Potter <jpo...@falcon.lhup.edu> wrote in message
news:3c88ff4f...@news.earthlink.net...
> On Fri, 8 Mar 2002 16:34:38 GMT, mar...@yahoo.com (Vahan Margaryan)
> wrote:
>
> > Since the standard didn't take a stand on this, we felt safe to use
> > set iterators as non-constant. It makes sense, in situations like
> > this:
>
> > class Person {
> > public:
> > explicit Person(const string& s) : name_(s), age_(0){}
> > const string& name()const;
> >
> > bool operator<(const Person& rhs)const { return name_ < rhs.name_; }
> >
> > void age(int i);
> > int age()const;
> > private:
> > consistent
>
> Watch out for concept checking versions of the library. The value_type
> is not assignable and that is a requirement for all standard containers.
>
> > };
> >
> > set<Person> people;
> >
> > Now, lots of code has to be rewritten (even though it's conceptually
> > safe, like the one above).
>
> const_cast<Person&>(people.begin()).age(42);
>
> A constant iterator returns a const T&, not a convertable to T. The
> cast must work and you know that it is safe.
>
> You may find the boost::projection iterator useful to hide the cast.
> I think it is a bit of an overkill.
>
> Yes, I understand your problem. Just offering a work around. I think
> the const_cast is the accepted way to make set useful for something
> more like a relational database than a set. No, I would not even
> think of suggesting that you split your class to use a map.
>
> John
Surely all that's needed is to add replace functions to set, something
like...
pair<iterator,bool> replace(T const& t);
pair<iterator,bool> replace(T const& t,iterator hint);
Returns true if an equivalent t is found. The returned iterator points
to the original element that's now been overwritten by t (via assignment).
Otherwise returns false and an iterator to the element before which t
would be inserted.
...wouldn't this, together with the option of const_cast, satisfy all?
Louis.
Vahan Margaryan
>
> Surely all that's needed is to add replace functions to set, something
> like...
>
> pair<iterator,bool> replace(T const& t);
> pair<iterator,bool> replace(T const& t,iterator hint);
>
> Returns true if an equivalent t is found. The returned iterator points
> to the original element that's now been overwritten by t (via assignment).
>
> Otherwise returns false and an iterator to the element before which t
> would be inserted.
>
> ...wouldn't this, together with the option of const_cast, satisfy all?
>
> Louis.
Unfortunately, replace is, generally speaking, slower than
modification of a single data member through const-cast, because it
replaces the whole object.
There are even more special circumstances, where it makes sense to
modify the key-forming part of the object. It is known (from the
algorithm context) that the order of the objects won't change even
though the object is modified so as to change the key value. I agree
that this is a very dangerous case. In this case replace will just
return false.
So, const_cast remains the only practice in most cases...
-Vahan
John Potter
<Lo...@devilschimney.co.uk> wrote:
>
> Surely all that's needed is to add replace functions to set, something
> like...
>
> pair<iterator,bool> replace(T const& t);
> pair<iterator,bool> replace(T const& t,iterator hint);
>
> Returns true if an equivalent t is found. The returned iterator points
> to the original element that's now been overwritten by t (via assignment).
>
> Otherwise returns false and an iterator to the element before which t
> would be inserted.
>
> ...wouldn't this, together with the option of const_cast, satisfy all?
struct S { int key; int data; };
set<S> ss;
set<S>::iterator it;
We established the iterator and wish to change it->data.
Normal expected use:
S temp(*it);
ss.erase(it++);
temp.data = newValue;
ss.insert(it, temp);
With replace use:
S temp(*it);
temp.data = newValue;
ss.replace(it, temp);
With const_cast use:
const_cast<int&>(it->data) = newValue;
The first two have the copy out and copy in. The first adds the cost
of erase and insert. The worst case for the erase/insert is lgN, but
the average case is constant time.
I have suggested that insert be a replace when found. This or your
replace seems like a nice compromise; however, I no longer think that
it is worth any effort. The const_cast is the best that could be done
and both it and the erase/insert are supported.
Those who want speed can use const_cast. Those who want to feel clean
can use erase/insert. Those who want to feel clean half fast are
confused and likely few in number.
The nice thing about the const_cast is that it is a nop for strict
implementations and is a nop for those with an extension of iterator
returning a non-const reference. The code is totally portable.
John
John Potter
<aus...@research.att.com> wrote:
> Perhaps there should be a middle ground between the total lack of
> safety that you get from std::set::iterator being mutable and the
> inconvenience that you get now from having no provided mechanism other
> than const_cast<>. I'm not sure what that middle ground might look
> like, but, if someone provides one that's upward compatible with what
> we've got now, I'm sure the committee will consider it.
I've played with this problem for many years trying to find the ideal
interface. I think that the committee made an excellent compromise
for a safe container with intelligent access still available. The
library should be usable by Murphy and others, and it is.
John
John Potter
<non-ex...@iobox.com> wrote:
> BTW from the conceptual point of view, set is map without mapped_type.
> But map::value_type is pair<const Key, T> while set::value_type is
> just Key. IMHO const Key as set::value_type would be more consistent.
The map value_type is inconsistent with the container requirements
that value_type be assignable. No need to break set also. Note also
that there is no difference between iterator::value_type and
const_iterator::value_type for any container.
> Are there any reasons to define it as (plain) Key?
template <class Iter>
void whatever (Iter it) {
iterator_traits<Iter>::value_type temp;
That is an error.
John
Sergey P. Derevyago
> > BTW from the conceptual point of view, set is map without mapped_type.
> > But map::value_type is pair<const Key, T> while set::value_type is
> > just Key. IMHO const Key as set::value_type would be more consistent.
> The map value_type is inconsistent with the container requirements
> that value_type be assignable.
:) Container and Associative Container are quite different beasts so
non-assignable value_types are OK (but see below).
> > Are there any reasons to define it as (plain) Key?
> template <class Iter>
> void whatever (Iter it) {
> iterator_traits<Iter>::value_type temp;
>
> That is an error.
IMHO it's a STL design flaw: (const_)iterators of Containers and Associative
Containers must be separated.
They clearly differs just like Cont::value_type is a "plain value" while
AssocCont::value_type is a pair of ("key", "plain value").
--
With all respect, Sergey. http://cpp3.virtualave.net/
mailto : ders at skeptik.net
---
John Potter
<non-ex...@iobox.com> wrote:
> John Potter wrote:
> > > BTW from the conceptual point of view, set is map without mapped_type.
> > > But map::value_type is pair<const Key, T> while set::value_type is
> > > just Key. IMHO const Key as set::value_type would be more consistent.
> > The map value_type is inconsistent with the container requirements
> > that value_type be assignable.
> While map is consistent with the "Sorted Associative Container" requirements
> :) Container and Associative Container are quite different beasts so
> non-assignable value_types are OK (but see below).
I think we have confused terms. The standard has containers and their
requirements. There are two types of containers, sequences and
associatives. Assignable is a requirement for all containers. The
standard does not talk about array based and node based containers. You
might say, and I might agree, that there is no need for assignable in
the node based containers, associatives and list. That does not change
the fact that the standard requires assignable for all containers.
> > > Are there any reasons to define it as (plain) Key?
> > template <class Iter>
> > void whatever (Iter it) {
> > iterator_traits<Iter>::value_type temp;
> >
> > That is an error.
> IMHO it's a STL design flaw: (const_)iterators of Containers and Associative
> Containers must be separated.
Do you mean sequences and associatives? What about list? Should all
associatives be the same? Should map::iterator be a constant iterator
like set?
> They clearly differs just like Cont::value_type is a "plain value" while
> AssocCont::value_type is a pair of ("key", "plain value").
Set is an associative and its value_type is not a pair. Should it be
pair<const key, empty>?
IMO, map::value_type should be pair<key, value> and
map::iterator::reference should be pair<key const, value>&.
pair<T, U> p;
pair<T const, U>& r = reinterpret_cast<pair<T const, U>&>(p);
is valid but, must it do the right thing? Should it be a valid
static_cast?
What affect does this all have on algorithms which is the only reason
that the containers exist?
John
Sergey P. Derevyago
> > While map is consistent with the "Sorted Associative Container" requirements
> > :) Container and Associative Container are quite different beasts so
> > non-assignable value_types are OK (but see below).
> I think we have confused terms.
> The standard has containers and their
> requirements. There are two types of containers, sequences and
> associatives. Assignable is a requirement for all containers.
And the standard is clearly inconsistent here.
> The
> standard does not talk about array based and node based containers. You
> might say, and I might agree, that there is no need for assignable in
> the node based containers, associatives and list.
Not exact. std::list is a container and it's OK. But map is associative
container:
container : element is T
associative container: element is T with associated Key
From the conceptual point of view, Key is a part of container itself (kind of
a hidden link next in a list node). So we're not allowed to directly modify
the internals of container (Key), just like we can do with its data (T).
And in order to support this concept, we should define new class: "iterator to
associative container elements", which knows about keys and values. It'll be
modifiable w.r.t. data (T), if any, and constant w.r.t. internals (Key).
> That does not change
> the fact that the standard requires assignable for all containers.
>
> > > > Are there any reasons to define it as (plain) Key?
> > > template <class Iter>
> > > void whatever (Iter it) {
> > > iterator_traits<Iter>::value_type temp;
> > >
> > > That is an error.
> > IMHO it's a STL design flaw: (const_)iterators of Containers and Associative
> > Containers must be separated.
> Do you mean sequences and associatives? What about list?
list is a sequence.
> Should all associatives be the same?
No. Some of them don't have mapped_type (they contain only immutable Keys).
> Should map::iterator be a constant iterator like set?
It should be an "iterator of associative container".
> > They clearly differs just like Cont::value_type is a "plain value" while
> > AssocCont::value_type is a pair of ("key", "plain value").
> Set is an associative and its value_type is not a pair. Should it be
> pair<const key, empty>?
No. And I'm not quite sure that pair<> is really needed here at all.
PS And it's obvious that such global modifications (as iterator of associative
container) are not acceptable for STL :(
--
With all respect, Sergey. http://cpp3.virtualave.net/
mailto : ders at skeptik.net
---