前言

假设我们需要在一个区间内进行搜寻，并且拥有众多的搜索策略:count、count_if、find、find_if、binary_search、lower_bound、upper_bound和equal_range。

区间的有序性

在查找之前，首先要判断区间的性质，如果是有序区间，可以用binary_search、lower_bound、upper_bound和equal_range，它们消耗对数时间。
如果不是，那你只能用线性时间的算法count、count_if、find和find_if。

无序区间

如果你已经选择了find或者count，要明白它们针对的问题并不相同。

count回答的问题是“是否存在，如果有，则存在几份”
find则回答“是否存在，如果有，它在哪儿”

问题实例

如果你想知道是否有一个特定的Widget值w在list中。
使用count的代码大概如下所示：

1
2
3

list<Widget> lw; 
Widget w;//被搜索物
if (count(lw.begin(), lw.end(), w))//true则存在

如果使用find，则代码大致如下：

1	if (find(lw.begin(), lw.end(), w) != lw.end())//true则存在

count在这里的效率要低于find，因为find一旦找到就终止算法，而count则一直搜索到结尾。同时，find能够提供对象所在的位置，这也是count做不到的。

有序区间

对于有序区间，查找的效率得到了提高。但是因此导致了另一个问题，判同由相等变为了等价。别忘了，count和find算法都用相等来搜索，而binary_search、lower_bound、upper_bound和equal_range则基于等价。

binary_search只返回bool，也就是说，它只能告诉你某个值是否存在于区间内，如果你需要其具体的位置，那我们得使用equal_range，或者lower_bound。

lower_bound

lower_bound在寻找时返回一个迭代器，它往往指向该值的第一个copy或者可以插入该值的位置，具体使用方略如下：

auto i = lower_bound(vw.begin(), vw.end(), w);
if (i != vw.end() && *i == w) {//存在bug
    ...
} 
else {
    ...
}

bug在于lower_bound使用等价判定，而非相等判定。尽管在大多数情况下他们确实是一致的，但正如Effective STL 19所指出的那样，总有例外。

equal_range

equal_range是一个非常好用的算法，它返回一对迭代器，第一个等于lower_bound返回的，第二个等于upper_bound返回的。因此，它返回了与你要搜索的值等价的区间。使用方略如下：

vector<Widget> vw;
sort(vw.begin(), vw.end());
typedef vector<Widget>::iterator VWIter;
typedef pair<VWIter, VWIter> VWIterPair;
VWIterPair p = equal_range(vw.begin(), vw.end(), w);
if (p.first != p.second) {
    ...//找到了，且p.first指向第一个
} 
else {
    ...//不在区间内，不过找到了合适的插入位置
}

另外，对这两个迭代器作distance得到的就是count的功能。

寻找位置

之前一直假设任务为在区间中搜索某个特定值，但有时候我们更感兴趣于在区间中寻找一个位置。

问题实例

假设我们有一个TimeStamp类与一个存储它的vector，它的排序方式是老的在新的前面：

class Timestamp { ... };
bool operator<(const Timestamp& lhs,const Timestamp& rhs); //按照时间比较
vector<Timestamp> vt; 
sort(vt.begin(), vt.end());

现在我们有一个特殊的TimeStamp对象——ageLimit，而且我们需要从vt中删除所有比ageLimit老的TimeStamp。

解决方案

在这种情况下，我们不需要在vt中搜索和ageLimit等价的Timestamp，因为可能不存在任何等价于这个精确值的元素。取而代之的是，我们需要在vt中找到一个位置：第一个不比ageLimit更老的元素。那无疑应当使用lower_bound.
那如果是删除所有至少和agelimit一样大的呢？那无疑是使用upper_bound.

总结

我们可以根据下表来判断何时使用何种查找算法：
image_1cbiseq7rd1919oe1s6a9pf1sjg9.png-114.4kB