What type should std::set::begin() return?

前几天在写一个小程序,总是无法在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++的头文件中可以发现一个,gcc中同样有一个
.内部实现的都是一棵红黑树。但是,之后在实现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 s(a,a+4);
std::set::iterator i=s.begin();
(*i) = 9;
std::cout<<"Now s = ";
std::copy(s.begin(),s.end(),std::ostream_iterator(std::cout,","));
std::cout<<:endl;
std::set::const_iterator p=s.find(9);
if(p != s.end() )
std::cout<<(*p);
else std::cout<<"Cannot find the element special"<<:endl;<> <:endl;
<: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 _Identity, 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 };
std::set 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;

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥