Effective STL之在程序中使用STL-摩杜云开发者社区

一、用纯函数做判断式

先介绍两个概念–“纯函数”与“判别式”：

纯函数是返回值只依赖于参数的函数。如果f是一个纯函数，x和y是对象，f(x, y)的返回值仅当x或y的值改变的时候才会改变。

判别式是返回bool（或者其他可以隐式转化为bool的东西）。判别式在STL中广泛使用。标准关联容器的比较函数是判断式，判断式函数常常作为参数传递给算法，比如find_if和多种排序算法。

判别式类是仿函数类，它的operator()函数是一个判断式，也就是，它的operator()返回true或false（或其他可以隐式转换到true或false的东西）。
【Note】：
（1）判别式函数必须是纯函数。

二、尽量用算法调用代替手写循环

本条款将证明调用算法通常比手写的循环更优越，有三个理由：

效率：算法通常比程序员产生的循环更高效。
正确性：写循环时比调用算法更容易产生错误。
可维护性：算法通常使代码比相应的显式循环更干净、更直观。

#include <bits/stdc++.h>
using namespace std;
class A {  
public:  
  A(int x=0): val(x) {}  
  void print() { cout << val << " "; }  
private:  
  int val;  
};  
int main(int argc, char const *argv[])
{
    vector<A> vec = {A(1), A(2)};
    for_each(vec.begin(), vec.end(), [](A &a){a.print();});
    return 0;
}

三、尽量用成员函数代替同名的算法

有些容器拥有和STL算法同名的成员函数。关联容器提供了count、find、lower_bound、upper_bound和 equal_range，而list提供了remove、remove_if、unique、sort、merge和reverse。大多数情况下，应该用成员函数代替算法。这样做有两个理由：

成员函数更快；
比起算法来，它们与容器结合得更好（尤其是关联容器）

【Note】：
（1）当面临着STL算法和同名的容器成员函数间进行选择时，你应该尽量使用成员函数。几乎可以肯定它更高效，而且它看起来也和容器的惯常行为集成得更好。

四、注意count、find、binary_search、lower_bound、upper_bound和equal_range的区别

你要寻找什么，而且你有一个容器或者你有一个由迭代器划分出来的区间——你要找的东西就在里面。你要怎么完成搜索呢？你箭袋中的箭有这些：count、count_if、find、find_if、binary_search、lower_bound、upper_bound和equal_range。面对着它们，你要怎么做出选择？

1、count和find

如果你有一个无序区间，你的选择是count或着find。它们分别可以回答略微不同的问题，所以值得仔细去区分它们。count回答的问题是：是否存在这个值，如果有，那么存在几份拷贝？”“而find回答的问题是：是否存在，如果有，那么它在哪儿？”“

list<Widget> lw;   // Widget的列表
Widget w;         // 特殊的Widget值
...
if (count(lw.begin(), lw.end(), w)) {
 ...    // w在lw中，有多少个
} else {
 ...    // 不在
}

if (find(lw.begin(), lw.end(), w) != lw.end()) {
 ...    // 找到了
} else {
 ...    // 没找到
}

对于已序区间，你有其他的选择，而且你应该明确的使用它们。count和find是线性时间的，但已序区间的搜索算法（binary_search、lower_bound、upper_bound和equal_range）是对数时间的。

2、binary_search

要测试在已序区间中是否存在一个值，使用binary_search。不像标准C库中的（因此也是标准C++库中的）bsearch，binary_search只返回一个bool：这个值是否找到了。binary_search回答这个问题：“它在吗？”它的回答只能是是或者否。如果你需要比这样更多的信息，你需要一个不同的算法。

vector<Widget> vw;   // 建立vector，放入
...                  // 数据，
sort(vw.begin(), vw.end()); // 把数据排序
Widget w;    // 要找的值
...
if (binary_search(vw.begin(), vw.end(), w)) {
 ...    // w在vw中
} else {
 ...    // 不在
}

3、lower_bound

当你用lower_bound来寻找一个值的时候，它返回一个迭代器，这个迭代器指向这个值的第一个拷贝（如果找到的话）或者到可以插入这个值的位置（如果没找到）。因此lower_bound回答这个问题：“它在吗？如果是，第一个>=查找值拷贝在哪里？如果不是，它将在哪里？”和find一样，你必须测试lower_bound的结果，来看看它是否指向你要寻找的值。但又不像find，你不能只是检测lower_bound的返回值是否等于end迭代器。取而代之的是，你必须检测lower_bound所标示出的对象是不是你需要的值。

vector<Widget>::iterator i = lower_bound(vw.begin(), vw.end(), w);

4、upper_bound

upper_bound回答这个问题：“它在吗？如果是，第一个>查找值的拷贝在哪里？如果不是，它将在哪里？”

vector<Widget>::iterator i = lower_bound(vw.begin(), vw.end(), w);

5、equal_range

equal_range返回一对迭代器，第一个等于lower_bound返回的迭代器，第二个等于upper_bound返回的（也就是，等价于要搜索值区间的末迭代器的下一个）。因此，equal_range返回了一对划分出了和你要搜索的值等价的区间的迭代器。一个名字很好的算法，不是吗？

vector<Widget> vw;
...
sort(vw.begin(), vw.end());
typedef vector<Widget>::iterator VWIter; // 方便的typedef
typedef pair<VWIter, VWIter> VWIterPair;
VWIterPair p = equal_range(vw.begin(), vw.end(), w);
if (p.first != p.second) {   // 如果equal_range不返回
      // 空的区间...
 ...     // 说明找到了，p.first指向
      // 第一个而p.second
      // 指向最后一个的下一个
} else {
 ...     // 没找到，p.first和
      // p.second都指向搜索值
}      // 的插入位置

//distance用于计算区间中对象的数目
cout << "There are " << distance(p.first, p.second)
<< " elements in vw equivalent to w.";

6、总结

Effective STL之在程序中使用STL_迭代器

五、考虑使用函数对象代替函数作算法的参数

一般我们都会这样认为，用高级语言编程时抽象层次越高，产生的代码效率就越低。这在很多情况下都是事实，Alexander Stepano (STL的发明者) 有一次作了一组小测试，试图测量出相对于C而言，C++的“抽象惩罚”:

假设你需要以降序排序一个double的vector。最直接的STL方式是通过sort算法和greater类型的函数对象：

vector<double> v;
//...初始化V
sort(v.begin(), v.end(), greater<double>());

如果你注意了抽象惩罚，你可能决定避开函数对象而使用真的函数，它可能不只是简单意义上的一个函数，而且是内联的函数：

inline
bool doubleGreater(double d1, double d2)
{
    return d1 > d2;
}
//...
sort(v.begin(), v.end(), doubleGreater);

但是仿函数竟然比内联的真正函数快了4倍。这个行为的解释很简单：内联。如果一个函数对象的operator()函数被声明为内联（不管显式地通过inline或者隐式地通过定义在它的类定义中），编译器就可以获得那个函数的函数体，而且大部分编译器喜欢在调用算法的模板实例化时内联那个函数。在上面的例子中，greater::operator()是一个真正的内联函数，所以编译器在实例化sort时内联展开它。结果，sort没有包含一次函数调用，而且编译器可以对这个没有调用操作的代码进行其他情况下不经常进行的优化。

使用doubleGreater调用sort的情况则不同。要知道有什么不同，我们必须知道不可能把一个函数作为参数传给另一个函数。当我们试图把一个函数作为参数时，编译器默默地把函数转化为一个指向那个函数的指针，而那个指针是我们真正传递的。所以每次在sort中用到时，编译器产生一个间接函数调用——通过指针调用。大部分编译器不会试图去内联通过函数指针调用的函数。