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: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
--
---------------snnn-------------
---http://snnn.blogone.net-----

snnn

On Thu, 06 Jan 2005 01:18:22 +0800, snnn
<> 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: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.

--
Bob Hairgrove

Bob Hairgrove wrote:
> On Thu, 06 Jan 2005 01:18:22 +0800, snnn
> <> 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?

> [...]

On Wed, 05 Jan 2005 15:36:30 -0500, Victor Bazarov
<> 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

On Wed, 05 Jan 2005 15:36:30 -0500, Victor Bazarov
<> wrote:

>Bob Hairgrove wrote:
>> On Thu, 06 Jan 2005 01:18:22 +0800, snnn
>> <> 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

Bob Hairgrove wrote:
> On Wed, 05 Jan 2005 15:36:30 -0500, Victor Bazarov
> <> 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...

The second param is a past-the-end iterator

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.

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

I think you need to submit this as a proposal to comp.std.c++.

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