- 正确区分不同的查找算法count,find,binary_search,lower_bound,upper_bound,equal_range 本文是对Effective STL第45条的一个总结，阐述了各种查找算法的异同以及使用他们的时机。
- 首先可供查找的算法大致有count,find,binary_search,lower_bound,upper_bound,equal_range。带有判别式的如count_if,find_if或者binary_search的派别式版本，其用法大致相同，不影响选择
可以按是否需要排序区间分为两组: A. count,find B. binary_search,lower_bound,upper_bound,equal_range A组不需排序区间， B组需要排序区间。当一个区间被排序，优先选择B组，因为他们提供对数时间的效率。而A则是线性时间。
另外A组B组所依赖的查找判断法则不同，A使用相等性法则(查找对象需要定义operator==), B使用等价性法则(查找对象需要定义operator<,必须在相等时返回false)。
如果在C++ STL容器中包含了有序的序列，STL提供了四个函数进行搜索，他们是利用二分查找实现的(Binary search).其中：假定相同值的元素可能有多个 lower_bound 返回第一个符合条件的元素位置 upper_bound 返回最后一个符合条件的元素位置 equal_range 返回所有等于指定值的头/尾元素的位置，其实就是lower_bound和upper_bound binary_search 返回是否有需要查找的元素。
- 转换主要是使用stl中的advance和distance函数来进行的，advance是将iterator移动指定个元素，distance是计算两个iterator直接的距离。distance计算第一个参数到第二个参数之间的距离。如果第二个参数的顺序在第一个参数前面的话,函数是会返回负值的；如果迭代器不在一个容器内,程序会抛出异常。advance是将第一个参数向后移动第二个参数指定个元素。如果第二个参数为负,则向前移动；如果向前或向后移动超出容器范围,则抛出异常。
#include#include#includeusing namespace std;int main (){ list mylist; for (int i=0; i<10; i++) mylist.push_back (i*10.0); list::iterator first = mylist.begin(); list::iterator last = mylist.end(); advance(first, 1); cout << "The distance is: " << distance(first,last) << endl; return 0;}
（1）STL中关于二分查找的函数有三个：lower_bound 、upper_bound 、binary_search —— 这三个函数都运用于有序区间（当然这也是运用二分查找的前提），下面记录一下这两个函数；
（2）ForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)算法返回一个非递减序列[first, last)中的第一个大于等于值val的位置；
（3）ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val)算法返回一个非递减序列[first, last)中的第一个大于值val的位置。
二：lower_bound和upper_bound如下图所示：
| 你想知道的 | 在无序区间 | 在有序区间 | 在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
|