《Effective STL》

haoji

Center of STL Study
——最优秀的STL学习网站
条款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实现都使用红黑树。

haoji

效率不是find成员函数和find算法间的唯一差别。正如条款19所解释的，STL算法判断两个对象是否相同的方
法是检查的是它们是否相等，而关联容器是用等价来测试它们的“同一性”。 因此，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中讲的对数时间搜索算法。相对
于性能的提升，这只是一个很小的代价。再者，如果你真的在乎效率，你应该考虑非标准的散列容器（在条
款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算法和同名的容器成员函数间进行选择时，你应该尽量使用成员函数。几
乎可以肯定它更高效，而且它看起来也和容器的惯常行为集成得更好。

haoji

Center of STL Study
——最优秀的STL学习网站
条款45：注意count、find、binary_search、lower_bound、upper_bound
和equal_range的区别
你要寻找什么，而且你有一个容器或者你有一个由迭代器划分出来的区间——你要找的东西就在里面。你要
怎么完成搜索呢？你箭袋中的箭有这些：count、count_if、find、find_if、binary_search、lower_bound、
upper_bound和equal_range。面对着它们，你要怎么做出选择？
简单。你寻找的是能又快又简单的东西。越快越简单的越好。
暂时，我假设你有一对指定了搜索区间的迭代器。然后，我会考虑到你有的是一个容器而不是一个区间的情
况。
要选择搜索策略，必须依赖于你的迭代器是否定义了一个有序区间。如果是，你就可以通过binary_search、
lower_bound、upper_bound和equal_range来加速（通常是对数时间——参见条款34）搜索。如果迭代器并没有
划分一个有序区间，你就只能用线性时间的算法count、count_if、find和find_if。在下文中，我会忽略掉count
和find是否有_if的不同，就像我会忽略掉binary_search、lower_bound、upper_bound和equal_range是否带有判
断式的不同。你是依赖默认的搜索谓词还是指定一个自己的，对选择搜索算法的考虑是一样的。
如果你有一个无序区间，你的选择是count或着find。它们分别可以回答略微不同的问题，所以值得仔细去区
分它们。count回答的问题是：“是否存在这个值，如果有，那么存在几份拷贝？”而find回答的问题
是：“是否存在，如果有，那么它在哪儿？”
假设你想知道的东西是，是否有一个特定的Widget值w在list中。如果用count，代码看起来像这样：
list<Widget> lw; // Widget的list
Widget w; // 特定的Widget值
...
if (count(lw.begin(), lw.end(), w)) {
... // w在lw中
} else {
... // 不在
}

haoji

这里示范了一种惯用法：把count用来作为是否存在的检查。count返回零或者一个正数，所以我们把非零转
化为true而把零转化为false。如果这样能使我们要做的更加显而易见：
if (count(lw.begin(), lw.end(), w) != 0) ...
而且有些程序员这样写，但是使用隐式转换则更常见，就像最初的例子。
和最初的代码比较，使用find略微更难懂些，因为你必须检查find的返回值和list的end迭代器是否相等：
if (find(lw.begin(), lw.end(), w) != lw.end()) {
... // 找到了
} else {
... // 没找到
}
如果是为了检查是否存在，count这个惯用法编码起来比较简单。但是，当搜索成功时，它的效率比较低，因
为当找到匹配的值后find就停止了，而count必须继续搜索，直到区间的结尾以寻找其他匹配的值。对大多数
程序员来说，find在效率上的优势足以证明略微增加复杂度是合适的。
通常，只知道区间内是否有某个值是不够的。取而代之的是，你想获得区间中的第一个等于该值的对象。比
如，你可能想打印出这个对象，你可能想在它前面插入什么，或者你可能想要删除它（但当迭代时删除的引
导参见条款9）。当你需要知道的不止是某个值是否存在，而且要知道哪个对象（或哪些对象）拥有该值，
你就得用find：
list<Widget>::iterator i = find(lw.begin(), lw.end(), w);
if (i != lw.end()) {
... // 找到了，i指向第一个
} else {
... // 没有找到
}
对于有序区间，你有其他的选择，而且你应该明确的使用它们。count和find是线性时间的，但有序区间的搜
索算法（binary_search、lower_bound、upper_bound和equal_range）是对数时间的。
从无序区间迁移到有序区间导致了另一个迁移：从使用相等来判断两个值是否相同到使用等价来判断。条款
19由一个详细地讲述了相等和等价的区别，所以我在这里不会重复。取而代之的是，我会简单地说明count和

haoji

find算法都用相等来搜索，而binary_search、lower_bound、upper_bound和equal_range则用等价。
要测试在有序区间中是否存在一个值，使用binary_search。不像标准C库中的（因此也是标准C++库中的）
bsearch，binary_search只返回一个bool：这个值是否找到了。binary_search回答这个问题：“它在吗？”它的
回答只能是是或者否。如果你需要比这样更多的信息，你需要一个不同的算法。
这里有一个binary_search应用于有序vector的例子（你可以从条款23中知道有序vector的优点）：
vector<Widget> vw; // 建立vector，放入
... // 数据，
sort(vw.begin(), vw.end()); // 把数据排序
Widget w; // 要找的值
...
if (binary_search(vw.begin(), vw.end(), w)) {
... // w在vw中
} else {
... // 不在
}
如果你有一个有序区间而且你的问题是：“它在吗，如果是，那么在哪儿？”你就需要equal_range，但你可
能想要用lower_bound。我会很快讨论equal_range，但首先，让我们看看怎么用lower_bound来在区间中定位某
个值。
当你用lower_bound来寻找一个值的时候，它返回一个迭代器，这个迭代器指向这个值的第一个拷贝（如果找
到的话）或者到可以插入这个值的位置（如果没找到）。因此lower_bound回答这个问题：“它在吗？如果
是，第一个拷贝在哪里？如果不是，它将在哪里？”和find一样，你必须测试lower_bound的结果，来看看它
是否指向你要寻找的值。但又不像find，你不能只是检测lower_bound的返回值是否等于end迭代器。取而代之
的是，你必须检测lower_bound所标示出的对象是不是你需要的值。
很多程序员这么用lower_bound：
vector<Widget>::iterator i = lower_bound(vw.begin(), vw.end(), w);
if (i != vw.end() && *i == w) { // 保证i指向一个对象；
// 也就保证了这个对象有正确的值。
// 这是个bug！
... // 找到这个值，i指向
// 第一个等于该值的对象
} else {

haoji

... // 没找到
}
大部分情况下这是行得通的，但不是真的完全正确。再看一遍检测需要的值是否找到的代码：
if (i != vw.end() && *i == w) ...
这是一个相等的测试，但lower_bound搜索用的是等价。大部分情况下，等价测试和相等测试产生的结果相
同，但就像条款19论证的，相等和等价的结果不同的情况并不难见到。在这种情况下，上面的代码就是错
的。
要完全完成，你就必须检测lower_bound返回的迭代器指向的对象的值是否和你要寻找的值等价。你可以手动
完成（条款19演示了你该怎么做，当它值得一做时条款24提供了一个例子），但可以更狡猾地完成，因为你
必须确认使用了和lower_bound使用的相同的比较函数。一般而言，那可以是一个任意的函数（或函数对
象）。如果你传递一个比较函数给lower_bound，你必须确认和你的手写的等价检测代码使用了相同的比较函
数。这意味着如果你改变了你传递给lower_bound的比较函数，你也得对你的等价检测部分作出修改。保持比
较函数同步不是火箭发射，但却是另一个要记住的东西，而且我想你已经有很多需要你记的东西了。
这儿有一个简单的方法：使用equal_range。equal_range返回一对迭代器，第一个等于lower_bound返回的迭代
器，第二个等于upper_bound返回的（也就是，等价于要搜索值区间的末迭代器的下一个）。因此，
equal_range，返回了一对划分出了和你要搜索的值等价的区间的迭代器。一个名字很好的算法，不是吗？
（当然，也许叫equivalent_range会更好，但叫equal_range也非常好。）
对于equal_range的返回值，有两个重要的地方。第一，如果这两个迭代器相同，就意味着对象的区间是空
的；这个只没有找到。这个结果是用equal_range来回答“它在吗？”这个问题的答案。你可以这么用：
vector<Widget> vw;
...
sort(vw.begin(), vw.end());
typedef vector<Widget>::iterator VWIter; // 方便的typedef
typedef pair<VWIter, VWIter> VWIterPair;
VWIterPair p = equal_range(vw.begin(), vw.end(), w);
if (p.first != p.second) { // 如果equal_range不返回
// 空的区间...
... // 说明找到了，p.first指向
// 第一个而p.second
// 指向最后一个的下一个

haoji

} else {
... // 没找到，p.first和
// p.second都指向搜索值
} // 的插入位置
这段代码只用等价，所以总是正确的。
第二个要注意的是equal_range返回的东西是两个迭代器，对它们作distance就等于区间中对象的数目，也就
是，等价于要寻找的值的对象。结果，equal_range不光完成了搜索有序区间的任务，而且完成了计数。比如
说，要在vw中找到等价于w的Widget，然后打印出来有多少这样的Widget存在，你可以这么做：
VWIterPair p = equal_range(vw.begin(), vw.end(), w);
cout << "There are " << distance(p.first, p.second)
<< " elements in vw equivalent to w.";
到目前为止，我们所讨论的都是假设我们要在一个区间内搜索一个值，但是有时候我们更感兴趣于在区间中
寻找一个位置。比如，假设我们有一个Timestamp类和一个Timestamp的vector，它按照老的timestamp放在前面
的方法排序：
class Timestamp { ... };
bool operator<(const Timestamp& lhs, // 返回在时间上lhs
const Timestamp& rhs); // 是否在rhs前面
vector<Timestamp> vt; // 建立vector，填充数据，
... // 排序，使老的时间
sort(vt.begin(), vt.end()); // 在新的前面
现在假设我们有一个特殊的timestamp——ageLimit，而且我们从vt中删除所有比ageLimit老的timestamp。在这
种情况下，我们不需要在vt中搜索和ageLimit等价的Timestamp，因为可能不存在任何等价于这个精确值的元
素。 取而代之的是，我们需要在vt中找到一个位置：第一个不比ageLimit更老的元素。这是再简单不过的了，
因为lower_bound会给我们答案的：
Timestamp ageLimit;
...
vt.erase(vt.begin(), lower_bound(vt.begin(), // 从vt中排除所有
vt.end(), // 排在ageLimit的值
ageLimit)); // 前面的对象

haoji

如果我们的需求稍微改变了一点，我们要排除所有至少和ageLimit一样老的timestamp，也就是我们需要找到
第一个比ageLimit年轻的timestamp的位置。这是一个为upper_bound特制的任务：
vt.erase(vt.begin(), upper_bound(vt.begin(), // 从vt中除去所有
vt.end(), // 排在ageLimit的值前面
ageLimit)); // 或者等价的对象
如果你要把东西插入一个有序区间，而且对象的插入位置是在有序的等价关系下它应该在的地方时，
upper_bound也很有用。比如，你可能有一个有序的Person对象的list，对象按照name排序：
class Person {
public:
...
const string& name() const;
...
};
struct PersonNameLess:
public binary_function<Person, Person, bool> { // 参见条款40
bool operator()(const Person& lhs, const Person& rhs) const
{
return lhs.name() < rhs.name();
}
};
list<Person> lp;
...
lp.sort(PersonNameLess()); // 使用PersonNameLess排序lp
要保持list仍然是我们希望的顺序（按照name，插入后等价的名字仍然按顺序排列），我们可以用
upper_bound来指定插入位置：
Person newPerson;
...
lp.insert(upper_bound(lp.begin(), // 在lp中排在newPerson
lp.end(), // 之前或者等价

haoji

newPerson, // 的最后一个
PersonNameLess()), // 对象后面
newPerson); // 插入newPerson
这工作的很好而且很方便，但很重要的是不要被误导——错误地认为upper_bound的这种用法让我们魔术般
地在一个list里在对数时间内找到了插入位置。我们并没有——条款34解释了因为我们用了list，查找花费线性
时间，但是它只用了对数次的比较。
一直到这里，我都只考虑我们有一对定义了搜索区间的迭代器的情况。通常我们有一个容器，而不是一个区
间。在这种情况下，我们必须区别序列和关联容器。对于标准的序列容器（vector、string、deque和list），你
应该遵循我在本条款提出的建议，使用容器的begin和end迭代器来划分出区间。
这种情况对标准关联容器（set、multiset、map和multimap）来说是不同的，因为它们提供了搜索的成员函
数，它们往往是比用STL算法更好的选择。条款44详细说明了为什么它们是更好的选择，简要地说，是因为
它们更快行为更自然。幸运的是，成员函数通常和相应的算法有同样的名字，所以前面的讨论推荐你使用的
算法count、find、equal_range、lower_bound或upper_bound，在搜索关联容器时你都可以简单的用同名的成员
函数来代替。
调用binary_search的策略不同，因为这个算法没有提供对应的成员函数。要测试在set或map中是否存在某个
值，使用count的惯用方法来对成员进行检测：
set<Widget> s; // 建立set，放入数据
...
Widget w; // w仍然是保存要搜索的值
...
if (s.count(w)) {
... // 存在和w等价的值
} else {
... // 不存在这样的值
}
要测试某个值在multiset或multimap中是否存在，find往往比count好，因为一旦找到等于期望值的单个对象，
find就可以停下了，而count，在最遭的情况下，必须检测容器里的每一个对象。（对于set和map，这不是问
题，因为set不允许重复的值，而map不允许重复的键。）
但是，count给关联容器计数是可靠的。特别，它比调用equal_range然后应用distance到结果迭代器更好。首
先，它更清晰：count 意味着“计数”。第二，它更简单；不用建立一对迭代器然后把它的组成（译注：就

haoji

是first和second）传给distance。第三，它可能更快一点。
要给出所有我们在本条款中所考虑到的，我们的从哪儿着手？下面的表格道出了一切。
你想知道的
使用的算法 使用的成员函数
在无序区间 在有序区间 在set或map上 在multiset或multimap上
期望值是否存在？ find binary_search count find
期望值是否存在？
如果有，第一个等
于这个值的对象在
哪里？
find equal_range find find或lower_bound（参见下面）
第一个不在期望值
之前的对象在哪
里？
find_if lower_bound lower_bound lower_bound
第一个在期望值之
后的对象在哪里？
find_if upper_bound upper_bound upper_bound
有多少对象等于期
望值？
count equal_range，然后distance count count
等于期望值的所有
对象在哪里？
find（迭代） equal_range equal_range equal_range
上表总结了要怎么操作有序区间，equal_range的出现频率可能令人吃惊。当搜索时，这个频率因为等价检测
的重要性而上升了。对于lower_bound和upper_bound，它很容易在相等检测中退却，但对于equal_range，只
检测等价是很自然的。在第二行有序区间，equal_range打败了find还因为一个理由：equal_range花费对数时
间，而find花费线性时间。
对于multiset和multimap，当你在搜索第一个等于特定值的对象的那一行，这个表列出了find和lower_bound两
个算法作为候选。 已对于这个任务find是通常的选择，而且你可能已经注意到在set和map那一列里，这项只
有find。但是对于multi容器，如果不只有一个值存在，find并不保证能识别出容器里的等于给定值的第一个元
素；它只识别这些元素中的一个。如果你真的需要找到等于给定值的第一个元素，你应该使用lower_bound，
而且你必须手动的对第二部分做等价检测，条款19的内容可以帮你确认你已经找到了你要找的值。（你可以
用equal_range来避免作手动等价检测，但是调用equal_range的花费比调用lower_bound多得多。）
在count、find、binary_search、lower_bound、upper_bound和equal_range中做出选择很简单。当你调用时，选
择算法还是成员函数可以给你需要的行为和性能，而且是最少的工作。按照这个建议做（或参考那个表
格），你就不会再有困惑。