set::iterators same as set::const_iterator?
Martin Fabian
std::set::iterator being typedef'ed from a const_iterator (and before I
noticed that typedef I did waste some time!)
Now, looking at the standard, I can find no requirement for std::set to
only return const_iterators. In fact, iterators are "implementation
defined" ($23.3.3) and "iterator of an associative container is of the
bidirectional iterator category" ($23.1.2.6). The only thing I can find
is that the writing that lower_bound returns iterator for a non-const
set implies that iterator is different from const_iterator. SGI's
stl-page states this explicitly, saying that a.lower_bound(k) returns
"iterator if a is mutable, otherwise const_iterator" for a Sorted
Associative Container.
What gives, really?
--
Martin Fabian http://www.s2.chalmers.se/~fabian/
--
Ask enough experts. Eventually you'll get the answer you want.
/* Remove NOSPAM from reply-to address to mail me */
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]
Tom
<fabian...@s2.chalmers.se> wrote:
>I've switched to StlPort4 and was suddenly bitten by the
>std::set::iterator being typedef'ed from a const_iterator (and before I
>noticed that typedef I did waste some time!)
>
>Now, looking at the standard, I can find no requirement for std::set to
>only return const_iterators. In fact, iterators are "implementation
>defined" ($23.3.3) and "iterator of an associative container is of the
>bidirectional iterator category" ($23.1.2.6). The only thing I can find
>is that the writing that lower_bound returns iterator for a non-const
>set implies that iterator is different from const_iterator. SGI's
>stl-page states this explicitly, saying that a.lower_bound(k) returns
>"iterator if a is mutable, otherwise const_iterator" for a Sorted
>Associative Container.
>
>What gives, really?
http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#103
Since iterators for sets should really be immutable to stop the user
from being able to mess up the ordering, typedeffing iterator as a
const iterator will be conforming but is not required, assuming the DR
goes through. Currently I think STLport is non-conforming in the
strict sense of the word.
Tom
John Potter
<fabian...@s2.chalmers.se> wrote:
> I've switched to StlPort4 and was suddenly bitten by the
> std::set::iterator being typedef'ed from a const_iterator (and before I
> noticed that typedef I did waste some time!)
>
> What gives, really?
See LWG issue 103. Set iterator and const_iterator need not be the
same type; however, they must both be constant iterators. Constant
iterators are not mutable iterators. Operator* yields a const
reference.
John
Peter Dimov
news:39f880e0...@news.csrlink.net...
>
> See LWG issue 103. Set iterator and const_iterator need not be the
> same type; however, they must both be constant iterators. Constant
> iterators are not mutable iterators. Operator* yields a const
> reference.
Which means that we have to either declare everything but the key
mutable, or not use std::set at all.
Such is life.
--
Peter Dimov
Multi Media Ltd.
John Potter
> "John Potter" <jpo...@falcon.lhup.edu> wrote in message
> news:39f880e0...@news.csrlink.net...
> >
> > See LWG issue 103. Set iterator and const_iterator need not be the
> > same type; however, they must both be constant iterators. Constant
> > iterators are not mutable iterators. Operator* yields a const
> > reference.
>
> Which means that we have to either declare everything but the key
> mutable, or not use std::set at all.
I don't think those are the only options. The value_type is not const
and we have a const_reference to it. This is a case where we know
that const_cast is well defined. I think that the resolution of
issue 103 is the best of all worlds. With constant iterators, there
is no chance to accidently change the key and it is still possible
to make intelligent use of const_cast to change other fields. It
also requires knowing that the set is not const; however, a const
set is a rare thing.
It is also possible to use copy out, erase, modify, insert. Update
in place is an optimization and const_cast is justified when needed.
The problem of having a container which safely maintains its order
and allows efficient updates is a hard problem. I have looked at
it for years and the standard solution is as good as any other that
I have seen.
John
Peter Dimov
[...]
> I don't think those are the only options. The value_type is not const
> and we have a const_reference to it. This is a case where we know
> that const_cast is well defined.
Yes, I overlooked that possibility (const_cast firmly in the 'evil'
category in my mind.)
But this leads to an interesting question. Is it guaranteed that the
std::set stores non-const values? It certainly is possible to implement
a set that stores "value_type const"'s - since std::map does store
non-assignables.
Also note that std::set::iterator being a constant iterator (in the
24.1/4 sense) means that we don't even have a reference to the element.
--
Peter Dimov
Multi Media Ltd.
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
John Potter
> "John Potter" <jpo...@falcon.lhup.edu> wrote in message
> news:39fabc55...@news.csrlink.net...
>
> [...]
>
> > I don't think those are the only options. The value_type is not const
> > and we have a const_reference to it. This is a case where we know
> > that const_cast is well defined.
>
> Yes, I overlooked that possibility (const_cast firmly in the 'evil'
> category in my mind.)
It's in the practical category in my mind. Consider the recommended
way of writing the non-const member in terms of the const member.
> But this leads to an interesting question. Is it guaranteed that the
> std::set stores non-const values? It certainly is possible to implement
> a set that stores "value_type const"'s - since std::map does store
> non-assignables.
Value_type for containers must be assignable. Std::map::value_type is
not assignable. Std::map is not a container. Nobody wants to write
that DR.
> Also note that std::set::iterator being a constant iterator (in the
> 24.1/4 sense) means that we don't even have a reference to the element.
24.1/4 is self contradictory. The first sentence says that *it is a
reference to const. References are lvalues. The second sentence
says that it can't be used as an lvalue. Nobody wants to talk about
that DR either.
Since this is clc++m not csc++, I will take a pragmatic approach. In
either case I will cast away the const and know that it will work.
They are node based containers and a new some_struct with a const
member will be modifiable. Implementers are not out to get me, they
are out to make usable libraries.
See also: the October CUJ Experts article on creating an iterator to
hide the const_cast which I prefer to keep visable. It is the accepted
solution to the old problem of set members being const and map spliting
the object into disjoint pieces.
John
pdi...@techno-link.com
jpo...@falcon.lhup.edu (John Potter) wrote:
> Value_type for containers must be assignable. Std::map::value_type is
> not assignable. Std::map is not a container. Nobody wants to write
> that DR.
I'm not talking about the value_type. std::set::value_type is non-
const. However, the set can internally store "value_type const" in the
nodes; we have no way to find out.
> > Also note that std::set::iterator being a constant iterator (in the
> > 24.1/4 sense) means that we don't even have a reference to the
element.
>
> 24.1/4 is self contradictory. The first sentence says that *it is a
> reference to const. References are lvalues. The second sentence
> says that it can't be used as an lvalue. Nobody wants to talk about
> that DR either.
No, it's not. It says, in effect: *it returns either value_type &,
value_type const &, or value_type const.
If you're not allowed to use lvalue operations, you can't distinguish
the last two cases.
Although you may well consider writing that DR. :-)
--
Peter Dimov
Multi Media Ltd.
Sent via Deja.com http://www.deja.com/
Before you buy.
John Potter
> In article <39fe3ca3...@news.csrlink.net>,
> jpo...@falcon.lhup.edu (John Potter) wrote:
>
> > > Also note that std::set::iterator being a constant iterator (in the
> > > 24.1/4 sense) means that we don't even have a reference to the
> element.
> >
> > 24.1/4 is self contradictory. The first sentence says that *it is a
> > reference to const. References are lvalues. The second sentence
> > says that it can't be used as an lvalue. Nobody wants to talk about
> > that DR either.
>
> No, it's not. It says, in effect: *it returns either value_type &,
> value_type const &, or value_type const.
I assume that the first of those was intended to be value_type (no &)
as three possible types for *it for a constant iterator.
Please do not talk about "effect". It says it behaves as a reference
to const (period). It does not say it behaves as a convertable to
T as it does for input iterator. The standard is very clear about
saying reference to const or convertable to T. They have very
different meanings.
> If you're not allowed to use lvalue operations, you can't distinguish
> the last two cases.
I can distinguish the three cases by trying to use it as an lvalue.
T const* p = &*it;
I can bind a temporary rvalue to a const reference, but I can not take
its address. If it behaves as a reference to const, I can take its
address.
The second sentence is missing the word "modifiable" in front of lvalue.
It is easy to forget that there are two kinds of lvalues in C++. Insert
that word and it is consistent with everything else.
> Although you may well consider writing that DR. :-)
I did and prudently posted the question to csc++ first. No response.
Since there are always those willing to tell me that my opinion is
wrong for obvious reasons and nobody did, I conclude that nobody
wants to talk about it.
Here is another problem that I can't merge with your opinion.
set<pair<int,int> > s;
...
set<pair<int,int> >::iterator it;
cout << (*it).second << ' ' << it->second << '\n';
set<pair<int,int> >::iterator::pointer p = it.operator->();
cout << (*p).second << ' ' << p->second << '\n';
John
pdi...@techno-link.com
jpo...@falcon.lhup.edu (John Potter) wrote:
> On 1 Nov 2000 11:46:39 -0500, pdi...@techno-link.com wrote:
>
> > In article <39fe3ca3...@news.csrlink.net>,
> > jpo...@falcon.lhup.edu (John Potter) wrote:
> >
[...]
> > No, it's not. It says, in effect: *it returns either value_type &,
> > value_type const &, or value_type const.
>
> I assume that the first of those was intended to be value_type (no &)
> as three possible types for *it for a constant iterator.
No. value_type & is the only possible type for *it for a non-constant
iterator.
> Please do not talk about "effect". It says it behaves as a reference
> to const (period).
Right. 24.1/4 says:
-- *it for mutable it behaves as a reference to value_type;
-- *it for constant it behaves as a const reference to value_type,
except no lvalue operations are allowed on it.
Given that in the example
template<class T> void f(T & t);
f(*it);
the only return type for *it that behaves as value_type & is value_type
&, and the only return types that behave as value_type const & are
value_type const & and value_type const, I conclude that these three
are the only candidates.
Further, without using lvalue operations on *it (forbidden by the
second sentence) I cannot imagine an example that may disambiguate
between value_type const & and value_type const.
This is my interpretation of 24.1/4.
> I can distinguish the three cases by trying to use it as an lvalue.
> T const* p = &*it;
Except that you're not allowed to do that.
> I can bind a temporary rvalue to a const reference, but I can not take
> its address.
Yes, this is the only example I can think of that distinguishes the two
possibilities:
value_type const & v = *it;
// modify *it through a non-constant alias and look whether v changes.
> If it behaves as a reference to const, I can take its
> address.
No, you can't, not in this version of 24.1/4; the second sentence
imposes additional requirements on *it; it behaves as a const reference
only with non-lvalue operations.
> The second sentence is missing the word "modifiable" in front of
> lvalue.
> It is easy to forget that there are two kinds of lvalues in C++.
> Insert
> that word and it is consistent with everything else.
Perhaps. It may be speculated that 24.1/4 does not say exactly what the
authors wanted to say; I think that the odd "behaves as" language is a
(failed) attempt to legalize vector<bool>::iterator.
But it does have a valid interpretation in its current form.
> > Although you may well consider writing that DR. :-)
>
> I did and prudently posted the question to csc++ first. No response.
Yes, I saw this post and waited for the more knowledgeable among us to
answer, too. A full-blown DR is less easier to ignore, though. :-)
> Here is another problem that I can't merge with your opinion.
>
> set<pair<int,int> > s;
> ...
> set<pair<int,int> >::iterator it;
> cout << (*it).second << ' ' << it->second << '\n';
> set<pair<int,int> >::iterator::pointer p = it.operator->();
> cout << (*p).second << ' ' << p->second << '\n';
If I read you correctly, you're giving an example of a
conforming "backdoor use" of *it as an lvalue, because operator->()
should return &*it, right?
I think that this example will fit nicely in the defect report.
Note that the above is not "my opinion." It is my interpretation of the
current version of 24.1/4. My opinions are non-normative. :-)
--
Peter Dimov
Multi Media Ltd.
Sent via Deja.com http://www.deja.com/
Before you buy.
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Peter Dimov
> On 2 Nov 2000 21:01:54 -0500, pdi...@techno-link.com wrote:
>
> > In article <3a00e04c...@news.csrlink.net>,
> > jpo...@falcon.lhup.edu (John Potter) wrote:
>
> > 24.1/4 says:
> >
> > -- *it for mutable it behaves as a reference to value_type;
> > -- *it for constant it behaves as a const reference to value_type,
> > except no lvalue operations are allowed on it.
>
> used a comma above where the standard uses a period. I read the
> second sentence as a new subject which says that constant iterators
> may not be used where an output iterator is required because *it
> may not be used where a (mutable) lvalue is required.
Yes, I see, but note that you are introducing the concept of output
iterator
and the (mutable) in front of lvalue that are not present in the original
text. Your interpretation may be closer to what the authors intended to
say,
but I believe that mine is closer to what they actually said.
> Actually, operator*() should return *operator->(), but operator* was
> there long before operator-> was widely available. Any attempt to write
> an iterator for which operator* does not return a reference ends up
> with a broken operator->.
That's the same thing. The equation operator*() == *operator->() should be
equivalent to &operator*() == operator->(); although I note that your
version cleverly avoids using *it as an lvalue. :-)
In any event, I think that we have reached an agreement that this is a DR
material. I haven't considered operator-> in my analysis.
> > Which means that we have to either declare everything but the key
> > mutable, or not use std::set at all.
>
> I overlooked that we are obviously in violent agreement. Making
> everything mutable will not help if operator* does not return a
> reference.
Indeed. If there's something to be made mutable, it can be accessed via
op->, that is guaranteed to return a pointer and can be const_cast'ed. It
would be good for the standard to actually guarantee that the const_cast in
this case be legal, but in c.l.c++.m, we can safely assume that it is.
--
Peter Dimov
Multi Media Ltd.
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
John Potter
> In article <3a00e04c...@news.csrlink.net>,
> jpo...@falcon.lhup.edu (John Potter) wrote:
> 24.1/4 says:
>
> -- *it for mutable it behaves as a reference to value_type;
> -- *it for constant it behaves as a const reference to value_type,
> except no lvalue operations are allowed on it.
I understand your view, but read it differently. Note that you have
used a comma above where the standard uses a period. I read the
second sentence as a new subject which says that constant iterators
may not be used where an output iterator is required because *it
may not be used where a (mutable) lvalue is required.
> > Here is another problem that I can't merge with your opinion.
> >
> > set<pair<int,int> > s;
> > ...
> > set<pair<int,int> >::iterator it;
> > cout << (*it).second << ' ' << it->second << '\n';
> > set<pair<int,int> >::iterator::pointer p = it.operator->();
> > cout << (*p).second << ' ' << p->second << '\n';
>
> If I read you correctly, you're giving an example of a
> conforming "backdoor use" of *it as an lvalue, because operator->()
> should return &*it, right?
Actually, operator*() should return *operator->(), but operator* was
there long before operator-> was widely available. Any attempt to write
an iterator for which operator* does not return a reference ends up
with a broken operator->.
> Note that the above is not "my opinion." It is my interpretation of the
> current version of 24.1/4. My opinions are non-normative. :-)
As are your interpretations ;-)
On 28 Oct 2000 00:01:47 -0400, "Peter Dimov" <pdi...@mmltd.net> wrote:
> Which means that we have to either declare everything but the key
> mutable, or not use std::set at all.
I overlooked that we are obviously in violent agreement. Making
everything mutable will not help if operator* does not return a
reference.
Off to write that DR.
John
John Potter
> "John Potter" <jpo...@falcon.lhup.edu> wrote in message
> news:3a029162...@news.csrlink.net...
> > I understand your view, but read it differently. Note that you have
> > used a comma above where the standard uses a period. I read the
> > second sentence as a new subject which says that constant iterators
> > may not be used where an output iterator is required because *it
> > may not be used where a (mutable) lvalue is required.
>
> Yes, I see, but note that you are introducing the concept of output
> iterator
??????
> and the (mutable) in front of lvalue that are not present in the original
> text. Your interpretation may be closer to what the authors intended to
> say,
> but I believe that mine is closer to what they actually said.
Maybe we are not reading the same document. I am looking at the pdf
standard. Are you reading a draft or has the TC changed it? Here is
what I see for the second sentence.
Constant iterators do not satisfy the requirements for output
iterators, and the result of the expression *i (for constant
iterator i) cannot be used in an expression where an lvalue
is required.
The output iterator was there. I should have used "modifiable" for
the single word to be added. I read the "and" as "because".
Since two apparantly rational people can disagree on the meaning,
it at least requires amplification.
Peter Dimov
> On 3 Nov 2000 16:10:34 -0500, "Peter Dimov" <pdi...@mmltd.net> wrote:
>
> > Yes, I see, but note that you are introducing the concept of output
> > iterator
>
> ??????
A reasonable response. My mistake. Sorry about that.
> Constant iterators do not satisfy the requirements for output
> iterators, and the result of the expression *i (for constant
> iterator i) cannot be used in an expression where an lvalue
> is required.
>
> The output iterator was there. I should have used "modifiable" for
> the single word to be added. I read the "and" as "because".
I would have read it the same way, but I remember posts on c.s.c++ (by
people that obviously knew their stuff) that asserted that
&*v.begin()
is not the same as
&v[0]
for a constant vector v, citing the 'no lvalue operations' rule.
--
Peter Dimov
Multi Media Ltd.
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]