Sam Lindley wrote:

> > > The
> > > proposed resolution to this issue does not mention the lack of const and
> > > non-const versions of find(), lower_bound(), upper_bound(), and
> > > equal_range(). Do we need a separate defect report for this?
> >
> > I don't see how it is usefull to garanty that there are
> > two find functions in set, one const and one non const.
> >
> > All I want is that:
> > 1) the const find function in set returns a const_iterator
> > 2) the find function in set returns an iterator
> > ...and this is already garantied by the table Associative container
> > requirements.
>
> and contradicted by the definition of set (unless you assume a
> const_iterator is an iterator).

Then the definition of set could say so (that there is
only one iterator type) explicitly.

> > I don't care how many different find functions I have.
>
> What you're getting at is that set::iterator, and set::const_iterator may be
> identical?

No one said the contrary

> I don't care how these requirements are expressed, provided they
> are consistent throughout the whole standard. However, the way in which most
> of the standard seems to be written, is such that the types of member
> functions are usually defined explicitly, in addition to auxilliary
> requirements (though types are often implementation-defined).

iterator types are always implementation defined (except the
reverse iterators)

> > To summarise, all we need to say is that set<T>::value_type
> > is const T.
>
> I agree. However, this appears to be contrary to the conclusions of:
>
> http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#103
>
> however. This doesn't seem particularly clear to me, but I'd be interested
> to see a concrete example to demonstrate why it might be useful to allow
> mutable keys.
>
> My reasons for wanting an immutable key_type:

[ Fine, but they aren't needed. ]

The conclusion is silly. Historical and current practice
is that the key is const. It's what all textbooks say,
what the SGI doc says and does. It's the intent of almost
the entire committee. It's merelly an accident if the
standard doesn't say so.

The fix is obviously to make the standard match intent,
original STL, current practice, textbooks, proogrammer's
expectation, and committee members' expectation .

--

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

Valentin Bonnard <Bonnard.V@wanadoo.fr> writes:

> The conclusion is silly. Historical and current practice
> is that the key is const. It's what all textbooks say,
> what the SGI doc says and does. It's the intent of almost
> the entire committee. It's merelly an accident if the
> standard doesn't say so.
>
> The fix is obviously to make the standard match intent,
> original STL, current practice, textbooks, proogrammer's
> expectation, and committee members' expectation .

I happen to agree with your proposed fix, but not all implementations,
or all committee members, agree with us.  Sensible people have
proposed the opposite fix: requiring that set<>::const_iterator
be an unmodifiable iterator and that set<>::iterator be a modifiable
iterator.

(Please, let's not turn this into another thread like the one about
deleting const pointers!)




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

"Sam Lindley" <sam@redsnapper.net> writes:

> > > Also, I noticed that value_type for map and multimap is
> > > pair<const K, T>, which makes sense, but the iterator requirements are
> > > written in terms of T, not value_type.
> >
> > I don't see any problems there.
> >
> > To summarise, all we need to say is that set<T>::value_type
> > is const T.
>
> I agree. However, this appears to be contrary to the conclusions of:
>
> http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#103
>
> however. This doesn't seem particularly clear to me, but I'd be interested
> to see a concrete example to demonstrate why it might be useful to allow
> mutable keys.

There are no conclusions.  There's a proposed resolution, which is not
at all the same thing.  (Whoever submits an issue may propose a
resolution.)

Everyone on the library working group agrees that this part of the
standard is defective, and that the standard should be clarified so
that we can tell whether set<>::iterator is a mutable or an immutable
iterator, and whether set<>::iterator and set<>::const_iterator are
required to be the same type, or required to be different types, or
permitted to be either the same or different types.  There is
disagreement within the library working group about which choice is
better.  Existing implementations differ.



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

Sam Lindley <sam@redsnapper.net> wrote in message
news:7tbd7b$14a$1@plutonium.btinternet.com...
>
> > To summarise, all we need to say is that set<T>::value_type
> > is const T.
>
> I agree. However, this appears to be contrary to the conclusions of:
>
> http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#103
>
> however. This doesn't seem particularly clear to me, but I'd be interested
> to see a concrete example to demonstrate why it might be useful to allow
> mutable keys.

I encountered a real-world use for mutable keys when writing a high-speed
database engine a while back.  Basically, each index of a table looked like
this:

std::set<Row*, SortingPredicate> index;

The tricky operation is updating a row atomically (the row must be
completely updated or left in its former state).  If an indexed field gets
changed, it would violate the ordering of the index.  However, simply doing
an {erase, insert} combination to update the index isn't safe, because if
there is insufficient memory for the insert, there is no guarantee of
restoring the old state of the table.

So the order had to be {insert, erase}.  To make the set valid for the
insert, I set the old index element to be equal to an adjacent element.
(This is the safe mutation.)  Then I inserted the new index element.
Finally, I could erase the old index element.

Of course, there are lots more details, but this shows how mutable keys
played their part.  Note, too, that this is not some pathological case:
This database resides in memory only until persisted (just like your average
text document).  The index is used to identify rows to persist (for speed
reasons) and must correctly contain at least the old value of the row
following an out of memory condition.
---
[ 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 <7tbd7b$14a$1@plutonium.btinternet.com>,
  "Sam Lindley" <sam@redsnapper.net> wrote:
> This doesn't seem particularly clear to me, but I'd be interested
> to see a concrete example to demonstrate why it might be useful to
allow
> mutable keys.

BEGIN EXAMPLE

class customer
{
public:
  customer(const std::string& nm) : name_(nm), sentBrochure_(false) { }
  std::string name() const { return name_; }
  void sendBrochure() { sentBrochure_ = true; /* ... */ }
  bool sentBrochure() const { return sentBrochure_; }
private:
  std::string name_;
  bool sentBrochure_;
};

// less-than op only compares names
inline bool operator< (const customer& c1, const customer& c2)
  { return c1.name() < c2.name(); }

// Function f modifies cust
void f(customer& cust)
{
  if (cust.sentBrochure() == false && someOtherCondition())
    cust.sendBrochure();
}

std::set<customer> customerList;

for (std::set<customer>::iterator i = customerList.begin();
     i != customerList.end(); ++i)
  f(*i);   // Only works if *i is non-const

END EXAMPLE

The final statement simply passes the customer object to a function
that knows nothing about the customerList set. However, f() doesn't do
anything to the object that would change its position in the sort order.
The f() function does not *always* modify its argument, so erasing and
re-inserting the element every time we call f() would be inefficient,
especially if customer were expensive to copy.

>
> My reasons for wanting an immutable key_type:
>
> 1) If set<T>::key_type is mutable, why shouldn't map<T>::key_type be?

Because map separates the key from the content. If the key is
integrally connected to the content, as in the customer class above,
then a set with mutable elements is more appropriate, to avoid
duplicating the key.

> 2) The benefits of allowing mutable keys are far out-weighed by the
> disadvantages.

I dissagree. There are few advantages to having immutable keys. It is
not sufficient to prevent errors, because the key might be a pointer,
in which case the pointed-to object can be modified. Alternatively, the
key could have mutable members that allow breaking the sort order. The
correct solution is to require that the user of set not do anything
that breaks the sort order, without trying to stop him/her by
handicapping the iterator. See Herb Sutter's artical in the October
1999 C++ Report.

> 3) Modification is easy to simulate, anyway: erase() followed by
insert().

Easy but sometimes expensive. And it can break modularity by requiring
the pushing the modification regime on to the user of the set instead
of concentrating that information in the element type. It also can
break identity, if an object's address (or an iterator pointing to the
object) is used elsewhere in the program.

> 4) Other associative containers (useful ones at that - e.g. SGI's
hash_set,
> hash_map, etc.), have no natural way of allowing keys to be modified
(apart
> from 3)).

Nonsense. They could be modified to have the same restrictions/non-
restrictions as the standard types. If you allow an element to be
modified, you tell the user that he/she must not modify the the object
in such a way that its hash value would change.


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              ]

> > however. This doesn't seem particularly clear to me, but I'd be
interested
> > to see a concrete example to demonstrate why it might be useful to allow
> > mutable keys.
>
> I encountered a real-world use for mutable keys when writing a high-speed
> database engine a while back.  Basically, each index of a table looked
like
> this:
>
> std::set<Row*, SortingPredicate> index;
>
> The tricky operation is updating a row atomically (the row must be
> completely updated or left in its former state).  If an indexed field gets
> changed, it would violate the ordering of the index.  However, simply
doing
> an {erase, insert} combination to update the index isn't safe, because if
> there is insufficient memory for the insert, there is no guarantee of
> restoring the old state of the table.

True.

> So the order had to be {insert, erase}.  To make the set valid for the
> insert, I set the old index element to be equal to an adjacent element.
> (This is the safe mutation.)  Then I inserted the new index element.
> Finally, I could erase the old index element.
>
> Of course, there are lots more details, but this shows how mutable keys
> played their part.  Note, too, that this is not some pathological case:
> This database resides in memory only until persisted (just like your
average
> text document).  The index is used to identify rows to persist (for speed
> reasons) and must correctly contain at least the old value of the row
> following an out of memory condition.

Nice example.

There are other solutions to that problem... (often less elegant /
efficient, though).

Is this sort of situation general enough to justify mutable keys for
standard sets?

Are the issues the same for maps?

Is there a neat way of providing public access to some degree of mutability,
without exposing it to unwitting abuse?

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

> > The
> > proposed resolution to this issue does not mention the lack of const and
> > non-const versions of find(), lower_bound(), upper_bound(), and
> > equal_range(). Do we need a separate defect report for this?
>
> I don't see how it is usefull to garanty that there are
> two find functions in set, one const and one non const.
>
> All I want is that:
> 1) the const find function in set returns a const_iterator
> 2) the find function in set returns an iterator
> ...and this is already garantied by the table Associative container
> requirements.

and contradicted by the definition of set (unless you assume a
const_iterator is an iterator).

> I don't care how many different find functions I have.

What you're getting at is that set::iterator, and set::const_iterator may be
identical? I don't care how these requirements are expressed, provided they
are consistent throughout the whole standard. However, the way in which most
of the standard seems to be written, is such that the types of member
functions are usually defined explicitly, in addition to auxilliary
requirements (though types are often implementation-defined).

> > Also, I noticed that value_type for map and multimap is
> > pair<const K, T>, which makes sense, but the iterator requirements are
> > written in terms of T, not value_type.
>
> I don't see any problems there.
>
> To summarise, all we need to say is that set<T>::value_type
> is const T.

I agree. However, this appears to be contrary to the conclusions of:

http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#103

however. This doesn't seem particularly clear to me, but I'd be interested
to see a concrete example to demonstrate why it might be useful to allow
mutable keys.

My reasons for wanting an immutable key_type:

1) If set<T>::key_type is mutable, why shouldn't map<T>::key_type be?
2) The benefits of allowing mutable keys are far out-weighed by the
disadvantages.
3) Modification is easy to simulate, anyway: erase() followed by insert().
4) Other associative containers (useful ones at that - e.g. SGI's hash_set,
hash_map, etc.), have no natural way of allowing keys to be modified (apart
from 3)).

Sam Lindley



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

Pablo Halpern wrote:

> hinnant@anti-spam_metrowerks.com (Howard Hinnant) wrote:

> >The C++ committee is considering this issue:
> >
> >http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#103
>
> Thanks for the pointer. It is a good Web page to know about.

Indeed !

> The
> proposed resolution to this issue does not mention the lack of const and
> non-const versions of find(), lower_bound(), upper_bound(), and
> equal_range(). Do we need a separate defect report for this?

I don't see how it is usefull to garanty that there are
two find functions in set, one const and one non const.

All I want is that:
1) the const find function in set returns a const_iterator
2) the find function in set returns an iterator
...and this is already garantied by the table Associative container
requirements.

I don't care how many different find functions I have.

> Also, I noticed that value_type for map and multimap is
> pair<const K, T>, which makes sense, but the iterator requirements are
> written in terms of T, not value_type.

I don't see any problems there.

To summarise, all we need to say is that set<T>::value_type
is const T.

--

Valentin Bonnard


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

hinnant@anti-spam_metrowerks.com (Howard Hinnant) wrote:

>In article <37f282fd.289638508@news.internetconnect.com>,
>phalpern@newview.org (Pablo Halpern) wrote:
>
>> Section 23.3.3 lists the following member function for set<Key>:
>>
>>         iterator find(const key_type& x) const;
>>
>> In other words, it returns a non-const iterator from a const function.

[ deletia ]

>> It is a common understanding that you cannot modify a set element
>> through its iterator, but I can't find that written anywhere, including
>> in the standard. Indeed, Herb Sutter writes in the October 1999 issue of
>> __The C++ Report__ that you *can* modify a set element through its an
>> iterator, provided you don't do anything that will change its position
>> in the set.

[ more deletia ]

>The C++ committee is considering this issue:
>
>http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#103

Thanks for the pointer. It is a good Web page to know about. The
proposed resolution to this issue does not mention the lack of const and
non-const versions of find(), lower_bound(), upper_bound(), and
equal_range(). Do we need a separate defect report for this?

Also, I noticed that value_type for map and multimap is
pair<const K, T>, which makes sense, but the iterator requirements are
written in terms of T, not value_type. The requirements would imply that
map iterators point to objects of type T, when we all know they actually
point to objects of type value_type. Should I file a defect report? How
would I do that?

-------------------------------------------------------------
Pablo Halpern                            phalpern@newview.org

I am self-employed. Therefore, my opinions *do* represent
those of my employer.


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

Valentin Bonnard wrote:
>
> James Kuyper wrote:
>
> > Sam Lindley wrote:
> > ...
> > > According to table 65 of the standard, a set<char>::iterator should be
> > > convertible to a set<char>::const_iterator. Does this mean conversion should
> > > be implicit? If so, why does the above code not work? Surely we should
> >
> > I believe that an 'explicit' conversion constructor would meet that
> > requirement. Many people have disagreed with me on that, but I've never
> > seen any citations from the standard to support their point of view.
>
> The standard doesn't have to say so explicitely. Every one
> knows that this is incorrect (ie convertable means implicitly
> convertable).

Not true. There's at least one person who doesn't know that it's
incorrect - me.


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

James Kuyper wrote:

> Sam Lindley wrote:
> ...
> > According to table 65 of the standard, a set<char>::iterator should be
> > convertible to a set<char>::const_iterator. Does this mean conversion should
> > be implicit? If so, why does the above code not work? Surely we should
>
> I believe that an 'explicit' conversion constructor would meet that
> requirement. Many people have disagreed with me on that, but I've never
> seen any citations from the standard to support their point of view.

The standard doesn't have to say so explicitely. Every one
knows that this is incorrect (ie convertable means implicitly
convertable).

--

Valentin Bonnard


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

Sam Lindley wrote:

> bool contains(const set<char>& s, char c)
> {
> return (s.find(c) != s.end());
> }

> According to table 65 of the standard, a set<char>::iterator should be
> convertible to a set<char>::const_iterator.

Yes

> Does this mean conversion should
> be implicit?

Yes

> If so, why does the above code not work?

'cause the standard never says that it has to work.

(You are free to complain about that fact.)

--

Valentin Bonnard


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

James Kuyper wrote:

> Valentin Bonnard wrote:

> > The standard doesn't have to say so explicitely. Every one
> > knows that this is incorrect (ie convertable means implicitly
> > convertable).
>
> Not true. There's at least one person who doesn't know that it's
> incorrect - me.

I know.

I wanted to write ``Every one but you knows that this is
incorrect'', but I feared that the moderators would consider
that it is a personal attack against you.

If the standard didn't said anywhere that + (binary) on
integers stands for addition, I would still believe that it
means ``add''.

You are welcome to submit a RFI/DR.

--

Valentin Bonnard
---
[ 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:

>On 28 Sep 99 18:26:38 GMT, "Sam Lindley" <sam@redsnapper.net> wrote:
>
>: Is the following function legal?
>:
>: bool contains(const set<char>& s, char c)
>: {
>: return (s.find(c) != s.end());
>: }
>
....

>: The above compiles on many compilers,
>
>Because many compilers use a version of the STL where iterator and
>const_iterator are the same thing for set.

This has been discussed before in this newsgroup, but it left some open
issues. Here's the problem restated:

Section 23.1.2 states the requirement that all associative containers
provide a find() function that returns iterator as well as a find()
function that returns const_iterator for const containers.

Section 23.3.3 lists the following member function for set<Key>:

 iterator find(const key_type& x) const;

In other words, it returns a non-const iterator from a const function.
This is in direct conflict with section 23.1.2 unless you infer that
iterator and const_iterator are exactly the same type for sets. I doubt
such an important fact would be put in the standard in such an obscure
way (although there are some things that are awfully hard to find in the
standard), but it is consistent with most implementations of
set<T>::iterator.

It is a common understanding that you cannot modify a set element
through its iterator, but I can't find that written anywhere, including
in the standard. Indeed, Herb Sutter writes in the October 1999 issue of
__The C++ Report__ that you *can* modify a set element through its an
iterator, provided you don't do anything that will change its position
in the set. (The library doesn't enforce the latter restriction; it just
does bad things if you violate it.) The MS 6.0 library does let you
modify a set element through its iterator, so the iterator and
const_iterator types are certainly not the same.

It seems like either Herb Sutter is right, in which case there is a
defect in the standard (const find() should return const_iterator) or
else he's wrong and iterator must be the same as const_iterator. Can
anybody find anything in the standard that supports either position. If
Mr. Sutter is right, has there been a change from some previous
definition of set<T>::iterator?

-------------------------------------------------------------
Pablo Halpern                            phalpern@newview.org

I am self-employed. Therefore, my opinions *do* represent
those of my employer.


[ 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 <37f282fd.289638508@news.internetconnect.com>,
phalpern@newview.org (Pablo Halpern) wrote:

> >Because many compilers use a version of the STL where iterator and
> >const_iterator are the same thing for set.
>
> This has been discussed before in this newsgroup, but it left some open
> issues. Here's the problem restated:
>
> Section 23.1.2 states the requirement that all associative containers
> provide a find() function that returns iterator as well as a find()
> function that returns const_iterator for const containers.
>
> Section 23.3.3 lists the following member function for set<Key>:
>
>         iterator find(const key_type& x) const;
>
> In other words, it returns a non-const iterator from a const function.
> This is in direct conflict with section 23.1.2 unless you infer that
> iterator and const_iterator are exactly the same type for sets. I doubt
> such an important fact would be put in the standard in such an obscure
> way (although there are some things that are awfully hard to find in the
> standard), but it is consistent with most implementations of
> set<T>::iterator.
>
> It is a common understanding that you cannot modify a set element
> through its iterator, but I can't find that written anywhere, including
> in the standard. Indeed, Herb Sutter writes in the October 1999 issue of
> __The C++ Report__ that you *can* modify a set element through its an
> iterator, provided you don't do anything that will change its position
> in the set. (The library doesn't enforce the latter restriction; it just
> does bad things if you violate it.) The MS 6.0 library does let you
> modify a set element through its iterator, so the iterator and
> const_iterator types are certainly not the same.
>
> It seems like either Herb Sutter is right, in which case there is a
> defect in the standard (const find() should return const_iterator) or
> else he's wrong and iterator must be the same as const_iterator. Can
> anybody find anything in the standard that supports either position. If
> Mr. Sutter is right, has there been a change from some previous
> definition of set<T>::iterator?

The C++ committee is considering this issue:

http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#103

-Howard


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

Is the following function legal?

bool contains(const set<char>& s, char c)
{
return (s.find(c) != s.end());
}

The above compiles on many compilers, but Sun C++ 5.0 fails. It complains
that there is no operator!= for comparing set<char>::iterator and
set<char>::const_iterator. (Remember find returns an iterator, not a
const_iterator, whereas end returns a const_iterator.)

Inverting the parameters of the '!=' comparison does work, however.

According to table 65 of the standard, a set<char>::iterator should be
convertible to a set<char>::const_iterator. Does this mean conversion should
be implicit? If so, why does the above code not work? Surely we should
expect operator== and operator!= to be symmetric, particularly for a
standard library.

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

Sam Lindley <sam@redsnapper.net> wrote:

> Is the following function legal?
>
> bool contains(const set<char>& s, char c)
> {
> return (s.find(c) != s.end());
> }
>
> The above compiles on many compilers, but Sun C++ 5.0 fails. It complains
> that there is no operator!= for comparing set<char>::iterator and
> set<char>::const_iterator. (Remember find returns an iterator, not a
> const_iterator, whereas end returns a const_iterator.)
>
> Inverting the parameters of the '!=' comparison does work, however.
>
> According to table 65 of the standard, a set<char>::iterator should be
> convertible to a set<char>::const_iterator. Does this mean conversion should
> be implicit? If so, why does the above code not work? Surely we should
> expect operator== and operator!= to be symmetric, particularly for a
> standard library.

This was the subject of my recent defect report, titled "member == in
container iterators considered harmful". If you search with something like
www.deja.com you'll see a long discussion about the topic.

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

Sam Lindley wrote:
...
> According to table 65 of the standard, a set<char>::iterator should be
> convertible to a set<char>::const_iterator. Does this mean conversion should
> be implicit? If so, why does the above code not work? Surely we should

I believe that an 'explicit' conversion constructor would meet that
requirement. Many people have disagreed with me on that, but I've never
seen any citations from the standard to support their point of view.
---
[ 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 28 Sep 99 18:26:38 GMT, "Sam Lindley" <sam@redsnapper.net> wrote:

: Is the following function legal?
:
: bool contains(const set<char>& s, char c)
: {
: return (s.find(c) != s.end());
: }

Maybe :)  To be practical, you could replace it with

   s.count(c);

A bit strange that contains is spelled "count" :)

: The above compiles on many compilers,

Because many compilers use a version of the STL where iterator and
const_iterator are the same thing for set.

: but Sun C++ 5.0 fails. It complains
: that there is no operator!= for comparing set<char>::iterator and
: set<char>::const_iterator. (Remember find returns an iterator, not a
: const_iterator, whereas end returns a const_iterator.)

Hum.  The fact that a const member returns a non-const iterator
could be reason for a defect report.  In the mood?

: Inverting the parameters of the '!=' comparison does work, however.
:
: According to table 65 of the standard, a set<char>::iterator should be
: convertible to a set<char>::const_iterator. Does this mean conversion should
: be implicit? If so, why does the above code not work? Surely we should
: expect operator== and operator!= to be symmetric, particularly for a
: standard library.

There is a defect report on the lack of symmetry for comparing const
and non-const iterators.  The usual implementation has operator== as
a member function which explains, but does not justify, the lack of
symmetry.

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              ]

Sam Lindley wrote:
>
> Is the following function legal?
>
> bool contains(const set<char>& s, char c)
> {
> return (s.find(c) != s.end());
> }
>
> The above compiles on many compilers, but Sun C++ 5.0 fails. It complains
> that there is no operator!= for comparing set<char>::iterator and
> set<char>::const_iterator. (Remember find returns an iterator, not a
> const_iterator, whereas end returns a const_iterator.)
>
> Inverting the parameters of the '!=' comparison does work, however.
>
> According to table 65 of the standard, a set<char>::iterator should be
> convertible to a set<char>::const_iterator. Does this mean conversion should
> be implicit? If so, why does the above code not work? Surely we should
> expect operator== and operator!= to be symmetric, particularly for a
> standard library.

>From CD2, 23.1.2 [lib.associative.reqmts]/7:

  Table 7--Associative container requirements (in addition to container)

[...]

-----------------------------------------------------------------------------------------
      expression     return type
assertion/note                complexity
                                           pre/post-condition

-----------------------------------------------------------------------------------------
[...]
   a.find(k)        iterator; con- returns an iterator pointing to an
logarithmic
                    st_iterator    element with the key equivalent to
                    for constant a k, or a.end() if such an element is
                                   not found.
[...]

Now set is an associative container, and therefore find _has_
to return a const_iterator for a const set. Therefore your
line should compile regardless of the existance of an automatic
conversion between iterator and const_iterator.

I don't think this has changed in the standard.

According to the conversion iterator->const_iterator:

Probably Sun's iterator has a _member_ function

set<T>::iterator::operator!=(set<T>::iterator cons& other) const;

On the left hand side of a member function no conversion
is applied.

IIRC, there was a discussion of that either in comp.std.c++
or in comp.lang.c++.moderated not too long ago. Searching
for "iterator", "const_iterator" and "comparision" in DejaNews
should probably find it.
---
[ 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              ]