GeekBand STL与泛型编程 Second Week

STL 整体结构

STL 主要是有六大主要的部件构成。

容器
分配器
算法
迭代器
适配器
仿函数

#include<vector>
#include<algorithm>
#include<functional>
#include<iostream>

using namespace std;

int main()
{
    int ia[6] = { 1, 2, 3};
    vector<int, allocator<int> > v(ia, ia+6);
    
    cout << count_if(v.begin(), v.end(), not1(bind2nd(less<int>(), 2)));
    
    return 0;
}
// 这其中包含了 容器 vector， 分配器 allocator， 迭代器 v.begin(), 算法 count_if, functor less<int>, adapter not1, bind2nd.

仿函数

仿函数是STL中非常重要的一部分。仿函数又称函数对象，齐最用相当于一个函数指针。它是重载了 operator() 的对象，从而使得仿函数可以像函数一样被调用。

STL中使用仿函数来代替诸如C中的函数指针，是因为普通的函数指针不能满足STL的抽象要求，且函数指针无法和其他STL的组件交互。

同时仿函数可作为模版实参用于定义对象的某种默认行为。比如以某种顺序对于元素进行排序的容器，排序规则就是一个模版实参。

// std::set
template<typename _Ky, typename _Pr = less<_Ky> >
class set {
...
};

// set 默认以less 作为元素的排序行为。如果两个set具有不同的排序规则，那么对他们的进行赋值和比较判断会导致错误。

仿函数适配器－bind1st/bind2st , mem_fun/mem_fun_ref && C++11 functio, bind && lambda

仿函数适配器(Functor adapter),目的在于将无法匹配的仿函数 “套结” 成可以匹配的类型。

mem_fun 和 mem_fun_ref 用来适配对象的成员函数

重点说下 mem_fun
看如下代码

class Person
{
public:
    void Print()
    {
        wcout<< id << name << endl;
    }
private:
    int id;
    wstring name;
};

vector<Person*> v;
v.push_back(new Person(1, L"AA"));
v.push_back(new Person(1, L"BB"));
v.push_back(new Person(1, L"BB"));

// 如果要使用for_each 遍历
for_each(v.begin(), v.end(), &Person::Print) // 这个是无法通过编译的

// for_each 的定义如下
template<class _It, class _Fn1>
inline void for_each(_It _First, _It _Last, _Fn1& _Func)
{
    for(; _First != _Last; ++_First)
        _Func(*_First)
}
// 这里的 _Func是一个函数指针或者是仿函数， 而 &Person::Print 的类型是一个类成员函数指针，它的调用方式是 (*_First).*Func(), 和for_each 中的调用不符。所以需要通过仿函数适配器来解决。

template<class _Result, class _Ty> 
inline mem_fun_t<_Result, _Ty> mem_fun(_Result (_Ty::*_pm)())
{
    return (mem_fun_t<_Result, _Ty> (_pm));
}

template<class _Result, class _Ty>
class mem_fun_t : public unary_function<_Ty *, _Result>
{
public:
    explict mem_fun_t(_Result (_Ty::*pm)()) : _pmemfun(_pm) 
    {
    }
    
    _Result operator()(_Ty *_pleft) const
    {
        return ((_pleft->*_pmemfun)());
    }
private:
    _Result (_Ty::*_pmemfun)();
};

// 可以如下写
for_each(v.begin(), v.end(), mem_fun(&Person::print));

// 可以看到 &Person::print 是符合 mem_fun的定义，men_fun 本身是仿函数，也符合 for_each 的定义。 所以这里mem_fun 起了一个适配器的作用，把本身不符合算法接口的参数封装成符合算法接口的参数。

C++11中新增的lambda表达式, function对象和bind机制。之所以把这三块放在一起讲，是因为这三块之间有着非常密切的关系，通过对比学习，加深对这部分内容的理解。在开始之间，首先要讲一个概念，closure（闭包），这个概念是理解lambda的基础。下面我们来看看wikipedia上对于计算机领域的closure的定义：

A closure (also lexical closure, function closure or function value) is a function together witha referencing environment for the non-local variables of that function.

上面的大义是说，closure是一个函数和它所引用的非本地变量的上下文环境的集合。从定义我们可以得知，closure可以访问在它定义范围之外的变量，也即上面提到的non-local vriables，这就大大增加了它的功力。关于closure的最重要的应用就是回调函数，这也是为什么这里把function, bind和lambda放在一起讲的主要原因，它们三者在使用回调函数的过程中各显神通。下面就为大家一步步接开这三者的神秘面纱。

1. function 我们知道，在C++中，可调用实体主要包括函数，函数指针，函数引用，可以隐式转换为函数指定的对象，或者实现了opetator()的对象（即C++98中的functor)。C++0x中，新增加了一个std::function对象，std::function对象是对C++中现有的可调用实体的一种类型安全的包裹（我们知道像函数指针这类可调用实体，是类型不安全的）。我们来看几个关于function对象的例子：

#include < functional>
 
std::function< size_t (const char*) > print_func;
 
/// normal function -> std::function object
size_t CPrint(const char*) { ... }
print_func = CPrint;
print_func("hello world"):
 
/// functor -> std::function object
class CxxPrint
{
public:
    size_t operator()(const char*) { ... }
};
CxxPrint p;
print_func = p;
print_func("hello world");

在上面的例子中，我们把一个普通的函数和一个functor赋值给了一个std::function对象，然后我们通过该对象来调用。其它的C++中的可调用实体都可以像上面一样来使用。通过std::function的包裹，我们可以像传递普通的对象一样来传递可调用实体，这样就很好解决了类型安全的问题。了解了std::function的基本用法，下面我们来看一些使用过程中的注意事项：

（1）关于可调用实体转换为std::function对象需要遵守以下两条原则：
a. 转换后的std::function对象的参数能转换为可调用实体的参数
b. 可高用实体的返回值能转换为std::function对象的（这里注意，所有的可调用实体的返回值都与返回void的std::function对象的返回值兼容）。
（2）std::function对象可以refer to满足（1）中条件的任意可调用实体
（3）std::function object最大的用处就是在实现函数回调，使用者需要注意，它不能被用来检查相等或者不相等

2. bind bind是这样一种机制，它可以预先把指定可调用实体的某些参数绑定到已有的变量，产生一个新的可调用实体，这种机制在回调函数的使用过程中也颇为有用。C++98中，有两个函数bind1st和bind2nd，它们分别可以用来绑定functor的第一个和第二个参数，它们都是只可以绑定一个参数。各种限制，使得bind1st和bind2nd的可用性大大降低。C++0x中，提供了std::bind，它绑定的参数的个数不受限制，绑定的具体哪些参数也不受限制，由用户指定，这个bind才是真正意义上的绑定，有了它，bind1st和bind2nd就没啥用武之地了，因此C++0x中不推荐使用bind1st和bind2nd了，都是deprecated了。下面我们通过例子，来看看bind的用法：

#include < functional>
 
int Func(int x, int y);
auto bf1 = std::bind(Func, 10, std::placeholders::_1);
bf1(20); ///< same as Func(10, 20)
 
class A
{
public:
    int Func(int x, int y);
};
 
A a;
auto bf2 = std::bind(&A::Func, a, std::placeholders::_1, std::placeholders::_2);
bf2(10, 20); ///< same as a.Func(10, 20)
 
std::function< int(int)> bf3 = std::bind(&A::Func, a, std::placeholders::_1, 100);
bf3(10); ///< same as a.Func(10, 100)

上面的例子中，bf1是把一个两个参数普通函数的第一个参数绑定为10，生成了一个新的一个参数的可调用实体体; bf2是把一个类成员函数绑定了类对象，生成了一个像普通函数一样的新的可调用实体; bf3是把类成员函数绑定了类对象和第二个参数，生成了一个新的std::function对象。看懂了上面的例子，下面我们来说说使用bind需要注意的一些事项：

（1）bind预先绑定的参数需要传具体的变量或值进去，对于预先绑定的参数，是pass-by-value的
（2）对于不事先绑定的参数，需要传std::placeholders进去，从_1开始，依次递增。placeholder是pass-by-reference的
（3）bind的返回值是可调用实体，可以直接赋给std::function对象
（4）对于绑定的指针、引用类型的参数，使用者需要保证在可调用实体调用之前，这些参数是可用的
（5）类的this可以通过对象或者指针来绑定

3. lambda 讲完了function和bind, 下面我们来看lambda。看到这里的朋友，请再回忆一下前面讲的closure的概念，lambda就是用来实现closure的东东。它的最大用途也是在回调函数，它和前面讲的function和bind有着千丝万缕的关系。下面我们先通过例子来看看lambda的庐山真面目：

vector< int> vec;
/// 1. simple lambda
auto it = std::find_if(vec.begin(), vec.end(), [](int i) { return i > 50; });
class A
{
public:
    bool operator(int i) const { return i > 50; }
};
auto it = std::find_if(vec.begin(), vec.end(), A());
 
/// 2. lambda return syntax
std::function< int(int)> square = [](int i) -> int { return i * i; }
 
/// 3. lambda expr: capture of local variable
{
    int min_val = 10;
    int max_val = 1000;
 
    auto it = std::find_if(vec.begin(), vec.end(), [=](int i) {
        return i > min_val && i < max_val; 
        });
 
    auto it = std::find_if(vec.begin(), vec.end(), [&](int i) {
        return i > min_val && i < max_val;
        });
 
    auto it = std::find_if(vec.begin(), vec.end(), [=, &max_value](int i) {
        return i > min_val && i < max_val;
        });
}
 
/// 4. lambda expr: capture of class member
class A
{
public:
    void DoSomething();
 
private:
    std::vector<int>  m_vec;
    int               m_min_val;
    int               m_max_va;
};
 
/// 4.1 capture member by this
void A::DoSomething()
{
    auto it = std::find_if(m_vec.begin(), m_vec.end(), [this](int i){
        return i > m_min_val && i < m_max_val; });
}
 
/// 4.2 capture member by default pass-by-value
void A::DoSomething()
{
    auto it = std::find_if(m_vec.begin(), m_vec.end(), [=](int i){
        return i > m_min_val && i < m_max_val; });
}
 
/// 4.3 capture member by default pass-by-reference
void A::DoSomething()
{
    auto it = std::find_if(m_vec.begin(), m_vec.end(), [&](int i){
        return i > m_min_val && i < m_max_val; });
}

上面的例子基本覆盖到了lambda表达的基本用法。我们一个个来分析每个例子（标号与上面代码注释中1，2，3，4一致）：

（1）这是最简单的lambda表达式，可以认为用了lambda表达式的find_if和下面使用了functor的find_if是等价的
（2）这个是有返回值的lambda表达式，返回值的语法如上面所示，通过->写在参数列表的括号后面。返回值在下面的情况下是可以省略的：a. 返回值是void的时候b. lambda表达式的body中有return expr，且expr的类型与返回值的一样
（3）这个是lambda表达式capture本地局部变量的例子，这里三个小例子，分别是capture时不同的语法，第一个小例子中=表示capture的变量pass-by-value, 第二个小拿出中&表示capture的变量pass-by-reference，第三个小例子是说指定了default的pass-by-value, 但是max_value这个单独pass-by-reference
（4）这个是lambda表达式capture类成员变量的例子，这里也有三个小例子。第一个小例子是通过this指针来capture成员变量，第二、三个是通过缺省的方式，只不过第二个是通过pass-by-value的方式，第三个是通过pass-by-reference的

分析完了上面的例子，我们来总结一下关于lambda表达式使用时的一些注意事项：

（1）lambda表达式要使用引用变量，需要遵守下面的原则：a. 在调用上下文中的局部变量，只有capture了才可以引用（如上面的例子3所示）b. 非本地局部变量可以直接引用
（2）使用者需要注意，closure（lambda表达式生成的可调用实体）引用的变量（主要是指针和引用），在closure调用完成之前，必须保证可用，这一点和上面bind绑定参数之后生成的可调用实体是一致的
（3）关于lambda的用处，就是用来生成closure，而closure也是一种可调用实体，所以可以通过std::function对象来保存生成的closure，也可以直接用auto

通过上面的介绍，我们基本了解了function, bind和lambda的用法，把三者结合起来，C++将会变得非常强大，有点函数式编程的味道了。最后，这里再补充一点，对于用bind来生成function和用lambda表达式来生成function, 通常情况下两种都是ok的，但是在参数多的时候,bind要传入很多的std::placeholders，而且看着没有lambda表达式直观，所以通常建议优先考虑使用lambda表达式。

泛型算法

泛型算法主要分为：

非易变算法
易变算法
排序
泛型数值算法

非易变算法是一系列模版函数，在不改变操作对象的前提下对元素进行处理。诸如：查找，统计，匹配等

具体包括：

for_each

find

find_if

adjacent_find

find_first_of

count

count_if

mismatch

equal

search

1.因为它们实现共同的操作，所以称之为“算法”；而“泛型”指的是它们可以操作在多种容器类型上——不但可作用于vector
或list
这些标准库类型，还可用在内置数组类型、甚至其他类型的序列上，这些我们将在本章的后续内容中了解。自定义的容器类型只要与标准库兼容，同样可以使用这些泛型算法。解算法的最基本方法是了解该算法是否读元素、写元素或者对元素进行重新排序。

2.大多数算法是通过遍历由两个迭代器标记的一段元素来实现其功能。典型情况下，算法在遍历一段元素范围时，操纵其中的每一个元素。算法通过迭代器访问元素，这些迭代器标记了要遍历的元素范围。

3.泛型算法本身从不执行容器操作，只是单独依赖迭代器和迭代器操作实现。算法基于迭代器及其操作实现，而并非基于容器操作。这个事实也许比较意外，但本质上暗示了：使用“普通”的迭代器时，算法从不修改基础容器的大小。正如我们所看到的，算法也许会改变存储在容器中的元素的值，也许会在容器内移动元素，但是，算法从不直接添加或删除元素.算法不直接修改容器的大小。

4.除了少数例外情况，所有算法都在一段范围内的元素上操作，我们将这段范围称为“输出范围（input range）”。带有输入范围参数的算法总是使用头两个形参标记该范围。这两个形参是分别指向要处理的第一个元素和最后一个元素的下一位置的迭代器。

Alogorithm Example

1.accumulate算法:容器内的元素类型必须与第三个实参的类型匹配，或者可转换为第三个实参的类型。

// sum the elements in vec starting the summation with the value 42
int sum = accumulate(vec.begin(), vec.end(), 42);

2.泛型算法都是在标记容器（或其他序列）内的元素范围的迭代器上操作的。**标记范围的两个实参类型必须精确匹配
**，而迭代器本身必须标记一个范围：它们必须指向同一个容器中的元素（或者超出容器末端的下一位置），并且如果两者不相等，则第一个迭代器通过不断地自增，必须可以到达第二个迭代器。

3.find_first_of:这个算法带有两对迭代器参数来标记两段元素范围，在第一段范围内查找与第二段范围中任意元素匹配的元素，然后返回一个迭代器，指向第一个匹配的元素。**如果找不到元素，则返回第一个范围的end
迭代器。
**

4.写入到输入序列的算法本质上是安全的——只会写入与指定输入范围数量相同的元素。
fill(vec.begin(), vec.end(), 0); // reset each element to 0
fill_n
函数带有的参数包括：一个迭代器、一个计数器以及一个值。在没有元素的空容器上调用fill_n函数是错误的.对指定数目的元素做写入运算，或者写到目标迭代器的算法，都不检查目标的大小是否足以存储要写入的元素。