前几天在写一个小程序，总是无法在 VC++.net 2003 和 gcc 下同时编译通过。因为我要做的是一个跨平台的库，所以这点极为重要，于是就一点点的去查看出错信息，看究竟是哪里的问题。
查到最后，发现原来是 const 的问题。
VC++ 下 set::begin() const 返回 const_iterator, 而 gcc 下返回 iterator. 也许你认为这是小事 ， 其实不 是。多一个 const, 少一个 const, 都是无法编译通过的。我别无所求，只求能在两个编译器下都能编译通过。
那么，究竟谁的实现更好些呢？抱着这样的疑问，我把我的问题发到了 comp.lang.c++.
然后，我查看了下二者的 STL 中的 set 的实现。发现他们在内部不约而同的都是使用的红黑树 (Red-Black tree) 来实现的 . 虽说 STL standard 中并没有 tree 这样的 container. 但是你在 VC++ 的头文件中可以发现一个 <xtree>,gcc 中同样有一个 <tree.h>. 内部实现的都是一棵红黑树。但是，之后在实现 set 的时候，二者的方式就有所不同了。
MS 用的是 is-a 关系从 class xtree 继承， GNU 用的是 has-a 关系在 set 内部定义了一个 _RBTree 。
如果你去比较下二者的源代码 , 你会发现 MS 的要简洁的多。虽说从本质上来讲基本都是一样的。但是由于 GNU 用的是 has-a 关系，所以它至少必须在其 set 类中对所有的外部接口重新定义一次。而在 MS STL 的 std::set 源代码中，你找不到 begin() 这个函数的定义，它是直接从基类 xtree 中继承而来的。
首先，我们查看标准中 std::begin() 是怎么定义的。
iterator set::begin() const.
和 gcc 完全一样
再看 MS VC++ STL 中
const_iterator begin() const;
iterator begin().
你会发现在 GNU 的实现中，一个 const 的 this 指针，却返回了一个 mutable iterator? 但是标准中就是这样定义的，为什么呢？我们继续来查看
在《 Generic Programming and the STL 》 (Matthew H. Austern) 中作者对 set 的定义是：
“Model Of
Sorted Associative Container, Simple Associative Container, Unique Associative Container. ”
追到它的基 concept,Container, 我们在这找到了 begin() 的定义
· Beginning of range
a.begin()
Return type: iterator if a is mutable, otherwise const_iterator.
Semantics: Returns an iterator pointing to the first element in the container.
理论上来讲 ， 对于任何一个 const Container, 那么 begin() 函数返回的就应该是一个 const_iterator. 但是事实不会这么简单。再看 set 中 iterator 和 const iterator 是怎么定义的。
set::iterator
The set's iterator type, a constant Bidirectional Iterator. ( The class set has no mutable iterator type. Elements may be inserted into or removed from a set, but they may never be modified in place.)
set::const_iterator
The set's constant iterator type,also a constant Bidirectional Iterator.(Possibly the same type as iterator.)
于是对于 iterator set::begin() const 这样奇怪的定义，我们也就能一目了然了。主要是考虑到对于一个 Sorted Container, 如果你得到一个 mutable iterator, 那么就可以利用它修改它所指向的值，那么这个 container 就会被破坏。
例如：
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;
再看对于此问题，他们是如何实现的。
MS VC++ STL 只是在 class set 中用 typedef 重新定义了下 iterator 和 const_iterator 这两个 type.
typedef _Tree<_Tset_traits<_Kty, _Pr, _Alloc, false> > _Mybase;
typedef typename _Mybase::iterator iterator;
typedef typename _Mybase::const_iterator const_iterator;
而 GCC
typedef _Rb_tree<key_type, value_type,
_Identity<value_type>, key_compare, _Alloc> _Rep_type;
typedef typename _Rep_type::const_iterator iterator;
typedef typename _Rep_type::const_iterator const_iterator;
我现在自己在写一个 container, it has-a set. 我要对外提供 begin() 和 insert() 方法，那么 ,begin() const 应该返回什么值？我需要能在 VC++ 和 gcc 上都能顺利的编译通过，于是，我就想当然的试着去修改 VC++ 中 iterator 的定义，使得让它能够符合 c++ standard. 我把 VC++ 中 set::iterator 也定义成了其基类的 const_iterator.
然而，事实远远没有我想象的那么简单。 gcc stl 中可以没有语义上的 iterator, 因为它是用的 has-a 关系，但是 VC++ 中必须有，因为它用的是 is-a 关系！当我调用 set::insert(iterator i) 的时候，其实是在直接调用 xtree::insert(iterator i). 在这里，我们需要的是一个 iterator, 而不是一个 const_iterator! 如果 MS 在其 STL 实现中强行的把 set ::iterator 定义为 xTree ::const_iterator. 将使得用户找不到 合适的 iterator 接口，来调用 set ::insert(iterator i) 方法！所以， MS 在其 std ::set 中提供 mutable iterator, 并非是设计时的概念错误，而是由于它选用了 is-a 的方式继承，所以它必须提供这样的接口。然后，就迫使它的
std ::begin() const 函数必须返回一个 const_iterator
作为补偿，它再定义了一个重载
iterator std ::begin() const.
说到这里，你可能会认为 MS 的实现很拙劣，为了少写几行代码，弄的一塌糊涂，再次违背 standard c++ stl 标准，那么果真是如此吗？
回到最初的问题，一个 set 是否应该拥有一个 public 的 mutable iterator 接口？它是否可以在某些情况下返回给用户 iterator 以使得用户利用其直接对它内部的这个 RB tree 的树叶的值进行修改？
在 comp.lang.c++ 上，回复者贴出了这样的代码
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
于是我才 恍然大悟。
具体来说，
我现在要做的这个 Container, 是一个多项式，它内部有一个 set,set 的每个元素是一个单项式。单项式的种类可以是多种多样的， 4X^2,8X, 或者一个矩阵，都可以。我现在只是实现了简单的这样的单向式 a*X^b. 然后 operator< 的定义是依据这个单项式的幂数对其排序。
回到原来的问题，我是否需要 set 返回一个 mutable iterator ?
答案是 ，当然需要！
+ ， * 这样简单的操作我很容易在单项式内部进行封装，但是， insert 方法！
当我向一个多项式插入一个单项式的时候，我会先检查是否有和它幂数相同的项，有的话，就改变这一项的系数，没有，就插入新项。
My God ! 依据 STL 标准，我必须先用一个临时变量保存找到的那一个多项式，然后利用指向它的 iterator 删除它，然后修改系数，然后再插入。
value_type t(*i);
this->erase(i);
exprList.insert(x+ t );
How terrible!
其实我需要的只是简单的
(*i). coefficient +=x. coefficient;
但是我不能这么做，除非我放弃可移植性！但是，如此低下的效率，就算我做好了，又能怎样呢？慢吞吞，谁会去用？
好吧，一个简单的方式。既然 GNU STL 和 MS STL 的 set 的源代码我都看了，而且基本完全看懂了。自己重新封装一次，也是很快的。那么，我现在就需要 copy 一个 RBtree 的源文件来，然后在我的 Container 中放一个 RBtree, 然后重新封装那些接口。
但是这样做很叫人恼火！
既然 STL 库中已经有一个 set 了，那么我为什么还要再重新去封装它？
GNU ，为了安全性，尽可能少的给用户提供接口。
MS, 则把选择的权利留给程序员，给了你权利，你可以拿它来破坏掉这棵树，也可以拿它来实现更快速的插入算法。