C++Talk.NET Forum Index C++Talk.NET
C++ language newsgroups
 
Archives   FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Compromising the order of a std::set
Goto page 1, 2, 3, 4, 5  Next
 
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C++ Language (Moderated)
View previous topic :: View next topic  
Author Message
Matthias Hofmann
Guest





PostPosted: Wed Jul 06, 2005 12:34 pm    Post subject: Compromising the order of a std::set Reply with quote



Hello!

I found something that puzzles me: I thought that the elements of a std::set
were constant in order not to compromise their order. However, some member
functions (such as std::set::lower_bound) seem to return an object of type
std::set::iterator when invoked on a non-constant set, which makes it
possible to assign a new value to the referenced element.

I consulted the relevant chapter of "The C++ Standard Library" by Nicolai
Josuttis in order to find out whether I remember things correctly. There it
says that the interface of a std::set reflects the need to keep the elements
sorted:

- Sets and multisets don't provide operations for direct element access.
- Indirect access via iterators has the constraint that, from the iterator's
point of view, the element value is constant.

This made me think that it would not be possible to modify the elements of a
std::set. However, on Visual C++ 6 and 7 it seems to be easy, as the
following code compiles and runs fine:

#include <set>
#include <algorithm>
#include <iostream>

int main()
{
int elems[] = { 1000, 2000, 3000, 4000 };
int count = sizeof elems / sizeof elems[0];

std::set<int> s( elems, elems + count );
std::set<int>::iterator it;

std::copy( s.begin(), s.end(),
std::ostream_iterator<int>( std::cout, "n" ) );

std::cout << std::endl;

*s.begin() = 5000;

std::copy( s.begin(), s.end(),
std::ostream_iterator
return 0;
}

The output of the program is:

1000
2000
3000
4000

5000
2000
3000
4000

This must be a defect in Microsoft's libraries, or otherwise there must be
something that I completely misunderstood...

--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers



[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
P.J. Plauger
Guest





PostPosted: Wed Jul 06, 2005 9:57 pm    Post subject: Re: Compromising the order of a std::set Reply with quote



"Matthias Hofmann" <hofmann (AT) anvil-soft (DOT) com> wrote


Quote:
I found something that puzzles me: I thought that the elements of a
std::set
were constant in order not to compromise their order. However, some member
functions (such as std::set::lower_bound) seem to return an object of type
std::set::iterator when invoked on a non-constant set, which makes it
possible to assign a new value to the referenced element.

I consulted the relevant chapter of "The C++ Standard Library" by Nicolai
Josuttis in order to find out whether I remember things correctly. There
it
says that the interface of a std::set reflects the need to keep the
elements
sorted:

- Sets and multisets don't provide operations for direct element access.
- Indirect access via iterators has the constraint that, from the
iterator's
point of view, the element value is constant.

This made me think that it would not be possible to modify the elements of
a
std::set. However, on Visual C++ 6 and 7 it seems to be easy, as the
following code compiles and runs fine:

#include <set
#include #include
int main()
{
int elems[] = { 1000, 2000, 3000, 4000 };
int count = sizeof elems / sizeof elems[0];

std::set std::set<int>::iterator it;

std::copy( s.begin(), s.end(),
std::ostream_iterator<int>( std::cout, "n" ) );

std::cout << std::endl;

*s.begin() = 5000;

std::copy( s.begin(), s.end(),
std::ostream_iterator
return 0;
}

The output of the program is:

1000
2000
3000
4000

5000
2000
3000
4000

This must be a defect in Microsoft's libraries, or otherwise there must be
something that I completely misunderstood...

It's not exactly a defect, but it's also not easy to understand.
The original STL made set::iterator a synonym for set::const_iterator,
so you couldn't destroy the integrity of a set. The wording was made
fuzzier in the C++ Standard to leave open the possibility that the
two iterators might be different types. That rewording also left open
the interpretation that set::iterator might let you alter the stored
values.

Believe it or not, several people on the C++ committee then argued
that you really should be able to modify members of a set. If you
know the ordering rule, and confine your changes to those that
preserve the strict weak ordering of the set, you should be free
to change things at your discretion. I personally feel that this
flies in the face of the basic philosophy of type safety and
encapsulation. But under pressure from what I thought was the
concensus several years ago, I changed the Dinkumware set to
permit changes.

The 2003 revision has changed wording in this area, which now
better endorses the notion that you shouldn't be able to alter
set elements. So our latest library can be built for safety
(the macro _HAS_IMMUTABLE_SETS is nonzero) or for backward
compatibility. I personally prefer the former option.

HTH,

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com



[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
chris jefferson
Guest





PostPosted: Wed Jul 06, 2005 10:00 pm    Post subject: Re: Compromising the order of a std::set Reply with quote



Matthias Hofmann wrote:
Quote:
Hello!

I found something that puzzles me: I thought that the elements of a std::set
were constant in order not to compromise their order. However, some member
functions (such as std::set::lower_bound) seem to return an object of type
std::set::iterator when invoked on a non-constant set, which makes it
possible to assign a new value to the referenced element.


This is something which I've seen discussed before, both here and on
comp.std.c++ (for example, go to google groups and search for "c++
std::set non-const iterator").

I personally think these iterators should only be const. The major
argument for making them non-const appears to be that some people want
to be able to change elements in ways that doesn't violate the ordering.

Chrisw

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Andrew Koenig
Guest





PostPosted: Wed Jul 06, 2005 10:05 pm    Post subject: Re: Compromising the order of a std::set Reply with quote

"Matthias Hofmann" <hofmann (AT) anvil-soft (DOT) com> wrote


Quote:
I found something that puzzles me: I thought that the elements of a
std::set
were constant in order not to compromise their order. However, some member
functions (such as std::set::lower_bound) seem to return an object of type
std::set::iterator when invoked on a non-constant set, which makes it
possible to assign a new value to the referenced element.

Well, not really -- because the value_type of std::set<T> is const T, not T.


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Gabriel Dos Reis
Guest





PostPosted: Wed Jul 06, 2005 10:06 pm    Post subject: Re: Compromising the order of a std::set Reply with quote

"Matthias Hofmann" <hofmann (AT) anvil-soft (DOT) com> writes:

Quote:
Hello!

I found something that puzzles me: I thought that the elements of a std::set
were constant in order not to compromise their order. However, some member

Opinions are divided.

It is a contentious issue as whether or not compromising the order is
a straight one-size-fits-all jacket the library should put on
everybody or a knife whose reponsability is left to the programmer.

For most parts, C++ has provided safety rules and way to violate to
violate them if the need arises. The library seems to have taken a
very curious counter-road here. The purpose of a set is not to order
elements -- but to contain them uniquely. Ordering is just a
technical tool, not a goal.

For the most part where I need a set -- collection of elements,
uniquely identified -- I end up with rolling my own. For my
practical need, std::set has been made close to useless.

And as such, std::set is not a Container -- unless the notion of
Container is redefinied.

--
Gabriel Dos Reis
[email]gdr (AT) integrable-solutions (DOT) net[/email]

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Sascha Müller
Guest





PostPosted: Wed Jul 06, 2005 10:09 pm    Post subject: Re: Compromising the order of a std::set Reply with quote

Matthias Hofmann wrote:
Quote:
- Sets and multisets don't provide operations for direct element access.
- Indirect access via iterators has the constraint that, from the iterator's
point of view, the element value is constant.

[...]
*s.begin() = 5000;

Nice catch!

According to Stroustrup, the type of std::set::iterator is
implementation-defined.

In GCC 3.3.5 it is

(from stl_set.h)
typedef typename _Rep_type::const_iterator iterator;
typedef typename _Rep_type::const_iterator const_iterator;

where _Rep_Type is the underlying data structure that the data is stored
in (i.e. a red-black-tree). So the iterator is always const and the code
cannot be compiled on GCC.

However, I don't know what the Standard says about this issue.


Regards,

Sascha Müller

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Howard Hinnant
Guest





PostPosted: Wed Jul 06, 2005 10:15 pm    Post subject: Re: Compromising the order of a std::set Reply with quote

In article <dagg6m$e2t$1 (AT) news1 (DOT) nefonline.de>,
"Matthias Hofmann" <hofmann (AT) anvil-soft (DOT) com> wrote:

Quote:
Hello!

I found something that puzzles me: I thought that the elements of a std::set
were constant in order not to compromise their order. However, some member
functions (such as std::set::lower_bound) seem to return an object of type
std::set::iterator when invoked on a non-constant set, which makes it
possible to assign a new value to the referenced element.

I consulted the relevant chapter of "The C++ Standard Library" by Nicolai
Josuttis in order to find out whether I remember things correctly. There it
says that the interface of a std::set reflects the need to keep the elements
sorted:

- Sets and multisets don't provide operations for direct element access.
- Indirect access via iterators has the constraint that, from the iterator's
point of view, the element value is constant.

This made me think that it would not be possible to modify the elements of a
std::set. However, on Visual C++ 6 and 7 it seems to be easy, as the
following code compiles and runs fine:

#include <set
#include #include
int main()
{
int elems[] = { 1000, 2000, 3000, 4000 };
int count = sizeof elems / sizeof elems[0];

std::set std::set<int>::iterator it;

std::copy( s.begin(), s.end(),
std::ostream_iterator<int>( std::cout, "n" ) );

std::cout << std::endl;

*s.begin() = 5000;

std::copy( s.begin(), s.end(),
std::ostream_iterator
return 0;
}

The output of the program is:

1000
2000
3000
4000

5000
2000
3000
4000

This must be a defect in Microsoft's libraries, or otherwise there must be
something that I completely misunderstood...

The current standard is not clear on this subject, and thus
I would not classify this as a defect in the Microsoft
libraries. Rather it is a defect in the standard itself.

There is a defect report on this issue here:

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#
103

The resolution to this dr won't become official until the
ratification of C++0X. The resolution includes wording
which clarifies that set::iterator is a constant iterator
(like set::const_iterator).

The Freescale CodeWarrior std::lib already implements lwg
103 and gives a compile time error:

Error : illegal assignment to constant
HelloWorld.cp line 18 *s.begin() = 5000;


-Howard

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
RenjithMohan
Guest





PostPosted: Wed Jul 06, 2005 10:28 pm    Post subject: Re: Compromising the order of a std::set Reply with quote

The answer is obvious. If you destroy the internal structure of a set
(which is implemented as a ordered red-black tree) then you loose many
things.

After your code
*s.begin() = 5000;

Eventhough it prints out all the values correctly, the fundamental
things stop working. For e.g try to find the value 2000 from the set.

set<int>::iterator itrFind = s.find(2000);
if(itrFind != s.end())
{
cout << "Found value" << *itrFind << std::endl;
}
else
{
cout << "Not Found value!!!";
}
It prints "Not Found value!!!"
However if I do the following

set if(itrChange!= s.end())
{
s.erase(itrFirst);
s.insert(5000);
}
Everything works.

The short and simple rule would be to, not change the Keys of
associative containers directly but to use the erase-insert idiom so
that the insert will place the new value in its appropriate place.
But the crucial thing is, should begin() return a const_iterator?.
Even the SGI STL implementation begin() method returns the iterator.


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Back to top
Gianluca Silvestri
Guest





PostPosted: Wed Jul 06, 2005 10:31 pm    Post subject: Re: Compromising the order of a std::set Reply with quote


"Matthias Hofmann" <hofmann (AT) anvil-soft (DOT) com> ha scritto nel messaggio
news:dagg6m$e2t$1 (AT) news1 (DOT) nefonline.de...
Quote:
Hello!

I found something that puzzles me: I thought that the elements of a
std::set
were constant in order not to compromise their order. However, some member
functions (such as std::set::lower_bound) seem to return an object of type
std::set::iterator when invoked on a non-constant set, which makes it
possible to assign a new value to the referenced element.

I consulted the relevant chapter of "The C++ Standard Library" by Nicolai
Josuttis in order to find out whether I remember things correctly. There
it
says that the interface of a std::set reflects the need to keep the
elements
sorted:

- Sets and multisets don't provide operations for direct element access.
- Indirect access via iterators has the constraint that, from the
iterator's
point of view, the element value is constant.

This made me think that it would not be possible to modify the elements of
a
std::set.

Current standard says very few about iterators for associative containers
(25.1.2/5:iterator of an associative container if of the bidirectional
iterator category).
But the latest working draft says more (same reference):
iterator of an associative container is of the bidirectional iterator
category. For associative containers where the value

type is the same as the key type, both iterator and const_iterator are
constant iterators. It is unspecified whether

or not iterator and const_iterator are the same type.

you can also look here
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#103



HTH

Gianluca


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Bo Persson
Guest





PostPosted: Wed Jul 06, 2005 10:33 pm    Post subject: Re: Compromising the order of a std::set Reply with quote


"Matthias Hofmann" <hofmann (AT) anvil-soft (DOT) com> skrev i meddelandet
news:dagg6m$e2t$1 (AT) news1 (DOT) nefonline.de...
Quote:
Hello!

I found something that puzzles me: I thought that the elements of a
std::set
were constant in order not to compromise their order. However, some
member
functions (such as std::set::lower_bound) seem to return an object of
type
std::set::iterator when invoked on a non-constant set, which makes it
possible to assign a new value to the referenced element.

I consulted the relevant chapter of "The C++ Standard Library" by
Nicolai
Josuttis in order to find out whether I remember things correctly.
There it
says that the interface of a std::set reflects the need to keep the
elements
sorted:

- Sets and multisets don't provide operations for direct element
access.
- Indirect access via iterators has the constraint that, from the
iterator's
point of view, the element value is constant.

This made me think that it would not be possible to modify the
elements of a
std::set. However, on Visual C++ 6 and 7 it seems to be easy, as the
following code compiles and runs fine:


This is a possible defect in the Standard, not specifying when an update
might be ok. A proposal for a revised wording is available here:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1831.html#103


The "WP" status indicates that it is already included in the draft of
the next revision of the standard.


Bo Persson



[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Paul Groke
Guest





PostPosted: Wed Jul 06, 2005 10:39 pm    Post subject: Re: Compromising the order of a std::set Reply with quote

Matthias Hofmann wrote:
Quote:
Hello!

I found something that puzzles me: I thought that the elements of a std::set
were constant in order not to compromise their order. However, some member
functions (such as std::set::lower_bound) seem to return an object of type
std::set::iterator when invoked on a non-constant set, which makes it
possible to assign a new value to the referenced element.

I consulted the relevant chapter of "The C++ Standard Library" by Nicolai
Josuttis in order to find out whether I remember things correctly. There it
says that the interface of a std::set reflects the need to keep the elements
sorted:

- Sets and multisets don't provide operations for direct element access.
- Indirect access via iterators has the constraint that, from the iterator's
point of view, the element value is constant.

This made me think that it would not be possible to modify the elements of a
std::set. However, on Visual C++ 6 and 7 it seems to be easy, as the
following code compiles and runs fine:

#include <set
#include #include
int main()
{
int elems[] = { 1000, 2000, 3000, 4000 };
int count = sizeof elems / sizeof elems[0];

std::set std::set<int>::iterator it;

std::copy( s.begin(), s.end(),
std::ostream_iterator<int>( std::cout, "n" ) );

std::cout << std::endl;

*s.begin() = 5000;

std::copy( s.begin(), s.end(),
std::ostream_iterator
return 0;
}

The output of the program is:

1000
2000
3000
4000

5000
2000
3000
4000

This must be a defect in Microsoft's libraries, or otherwise there must be
something that I completely misunderstood...

Well, the SGI docs say that "iterator" and "const_iterator" are the
same type, and STLport indeed does define them as being the same type.
So it looks like a bug to me too...

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
P.J. Plauger
Guest





PostPosted: Thu Jul 07, 2005 12:15 pm    Post subject: Re: Compromising the order of a std::set Reply with quote

"Andrew Koenig" <ark (AT) acm (DOT) org> wrote


Quote:
"Matthias Hofmann" <hofmann (AT) anvil-soft (DOT) com> wrote in message
news:dagg6m$e2t$1 (AT) news1 (DOT) nefonline.de...

I found something that puzzles me: I thought that the elements of a
std::set
were constant in order not to compromise their order. However, some
member
functions (such as std::set::lower_bound) seem to return an object of
type
std::set::iterator when invoked on a non-constant set, which makes it
possible to assign a new value to the referenced element.

Well, not really -- because the value_type of std::set<T> is const T, not
T.

I don't think so.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com



[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
P.J. Plauger
Guest





PostPosted: Thu Jul 07, 2005 12:16 pm    Post subject: Re: Compromising the order of a std::set Reply with quote

"Paul Groke" <swampmonster (AT) der-ball-ist-rund (DOT) net> wrote


Quote:
This must be a defect in Microsoft's libraries, or otherwise there must
be
something that I completely misunderstood...

Well, the SGI docs say that "iterator" and "const_iterator" are the
same type, and STLport indeed does define them as being the same type.
So it looks like a bug to me too...

Uh, neither the SGI nor the STLport implementation defines the
C++ Standard.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com



[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
P.J. Plauger
Guest





PostPosted: Thu Jul 07, 2005 12:17 pm    Post subject: Re: Compromising the order of a std::set Reply with quote

"Gabriel Dos Reis" <gdr (AT) integrable-solutions (DOT) net> wrote


Quote:
"Matthias Hofmann" <hofmann (AT) anvil-soft (DOT) com> writes:

| Hello!
|
| I found something that puzzles me: I thought that the elements of a
std::set
| were constant in order not to compromise their order. However, some
member

Opinions are divided.

It is a contentious issue as whether or not compromising the order is
a straight one-size-fits-all jacket the library should put on
everybody or a knife whose reponsability is left to the programmer.

For most parts, C++ has provided safety rules and way to violate to
violate them if the need arises. The library seems to have taken a
very curious counter-road here. The purpose of a set is not to order
elements -- but to contain them uniquely. Ordering is just a
technical tool, not a goal.

Perhaps, but the specification of set is that it is ordered.
You can destroy that condition by an injudicious assignment.

Quote:
For the most part where I need a set -- collection of elements,
uniquely identified -- I end up with rolling my own. For my
practical need, std::set has been made close to useless.

And as such, std::set is not a Container -- unless the notion of
Container is redefinied.

I believe that set meets the requirements of an associative
container in the C++ Standard.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com



[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Gene Bushuyev
Guest





PostPosted: Thu Jul 07, 2005 12:31 pm    Post subject: Re: Compromising the order of a std::set Reply with quote

"Gabriel Dos Reis" <gdr (AT) integrable-solutions (DOT) net> wrote

Quote:
"Matthias Hofmann" <hofmann (AT) anvil-soft (DOT) com> writes:
....
very curious counter-road here. The purpose of a set is not to order
elements -- but to contain them uniquely. Ordering is just a
technical tool, not a goal.

I beg to differ. If (multi)set were allowed to be unsorted then they would
be pretty useless. In fact you wouldn't be able to use any of the set_xxxx
algorithms with (multi)set as those require sorted ranges (25.3.5):

"This section defines all the basic set operations on sorted structures.
They also work with multisets (23.3.4) containing multiple copies of
equivalent elements."

Gene


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]


Back to top
Post new topic   Reply to topic    C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT
Goto page 1, 2, 3, 4, 5  Next
Page 1 of 5

 
 


Powered by phpBB © 2001, 2006 phpBB Group