Effective_STL 学习笔记(四十四) 尽量使用成员函数代替同名的算法

有些容器拥有和 STL 算法同名的成员函数。

关联容器提供了 count、find、lower_bound、upper_bound 和 euqal_range

list 提供了 remove、remove_if、unique、merge 和 reverse

大多数时候应该用成员函数代替手写算法,这样做的两个理由:

  比起算法,它们与容器结合的更好(尤其是关联容器)

  同名的算法很成员函数通常不是一样的

假设 set<int> 容纳一百万个元素,想找到元素 727 的第一次出现的位置

1   set<int> s;
2   . . .
3   set<int>::iterator i = s.find(727);  // 使用成员函数
4   if( i != s.end() ) . . .
5   set<int>::iterator i = find( s.begin(), s.end(), 727 ); // 使用 find 算法
6   if( i != s.end()) . . .

使用成员函数花费对数时间(set实现为红黑树),使用算法将花费线性时间

STL 算法判断两个对象是否相同的方法检查的是它们是否相等,而关联容器是用等价来测试它们的 “同一性”

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

list 的成员函数。每个被 list 作了特化的算法(remove、remove_if、unique、sort、merge 和 reverse)都要拷贝对象,而 list 的特别版本什么都没有拷贝;它们只是简单地操纵连接 list 的节点的指针。算法和成员函数的算法复杂度是相同的。

另外,list 的成员函数的行为和它们的同名算法的行为经常是不相同。如果真想从容器中清除对象,调用 remove、remove_if 和 unique 算法后,必须接着调用 erase 函数;但是,list 的 remove、remove_if 和 unique 成员函数真的去掉了元素,后面不再需要接着调用 erase

在 sort 算法和 list 的成员函数间的一个重要的区别是前者不能用于 list。作为单纯的双向迭代器, list 的迭代器不能传给 sort 算法。merge 算法和 list 的merge 成员函数之间也同样存在巨大差异

原文地址:https://www.cnblogs.com/kidycharon/p/10052504.html