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

[snnn]

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:stream_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

 

[Bob Hairgrove]

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:stream_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.

 

[Victor Bazarov]

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

[...]

 

[Bob Hairgrove]

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]

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...

 

[Victor Bazarov]

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...

 

[snnn]

The second param is a past-the-end iterator

 

[snnn]

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.

 

[Victor Bazarov]

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++.

 

[msalters]

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

 

[snnn]

!!!
You are right!

 

[ivy]

Have you got the rigth answer??
I've been thinking about it since we last meet.