📄 item_45.html
字号:
<?xml version="1.0" encoding="gb2312"?><!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><title>条款45：注意count、find、binary_search、lower_bound、upper_bound和equal_range的区别</title><meta http-equiv="Content-Type" content="text/html; charset=gb2312" /><link href="css/all.css" rel="stylesheet" type="text/css" /><link rel="stylesheet" href="http://stl.winterxy.com/styles-site.css" type="text/css" /><link rel="alternate" type="application/rss+xml" title="RSS" href="http://stl.winterxy.com/index.rdf" /><link rel="EditURI" type="application/rsd+xml" title="RSD" href="http://stl.winterxy.com/rsd.xml" /></head><body><div id="banner"><h1><a href="http://stl.winterxy.com/" accesskey="1">Center of STL Study</a> </h1><span class="description">——最优秀的STL学习网站<script language="javascript" src="http://www.winterxy.com/cgi-bin/js/webstats.js"></script></span></div><h2>条款45：注意count、find、binary_search、lower_bound、upper_bound和equal_range的区别</h2> <p>你要寻找什么，而且你有一个容器或者你有一个由迭代器划分出来的区间——你要找的东西就在里面。你要怎么完成搜索呢？你箭袋中的箭有这些：count、count_if、find、find_if、binary_search、lower_bound、upper_bound和equal_range。面对着它们，你要怎么做出选择？</p> <p>简单。你寻找的是能又快又简单的东西。越快越简单的越好。</p> <p>暂时，我假设你有一对指定了搜索区间的迭代器。然后，我会考虑到你有的是一个容器而不是一个区间的情况。</p> <p>要选择搜索策略，必须依赖于你的迭代器是否定义了一个有序区间。如果是，你就可以通过binary_search、lower_bound、upper_bound和equal_range来加速（通常是对数时间——参见<a href="item_34.html">条款34</a>）搜索。如果迭代器并没有划分一个有序区间，你就只能用线性时间的算法count、count_if、find和find_if。在下文中，我会忽略掉count和find是否有_if的不同，就像我会忽略掉binary_search、lower_bound、upper_bound和equal_range是否带有判断式的不同。你是依赖默认的搜索谓词还是指定一个自己的，对选择搜索算法的考虑是一样的。</p> <p>如果你有一个无序区间，你的选择是count或着find。它们分别可以回答略微不同的问题，所以值得仔细去区分它们。count回答的问题是：“是否存在这个值，如果有，那么存在几份拷贝？”而find回答的问题是：“是否存在，如果有，那么它在哪儿？”</p> <p>假设你想知道的东西是，是否有一个特定的Widget值w在list中。如果用count，代码看起来像这样：</p> <pre>list<Widget> lw; // Widget的listWidget w; // 特定的Widget值...if (count(lw.begin(), lw.end(), w)) { ... // w在lw中} else { ... // 不在}</pre> <p>这里示范了一种惯用法：把count用来作为是否存在的检查。count返回零或者一个正数，所以我们把非零转化为true而把零转化为false。如果这样能使我们要做的更加显而易见：</p> <pre>if (count(lw.begin(), lw.end(), w) <span class="highlight">!= 0</span>) ...</pre> <p>而且有些程序员这样写，但是使用隐式转换则更常见，就像最初的例子。</p> <p>和最初的代码比较，使用find略微更难懂些，因为你必须检查find的返回值和list的end迭代器是否相等：</p> <pre>if (<span class="highlight">find</span>(lw.begin(), lw.end(), w) <span class="highlight">!= lw.end()</span>) { ... // 找到了} else { ... // 没找到}</pre> <p>如果是为了检查是否存在，count这个惯用法编码起来比较简单。但是，当搜索成功时，它的效率比较低，因为当找到匹配的值后find就停止了，而count必须继续搜索，直到区间的结尾以寻找其他匹配的值。对大多数程序员来说，find在效率上的优势足以证明略微增加复杂度是合适的。</p> <p>通常，只知道区间内是否有某个值是不够的。取而代之的是，你想获得区间中的第一个等于该值的对象。比如，你可能想打印出这个对象，你可能想在它前面插入什么，或者你可能想要删除它（但当迭代时删除的引导参见<a href="item_09.html">条款9</a>）。当你需要知道的不止是某个值是否存在，而且要知道哪个对象（或哪些对象）拥有该值，你就得用find：</p><pre><span class="highlight">list<Widget>::iterator i = find</span>(lw.begin(), lw.end(), w);<span class="highlight">if (i != lw.end())</span> { ... // 找到了，i指向第一个} else { ... // 没有找到}</pre> <p>对于有序区间，你有其他的选择，而且你应该明确的使用它们。count和find是线性时间的，但有序区间的搜索算法（binary_search、lower_bound、upper_bound和equal_range）是对数时间的。</p> <p>从无序区间迁移到有序区间导致了另一个迁移：从使用相等来判断两个值是否相同到使用等价来判断。<a href="item_19.html">条款19</a>由一个详细地讲述了相等和等价的区别，所以我在这里不会重复。取而代之的是，我会简单地说明count和find算法都用相等来搜索，而binary_search、lower_bound、upper_bound和equal_range则用等价。</p> <p>要测试在有序区间中是否存在一个值，使用binary_search。不像标准C库中的（因此也是标准C++库中的）bsearch，binary_search只返回一个bool：这个值是否找到了。binary_search回答这个问题：“它在吗？”它的回答只能是是或者否。如果你需要比这样更多的信息，你需要一个不同的算法。</p> <p>这里有一个binary_search应用于有序vector的例子（你可以从<a href="item_23.html">条款23</a>中知道有序vector的优点）：</p><pre>vector<Widget> vw; // 建立vector，放入... // 数据，sort(vw.begin(), vw.end()); // 把数据排序Widget w; // 要找的值...if (<span class="highlight">binary_search</span>(vw.begin(), vw.end(), w)) { ... // w在vw中} else { ... // 不在}</pre> <p>如果你有一个有序区间而且你的问题是：“它在吗，如果是，那么在哪儿？”你就需要equal_range，但你可能想要用lower_bound。我会很快讨论equal_range，但首先，让我们看看怎么用lower_bound来在区间中定位某个值。</p> <p>当你用lower_bound来寻找一个值的时候，它返回一个迭代器，这个迭代器指向这个值的第一个拷贝（如果找到的话）或者到可以插入这个值的位置（如果没找到）。因此lower_bound回答这个问题：“它在吗？如果是，第一个拷贝在哪里？如果不是，它将在哪里？”和find一样，你必须测试lower_bound的结果，来看看它是否指向你要寻找的值。但又不像find，你不能只是检测lower_bound的返回值是否等于end迭代器。取而代之的是，你必须检测lower_bound所标示出的对象是不是你需要的值。</p> <p>很多程序员这么用lower_bound：</p><pre><span class="highlight">vector<Widget>::iterator i = lower_bound</span>(vw.begin(), vw.end(), w);<span class="highlight">if (i != vw.end() && *i == w)</span> { // 保证i指向一个对象； // 也就保证了这个对象有正确的值。 // 这是个bug！ ... // 找到这个值，i指向 // 第一个等于该值的对象} else { ... // 没找到}</pre> <p>大部分情况下这是行得通的，但不是真的完全正确。再看一遍检测需要的值是否找到的代码：</p> <pre>if (i != vw.end() && <span class="highlight">*i == w</span>) ...</pre> <p>这是一个<em>相等</em>的测试，但lower_bound搜索用的是<em>等价</em>。大部分情况下，等价测试和相等测试产生的结果相同，但就像<a href="item_19.html">条款19</a>论证的，相等和等价的结果不同的情况并不难见到。在这种情况下，上面的代码就是错的。</p> <p>要完全完成，你就必须检测lower_bound返回的迭代器指向的对象的值是否和你要寻找的值等价。你可以手动完成（<a href="item_19.html">条款19</a>演示了你该怎么做，当它值得一做时<a href="item_24.html">条款24</a>提供了一个例子），但可以更狡猾地完成，因为你必须确认使用了和lower_bound使用的相同的比较函数。一般而言，那可以是一个任意的函数（或函数对象）。如果你传递一个比较函数给lower_bound，你必须确认和你的手写的等价检测代码使用了相同的比较函数。这意味着如果你改变了你传递给lower_bound的比较函数，你也得对你的等价检测部分作出修改。保持比较函数同步不是火箭发射，但却是另一个要记住的东西，而且我想你已经有很多需要你记的东西了。</p> <p>这儿有一个简单的方法：使用equal_range。equal_range返回一对迭代器，第一个等于lower_bound返回的迭代器，第二个等于upper_bound返回的（也就是，等价于要搜索值区间的末迭代器的下一个）。因此，equal_range，返回了一对划分出了和你要搜索的值等价的区间的迭代器。一个名字很好的算法，不是吗？（当然，也许叫equivalent_range会更好，但叫equal_range也非常好。）</p> <p>对于equal_range的返回值，有两个重要的地方。第一，如果这两个迭代器相同，就意味着对象的区间是空的；这个只没有找到。这个结果是用equal_range来回答“它在吗？”这个问题的答案。你可以这么用：</p><pre>vector<Widget> vw;...sort(vw.begin(), vw.end());typedef vector<Widget>::iterator VWIter; // 方便的typedeftypedef pair<VWIter, VWIter> VWIterPair;<span class="highlight">VWIterPair p = equal_range</span>(vw.begin(), vw.end(), w);<span class="highlight">if (p.first != p.second)</span> { // 如果equal_range不返回 // 空的区间... ... // 说明找到了，p.first指向 // 第一个而p.second // 指向最后一个的下一个} else { ... // 没找到，p.first和 // p.second都指向搜索值} // 的插入位置</pre> <p>这段代码只用等价，所以总是正确的。</p> <p>第二个要注意的是equal_range返回的东西是两个迭代器，对它们作distance就等于区间中对象的数目，也就是，等价于要寻找的值的对象。结果，equal_range不光完成了搜索有序区间的任务，而且完成了计数。比如说，要在vw中找到等价于w的Widget，然后打印出来有多少这样的Widget存在，你可以这么做：</p> <pre>VWIterPair p = equal_range(vw.begin(), vw.end(), w);cout << "There are " << <span class="highlight">distance(p.first, p.second)</span> << " elements in vw equivalent to w.";</pre> <p>到目前为止，我们所讨论的都是假设我们要在一个区间内搜索一个值，但是有时候我们更感兴趣于在区间中寻找一个位置。比如，假设我们有一个Timestamp类和一个Timestamp的vector，它按照老的timestamp放在前面的方法排序：</p> <pre>class Timestamp { ... };bool operator<(const Timestamp& lhs, // 返回在时间上lhs const Timestamp& rhs); // 是否在rhs前面vector<Timestamp> vt; // 建立vector，填充数据，... // 排序，使老的时间sort(vt.begin(), vt.end()); // 在新的前面⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -