分享
 
 
 

Effective STL条款44

王朝other·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

条款44: 尽量用成员函数代替同名的算法

有些容器拥有和STL算法同名的成员函数。关联容器提供了count、find、lower_bound、upper_bound和equal_range,而list提供了remove、remove_if、unique、sort、merge和reverse。大多数情况下,你应该用成员函数代替算法。这样做有两个理由。首先,成员函数更快。其次,比起算法来,它们与容器结合得更好(尤其是关联容器)。那是因为同名的算法和成员函数通常并不是是一样的。

我们以对关联容器的实验开始。假如有一个set<int>,它存储了一百万个元素,而你想找到元素727的第一个出现位置(如果存在的话)。这儿有两个最自然的方法来执行搜索:

set<int> s; // 建立set,放1,000,000个数据

... // 进去

set<int>::iterator i = s.find(727); // 使用find成员函数

if (i != s.end()) ...

set<int>::iterator i = find(s.begin(), s.end(), 727); // 使用find算法

if (i != s.end()) ...

find成员函数运行花费对数时间,所以不管727是否存在于此set中,set::find只需执行不超过40次比较来查找它,而一般只需要大约20次。相反,find算法运行花费线性时间,所以如果727不在此set中,它需要执行1,000,000次比较。即使727在此set中,也平均需要执行500,000次比较来找到它。效率得分如下:

find成员:大约40(最坏的情况)至大约20(平均情况)

find算法:1,000,000(最坏的情况)至500,000(平均情况)

和高尔夫比赛一样,分值低的赢。正如你所见,这场比赛结果没什么可说的。

我必须对find成员函数所需的比较次数表示小小的谨慎,因为它有些依赖于关联容器的实现。绝大部分的实现是使用的红黑树——平衡树的一种——失衡度可能达到2。在这样的实现中,对一百万个元素的set进行搜索所需最多的比较次数是38次。但对绝大部分的搜索情况而言,只需要不超过22次。一个基于完全平衡树的实现绝不需要超过21次比较,但在实践中,完全平衡树的效率总的来说不如红黑树。这就是为什么大多数的STL实现都使用红黑树。

效率不是find成员函数和find算法间的唯一差别。正如条款19所解释的,STL算法判断两个对象是否相同的方法是检查的是它们是否相等(equality),而关联容器是用等价(equivalence)来测试它们的“同一性”。 因此,find算法搜索727用的是相等,而find成员函数用的是等价。相等和等价间的区别可能造成成功搜索和不成功搜索的区别。比如说,条款19演示了用find算法在关联容器搜索失败而用find成员函数却搜索成功的情况!因此,如果使用关联容器的话,你应该尽量使用成员函数形式的find、count、lower_bound等等,而不是同名的泛型算法,因为这些成员函数版本提供了和其它成员函数一致的行为。由于相等和等价间的差别,泛型算法不能提供这样的一致行为。

这一差别对map和multimap尤其明显,因为它们容纳的是对象对(pair object),而它们的成员函数只在意对象对的key部分。因此,count成员函数只统计key值匹配的对象对的数目 (所谓“匹配”,自然是检测等价情况);对象对的value部份被忽略。成员函数find、lower_bound、upper_bound和equal_range也是如此。但是如果你使用count算法,它的寻找将基于(a)相等和(b)对象对的全部组成部分;泛型算法find、lower_bound等同样如此。要想让泛型算法只关注于对象对的key部分,必须要跳出条款23描述的限制(那儿介绍了用相等测试代替等价测试的方法)。

另一方面,如果你真的关心效率,你可以采用条款23中的技巧,联合条款34中讲的对数时间搜索算法。相对于性能的提升,这只是一个很小的代价。再者,如果你真的在乎效率,你应该考虑非标准的hash容器(在条款25进行了描述),只是,你将再次面对相等和等价的区别。

对于标准的关联容器,选择成员函数而不是同名的算法有几个好处。首先,你得到的是对数时间而不是线性时间的性能。其次,你判断两个元素“相同”使用的是等价,这是关联容器的默认定义。第三,当操纵map和multimap时,你可以自动地只处理key值而不是(key, value)对。这三点给了优先使用成员函数完美的铁甲。

让我们转到list的与算法同名的成员函数身上。这里的故事几乎全部是关于效率的。每个被list作了特化的算法(remove、remove_if、unique、sort、merge和reverse)都要拷贝对象,而list的特别版本什么都没有拷贝;它们只是简单地操纵连接list的节点的指针。算法和成员函数的算法复杂度是相同的,但如果操纵指针比拷贝对象的代价小的话,list的版本应该提供更好的性能。

牢牢记住这一点很重要:list成员函数的行为和它们的算法兄弟的行为经常不相同。正如条款32所解释的,如果你真的想从容器中清除对象的话,调用remove、remove_if和unique算法后,必须紧接着调用erase函数;但list的remove、remove_if和unique成员函数真的去掉了元素,后面不需要接着调用erase。

在sort算法和list的sort成员函数间的一个重要区别是前者不能用于list。作为单纯的双向迭代器,list的迭代器不能传给sort算法。merge算法和list的merge成员函数之间也同样存在巨大差异。这个算法被限制为不能修改源范围,但list::merge总是修改它的宿主list。

所以,你明白了吧。 当面临着STL算法和同名的容器成员函数间进行选择时,你应该尽量使用成员函数。几乎可以肯定它更高效,而且它看起来也和容器的惯常行为集成得更好。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有