item_45.html

制作本书的目的是为了方便大家的阅读。转载时请保持本电子书的完整性。 前言、条款2、16、21、44根据从Addison-Wesley出版社下载的开放条款翻译。条款26、27、28、45根据从Sc

</pre> 
<p>现在假设我们有一个特殊的timestamp——ageLimit，而且我们从vt中删除所有比ageLimit老的timestamp。在这种情况下，我们不需要在vt中搜索和ageLimit等价的Timestamp，因为可能不存在任何等价于这个精确值的元素。 取而代之的是，我们需要在vt中找到一个位置：第一个不比ageLimit更老的元素。这是再简单不过的了，因为lower_bound会给我们答案的：</p> 
<pre>
Timestamp ageLimit;
...
vt.erase(vt.begin(), <span class="highlight">lower_bound</span>(vt.begin(),	// 从vt中排除所有
	vt.end(),				// 排在ageLimit的值
	ageLimit));			// 前面的对象
</pre> 
<p>如果我们的需求稍微改变了一点，我们要排除所有至少和ageLimit一样老的timestamp，也就是我们需要找到第一个比ageLimit年轻的timestamp的位置。这是一个为upper_bound特制的任务：</p> 
<pre>
vt.erase(vt.begin(), <span class="highlight">upper_bound</span>(vt.begin(),	// 从vt中除去所有
	vt.end(),				// 排在ageLimit的值前面
	ageLimit));			// 或者等价的对象
</pre> 
<p>如果你要把东西插入一个有序区间，而且对象的插入位置是在有序的等价关系下它应该在的地方时，upper_bound也很有用。比如，你可能有一个有序的Person对象的list，对象按照name排序：</p> 
<pre>
class Person {
public:
	...
	const string&amp; name() const;
	...
};

struct PersonNameLess:
public binary_function&lt;Person, Person, bool&gt; {	// 参见<a href="item_40.html">条款40</a>
	bool operator()(const Person&amp; lhs, const Person&amp; rhs) const
	{
		return lhs.name() &lt; rhs.name();
	}
};

list&lt;Person&gt; lp;
...
lp.sort(PersonNameLess());			// 使用PersonNameLess排序lp
</pre> 
<p>要保持list仍然是我们希望的顺序（按照name，插入后等价的名字仍然按顺序排列），我们可以用upper_bound来指定插入位置：</p> 
<pre>
Person newPerson;
...
lp.insert(<span class="highlight">upper_bound</span>(lp.begin(),		// 在lp中排在newPerson
	lp.end(),				// 之前或者等价
	newPerson,			// 的最后一个
	PersonNameLess()),			// 对象后面
	newPerson);			// 插入newPerson
</pre> 
<p>这工作的很好而且很方便，但很重要的是不要被误导——错误地认为upper_bound的这种用法让我们魔术般地在一个list里在对数时间内找到了插入位置。我们并没有——<a href="item_34.html">条款34</a>解释了因为我们用了list，查找花费线性时间，但是它只用了对数次的比较。</p> 
<p>一直到这里，我都只考虑我们有一对定义了搜索区间的迭代器的情况。通常我们有一个容器，而不是一个区间。在这种情况下，我们必须区别序列和关联容器。对于标准的序列容器（vector、string、deque和list），你应该遵循我在本条款提出的建议，使用容器的begin和end迭代器来划分出区间。</p> 
<p>这种情况对标准关联容器（set、multiset、map和multimap）来说是不同的，因为它们提供了搜索的成员函数，它们往往是比用STL算法更好的选择。<a href="item_44.html">条款44</a>详细说明了为什么它们是更好的选择，简要地说，是因为它们更快行为更自然。幸运的是，成员函数通常和相应的算法有同样的名字，所以前面的讨论推荐你使用的算法count、find、equal_range、lower_bound或upper_bound，在搜索关联容器时你都可以简单的用同名的成员函数来代替。</p> 
<p>调用binary_search的策略不同，因为这个算法没有提供对应的成员函数。要测试在set或map中是否存在某个值，使用count的惯用方法来对成员进行检测：</p> 
<pre>
set&lt;Widget&gt; s;		// 建立set，放入数据 
...
Widget w;			// w仍然是保存要搜索的值
...
if (<span class="highlight">s.count(w)</span>) {
	...		// 存在和w等价的值
} else {
	...		// 不存在这样的值
}
</pre> 
<p>要测试某个值在multiset或multimap中是否存在，find往往比count好，因为一旦找到等于期望值的单个对象，find就可以停下了，而count，在最遭的情况下，必须检测容器里的每一个对象。（对于set和map，这不是问题，因为set不允许重复的值，而map不允许重复的键。）</p> 
<p>但是，count给关联容器计数是可靠的。特别，它比调用equal_range然后应用distance到结果迭代器更好。首先，它更清晰：count 意味着“计数”。第二，它更简单；不用建立一对迭代器然后把它的组成<strong>（译注：就是first和second）</strong>传给distance。第三，它可能更快一点。</p> 
<p>要给出所有我们在本条款中所考虑到的，我们的从哪儿着手？下面的表格道出了一切。</p> 
<table cellpadding="2"> 
	<tr> 
		<th rowspan="2">你想知道的</th> 
		<th colspan="2">使用的算法</th> 
		<th colspan="2">使用的成员函数</th> 
	</tr> 
	<tr> 
		<td>在无序区间</td> 
		<td>在有序区间</td> 
		<td>在set或map上</td> 
		<td>在multiset或multimap上</td> 
	</tr> 
	<tr> 
		<td>期望值是否存在？</td> 
		<td>find</td> 
		<td>binary_search</td> 
		<td>count</td> 
		<td>find</td> 
	</tr> 
	<tr> 
		<td>期望值是否存在？如果有，第一个等于这个值的对象在哪里？</td> 
		<td>find</td> 
		<td>equal_range</td> 
		<td>find</td> 
		<td>find或lower_bound（参见下面）</td> 
	</tr> 
	<tr> 
		<td>第一个不在期望值之前的对象在哪里？</td> 
		<td>find_if</td> 
		<td>lower_bound</td> 
		<td>lower_bound</td> 
		<td>lower_bound</td> 
	</tr> 
	<tr> 
		<td>第一个在期望值之后的对象在哪里？</td> 
		<td>find_if</td> 
		<td>upper_bound</td> 
		<td>upper_bound</td> 
		<td>upper_bound</td> 
	</tr> 
	<tr> 
		<td>有多少对象等于期望值？</td> 
		<td>count</td> 
		<td>equal_range，然后distance</td> 
		<td>count</td> 
		<td>count</td> 
	</tr> 
	<tr> 
		<td> 等于期望值的所有对象在哪里？</td> 
		<td>find（迭代）</td> 
		<td>equal_range</td> 
		<td>equal_range</td> 
		<td>equal_range</td> 
	</tr> 
</table> 
<p>上表总结了要怎么操作有序区间，equal_range的出现频率可能令人吃惊。当搜索时，这个频率因为等价检测的重要性而上升了。对于lower_bound和upper_bound，它很容易在相等检测中退却，但对于equal_range，只检测等价是很自然的。在第二行有序区间，equal_range打败了find还因为一个理由：equal_range花费对数时间，而find花费线性时间。</p> 
<p>对于multiset和multimap，当你在搜索第一个等于特定值的对象的那一行，这个表列出了find和lower_bound两个算法作为候选。 已对于这个任务find是通常的选择，而且你可能已经注意到在set和map那一列里，这项只有find。但是对于multi容器，如果不只有一个值存在，find并不保证能识别出容器里的等于给定值的第一个元素；它只识别这些元素中的一个。如果你真的需要找到等于给定值的第一个元素，你应该使用lower_bound，而且你必须手动的对第二部分做等价检测，<a href="item_19.html">条款19</a>的内容可以帮你确认你已经找到了你要找的值。（你可以用equal_range来避免作手动等价检测，但是调用equal_range的花费比调用lower_bound多得多。）</p> 
<p>在count、find、binary_search、lower_bound、upper_bound和equal_range中做出选择很简单。当你调用时，选择算法还是成员函数可以给你需要的行为和性能，而且是最少的工作。按照这个建议做（或参考那个表格），你就不会再有困惑。</p> 
</body>
</html>