|
????????前情提示：我个人认为本条款Term45是《Effective STL》这本书中最重要的其中一个term！它不仅告诉我们如标题所述的几种算法的具体使用的规范，还提醒我们，应该如何在使用STL容器时do规范的查找操作！
????????假设我有一个容器，或者有一对迭代器标识了一个区间，now你希望在容器or区间中查找一些信息，这样的查找工作该如何进行呢？你的选择往往是：count、count_if、find、find_if、binary_search、lower_bound、upper_bound及equal_range。你究竟该如何选择呢？
????????case1：区间被排过序时，建议你优先选择binary_search、lower_bound、upper_bound及equal_range，因为这样会获得更快的查找速度。
????????case2：区间没有被排过序时，建议你优先选择count、count_if、find、find_if。（若不这么选择，那么你得先sort（），然后再像case1那样去使用binary_search、lower_bound、upper_bound及equal_range这几个算法也是可以的，只不过效率较低而已！）
下面我直接用测试代码对这几种查找算法予以讨论！
test_codes：（请仔细耐心地reading）
#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<functional>
#include<list>
using namespace std;
struct myPred :public binary_function<Widget, Widget,bool> {
bool operator()(const Widget& w1, const Widget& w2)const {
return w1.getWeight() < w2.getWeight();
}
};
struct Widget {
private:
double m_weight;
public:
Widget(double mw=0.0):m_weight(mw){}
double getWeight() const{ return m_weight; }
bool operator==(const Widget& w)const {
return w.getWeight() == this->getWeight();
}
};
int main(void) {
list<Widget> lw{ Widget(2.38),Widget(8.38) };
Widget w(2.381);
if (count(lw.begin(), lw.end(),w)!=0) {//用count做存在性的测试！！！
cout << "w在lw中！" << endl;
}
else {
cout << "w不在lw中！" << endl;
}
if (find(lw.begin(), lw.end(), w) != lw.end()) {
cout << "w在lw中！" << endl;//并且，这里find返回的是第一个满足条件的对象的iterator！
}
else {
cout << "w不在lw中！" << endl;
}
vector<Widget> vw{ Widget(2.38),Widget(8.38) };
Widget w2(2.38);
sort(vw.begin(), vw.end(),myPred());
//注意！这里使用sort算法和binary_search算法的函数调用中都必须是同一个Pred！否则编译通过不了！
if (binary_search(vw.begin(), vw.end(), w2, myPred())) {
cout << "w2在vw中！" << endl;
}
else {
cout << "w2不在vw中！" << endl;
}
//binary_search() 算法函数：回答的是-该容器区间中 是否 存在 这样一个给定的value的elem
//lower_bound() 算法函数：回答的是-该值在容器区间中吗？如果在，它的第一份拷贝在哪里？
//如果不在，它该往哪里插入呢？
//注意：与find算法函数一样的是，你必须测试lower_bound的结果，以便判断它是否指向你要找的值
//与find不一样的是，你不能用end()迭代器来测试lower_bound的返回值。
//相反，你必须测试你的lower_bound的返回值所标识的对象，以便判断该对象是否具有你想要找的值！
//许多程序员会按照如下方式来使用lower_bound：
auto it = lower_bound(vw.begin(), vw.end(), w2, myPred());
if (it != vw.end() && *it == w2) {//×！！！
//确保it指向一个对象，并且确保该对象有正确的值
//if找到该值，则it指向第一个具有该值的对象！
}
else {
//没有找到
}
//虽然在大部分case下这段代码可以正常工作，但这段代码是错误的！
//正确的做法是你必须检查lower_bound返回的迭代器所指向的对象是否等价于你要查找的值！
//（当然,所用的Pred也必须保持一致！）
auto it = lower_bound(vw.begin(), vw.end(), w2, myPred());
if (*it == w2) {//√！！！
//确保it指向一个对象，并且确保该对象有正确的值
//if找到该值，则it指向第一个具有该值的对象！
}
else {
//没有找到
}
//有一种比上述算法函数更加简单的算法函数，可以用于排序了的区间查找某个给定值
//equal_range()：返回一个迭代器对组（pair<iterator1,iterator2> ）
//iterator1 返回 == lower_bound返回的迭代器（即指向该区间中与所查找的值等价的第一个元素的位置）
//iterator2 返回 == upper_bound返回的迭代器（即指向该区间中与所查找的值等价的最后一个元素的下一个位置）
//if找不到，则iterator1和iterator2都指向w的（合适的）插入位置
//so equal_range()返回的这一对迭代器标识了一个子区间，其中的值与你所查找的值等价。
//关于该算法函数的返回值 有2个需要注意的地方：
//注意1-如果返回的2个迭代器相同，则表明查找所得到的对象区间为空，即没有找到这样的值
//这对于使用equal_range来回答“是否存在这样的值”是非常关键的！
vector<Widget> vw2{ Widget(2.38),Widget(8.38) };
Widget w3(2.38);
sort(vw2.begin(), vw2.end(), myPred());
//注意！这里使用sort算法和binary_search算法的函数调用中都必须是同一个Pred！否则编译通过不了！
auto IterPair = equal_range(vw2.begin(), vw2.end(), w3, myPred());
if (IterPair.first == IterPair.second) {
cout << "w2不在vw中！" << endl;//如果equal_range沒有找到所要查找的特定值
//pair.first 和 pair.second 都指向w的插入位置
}
else {
cout << "w2不在vw中！" << endl;//非空区间，则表明找到了特定值，
//此时pair.first指向第一个与特定值等价的对象，pair.second指向最后一个与特定值等价的下一个位置
}
//注意2- equal_range()所返回的迭代器 之间的距离 与这个区间中的 对象数目 是相等的。
//so，可以这么说，对于排了序的容器区间来讲，equal_range不仅仅完成了find的工作，还完成了count的工作！
vector<Widget> vw3{ Widget(2.38),Widget(8.38),Widget(2.38),Widget(2.38) };
Widget w4(2.38);
sort(vw3.begin(), vw3.end(), myPred());
auto VWIterPair = equal_range(vw3.begin(), vw3.end(), w4, myPred());
cout << "There are " << distance(VWIterPair.first, VWIterPair.second) <<
" elements in vw3 equivalent to w4." << endl;
return 0;
}
总结：
????????①binary_search() 算法函数：回答的是-该容器区间中 是否 存在 这样一个给定的value的elem，该函数返回值是true（存在） or false（不存在）。
????????②lower_bound() 算法函数：回答的是-该值在容器区间中吗？如果在，它的第一份拷贝在哪里？
如果不在，它该往哪里插入呢？该函数的返回值是指向该值等于给定值的第一份拷贝的迭代器（存在）or指向一个合适的插入给定值target对象到该容器中的位置的迭代器（注意，这里不一定是container.end()！不要乱来！）。
? ? ? ? ---注意：与find算法函数一样的是，你必须测试lower_bound的结果，以便判断它是否指向你要找的值。与find不一样的是，你不能用end()迭代器来测试lower_bound的返回值。相反，你必须测试你的lower_bound的返回值所标识的对象，以便判断该对象是否具有你想要找的值！
????????③upper_bound() 算法函数：回答的是-该值在容器区间中吗？如果在，它的最后一份拷贝的下一个位置在哪里？如果不在，它该往哪里插入呢？该函数的返回值是指向该值等于给定值的最后一份拷贝的下一个位置的迭代器（存在）or指向一个合适的插入给定值target对象到该容器中的位置的迭代器（注意，这里不一定是container.end()！不要乱来！）。
????????④equal_range()算法函数（比用上述算法来查找给定value的elem更好，推荐查找时使用！）：可以用于在排序了的区间中查找某个给定值。该函数返回一个迭代器对组（pair<iterator1,iterator2> ）
? ? ? ? ---iterator1 返回 == lower_bound返回的迭代器（即指向该区间中与所查找的值等价的第一个元素的位置）
????????---iterator2 返回 == upper_bound返回的迭代器（即指向该区间中与所查找的值等价的最后一个元素的下一个位置）
????????---if找不到，则iterator1和iterator2都指向w的（合适的）插入位置，且这个合适的位置是由该算法函数本书来找的，不是我们自定义的。
????????⑤对于标准序列式（Sequence Containers）容器（vector，string，deque，list）而言，使用通用的STL算法count、count_if、find、find_if、binary_search、lower_bound、upper_bound及equal_range来do查找操作。
? ? ? ? ⑥对于标准关联式（Associative Containers）容器（map/multimap，set/multiset，unordered_map，unordered_set）而言，则使用该容器本身的成员函数.count()、.find()、.lower_bound()、.upper_bound()及.equal_range()来do查找操作。
? ? ? ? 注意：这些与通用STL查找算法同名的成员函数往往比前者要好！（Effective STL Term44说明了，容器的成员函数往往比通用同名的STL算法好！）简而言之，即这些成语函数代码的执行速度更快！使用方便，行为方式也更自然！
|