468,272 Members | 2,202 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,272 developers. It's quick & easy.

which type should "std::set::begin() const" return?

On the book <Generic Programming and the STL>( Matthew . H . Austern ),this function is defined as
iterator set::begin() const.
However, why should a const object returns a non-const iterator?
Then, I found, in this book, the semantic of set::iterator is defined as same as set::const_iterator. Both of them must be const!
I tried to read the source of GNU STL(version 3.4.1).They were using a red-black tree to implant it (std::set has a _RBtree.) .Both set::iterator and set::const_iterator are simply defined as _RBtree::const_iterator.
But, in VC++, it is deferent.
There is a base class named xtree which also a red-black tree. Then the class map and set inherit from xtree (which implantation is better? is-a? has-a?).They don't defined iterator and const_iterator theirself,just inherit them from the base class xtree,and the member function begin() is defined as :
const_iterator set::begin() const;
iterator set::begin().
So ,we can initialize a mutable set, get the begin of it, then try to modify it!
The following code has been compiled successful under VC++2003
int a[4]={1,2,3,4};
std::set<int> s(a,a+4);
std::set<int>::iterator i=s.begin();
(*i) = 9;
std::cout<<"Now s = ";
std::copy(s.begin(),s.end(),std::ostream_iterator< int>(std::cout,","));
std::cout<<std::endl;
std::set<int>::const_iterator p=s.find(9);
if(p != s.end() )
std::cout<<(*p);
else std::cout<<"Cannot find the element special"<<std::endl;

A set must be a sorted container, but now it is not! So anything terrible things it would happen.
Is this a bug of VC++?

A bug of VC++.net STL
--
---------------snnn-------------
---http://snnn.blogone.net-----
Jul 22 '05 #1
11 2938
On Thu, 06 Jan 2005 01:18:22 +0800, snnn
<sn*****@gmail.com.haha.removeme> wrote:
On the book <Generic Programming and the STL>( Matthew . H . Austern ),this function is defined as
iterator set::begin() const.
However, why should a const object returns a non-const iterator?
Then, I found, in this book, the semantic of set::iterator is defined as same as set::const_iterator. Both of them must be const!
I tried to read the source of GNU STL(version 3.4.1).They were using a red-black tree to implant it (std::set has a _RBtree.) .Both set::iterator and set::const_iterator are simply defined as _RBtree::const_iterator.
But, in VC++, it is deferent.
There is a base class named xtree which also a red-black tree. Then the class map and set inherit from xtree (which implantation is better? is-a? has-a?).They don't defined iterator and const_iterator theirself,just inherit them from the base class xtree,and the member function begin() is defined as :
const_iterator set::begin() const;
iterator set::begin().
So ,we can initialize a mutable set, get the begin of it, then try to modify it!
The following code has been compiled successful under VC++2003
int a[4]={1,2,3,4};
std::set<int> s(a,a+4);
Shouldn't this be:
std::set<int> s(a,a+3);
??

Note that s is non-const...
std::set<int>::iterator i=s.begin();
(*i) = 9;
std::cout<<"Now s = ";
std::copy(s.begin(),s.end(),std::ostream_iterator< int>(std::cout,","));
std::cout<<std::endl;
std::set<int>::const_iterator p=s.find(9);
if(p != s.end() )
std::cout<<(*p);
else std::cout<<"Cannot find the element special"<<std::endl;

A set must be a sorted container, but now it is not! So anything terrible things it would happen.
Is this a bug of VC++? [or] A bug of VC++.net STL


You are mistaken... this is the declaration of begin() (actually two
declarations) for std::set as delivered with the Microsoft VCToolkit:

<quote>
iterator begin()
{ // return iterator for beginning of mutable
sequence
return (_TREE_ITERATOR(_Lmost()));
}

const_iterator begin() const
{ // return iterator for beginning of nonmutable
sequence
return (_TREE_CONST_ITERATOR(_Lmost()));
}
</quote>

As you can see, the "begin()" which returns a const_iterator is also
const, therefore you CANNOT modify the set if the set itself is const.

--
Bob Hairgrove
No**********@Home.com
Jul 22 '05 #2
Bob Hairgrove wrote:
On Thu, 06 Jan 2005 01:18:22 +0800, snnn
<sn*****@gmail.com.haha.removeme> wrote:
int a[4]={1,2,3,4};
std::set<int> s(a,a+4);

Shouldn't this be:
std::set<int> s(a,a+3);
??


That would only consume 3 elements of 's'.
Note that s is non-const...
What difference would that make? Values (r-values) used to
initialise the elements of the set<> cannot transfer their
const-ness, can they?
[...]

Jul 22 '05 #3
On Wed, 05 Jan 2005 15:36:30 -0500, Victor Bazarov
<v.********@comAcast.net> wrote:
Note that s is non-const...


What difference would that make? Values (r-values) used to
initialise the elements of the set<> cannot transfer their
const-ness, can they?


The subject line says it all:
"which type should "std::set::begin() const" return?"

Answer:
std::set::const_iterator (which it does).

The OP seems to think it doesn't.

--
Bob Hairgrove
No**********@Home.com
Jul 22 '05 #4
On Wed, 05 Jan 2005 15:36:30 -0500, Victor Bazarov
<v.********@comAcast.net> wrote:
Bob Hairgrove wrote:
On Thu, 06 Jan 2005 01:18:22 +0800, snnn
<sn*****@gmail.com.haha.removeme> wrote:
int a[4]={1,2,3,4};
std::set<int> s(a,a+4);

Shouldn't this be:
std::set<int> s(a,a+3);
??


That would only consume 3 elements of 's'.


Of course, you are right about this. I really need to RTFM some
more...

--
Bob Hairgrove
No**********@Home.com
Jul 22 '05 #5
Bob Hairgrove wrote:
On Wed, 05 Jan 2005 15:36:30 -0500, Victor Bazarov
<v.********@comAcast.net> wrote:

Note that s is non-const...


What difference would that make? Values (r-values) used to
initialise the elements of the set<> cannot transfer their
const-ness, can they?

The subject line says it all:
"which type should "std::set::begin() const" return?"

Answer:
std::set::const_iterator (which it does).

The OP seems to think it doesn't.


Well, yes. I just was curious on your 'notice that s is non-const'
comment placed right after another comment about the initialisation
of 's'. It shouldn't matter whether 's' is const or not when 's'
is initialised, no? I mean, it will be initialised just as well if
it were const...
Jul 22 '05 #6
The second param is a past-the-end iterator

Jul 22 '05 #7
Whether s is const or non-const,a set should never return a non-const
iterator.We can never modify a set by a iterator pointing to it's
element.Because a set must be a sorted container.You can insert and
remove element into/off it,but never manual modify it.

Jul 22 '05 #8
"snnn" <sn*****@gmail.com> wrote...
Whether s is const or non-const,a set should never return a non-const
iterator.We can never modify a set by a iterator pointing to it's
element.Because a set must be a sorted container.You can insert and
remove element into/off it,but never manual modify it.


I think you need to submit this as a proposal to comp.std.c++.
Jul 22 '05 #9

snnn wrote:
Whether s is const or non-const,a set should never return a non-const
iterator.We can never modify a set by a iterator pointing to it's
element.Because a set must be a sorted container.You can insert and
remove element into/off it,but never manual modify it.


Untrue.

class X {
int a;
int b;
public:
X(int a, int b) : a(a),b(b) {}
bool operator<( X const& rhs ) { return a<rhs.a; }
};
std::set<X> sox = foo();
sox.begin()->b=0; // safe

Regards,
Michiel Salters

Jul 22 '05 #10
!!!
You are right!

Jul 22 '05 #11
ivy
Have you got the rigth answer??
I've been thinking about it since we last meet.
Jul 22 '05 #12

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

4 posts views Thread by CupOfWater | last post: by
26 posts views Thread by Michael Klatt | last post: by
3 posts views Thread by Markus Dehmann | last post: by
1 post views Thread by Joe Gottman | last post: by
4 posts views Thread by chrisstankevitz | last post: by
5 posts views Thread by Austin | last post: by
7 posts views Thread by desktop | last post: by
reply views Thread by NPC403 | last post: by
reply views Thread by zattat | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.