顺序容器中只定义了添加删除访问等简单操作，用户更多的需求，只能通过泛型算法实现。此类算法称之为"泛型"是因为它们可以用于不同类型的元素和多种容器类型。

泛型算法分类

大多数泛型算法都定义在algorithm中，标准库还在numeric中定义了一组数值泛型算法。常见的泛型算法可以分为：只读算法、写容器算法、重排容器算法、定制操作等四个类别。下面将分别进行简单介绍。

1 只读算法

以下大部分算法都有自己的重载版本，感兴趣的同学可以查找相关资料，进行深入学习。下面用代码的方式对常见只读算法进行介绍。

1.1 find查找

//查找目标元素在容器中的位置
void find_element_pos(vector<int> & v, int val){
    cout << find(v.begin(), v.end(), val) - v.begin() << endl;
}

1.2 accumulate求和

void accumulate_display(){
    vector<int> vi = { 1, 2, 3, 4 };
    vector<string>vs = { "accu", "disp" };
    //整数累加初值设为0
    cout << accumulate(vi.begin(), vi.end(), 0) << endl;
    //字符累加初值设为"";
    cout << accumulate(vs.begin(), vs.end(), string("")) << endl;
}

1.3 count计算目标元素的个数

void count_element(vector<int> & v, int val){
    cout << count(v.begin(), v.end(), val) << endl;
}

1.4 equal判断两容器是否相等

void equal_display(){
    list <char*>a = { "a", "b" };
    vector<const char *> b = { "a", "b" };
    cout << equal(a.begin(), a.end(), b.begin())<<endl;
}
//两点说明：
//1. equal假设，第二序列b至少与a一样长，程序员有责任对此作出保证。
//2. 两序列中的元素类型不必完全相同，只要能够使用==进行比较即可。

2 写容器算法

当我们将新值赋予序列中元素时，必须保证序列原大小足够大。算法保持泛型，不会进行具体的容器操作（容器接口可能不同），因此算法自身不能改变容器的大小。常见用法如下：

2.1 填充fill/fill_n

void fill_container(){
    //fill_n/fill无法改变容器大小
    vector<int> vi;
    fill_n(vi.begin(), 10, 0);//错误，试图在空的vi中填入10个元素
    vi.push_back(1);
    vi.push_back(2);
    fill_n(vi.begin(), vi.size(), 0);//正确，将所有元素置为0
    fill(vi.begin(), vi.end(), 1);//正确，将所有元素置为1
}

2.2 拷贝copy

void copy_display(){
    int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int b[sizeof(a) / sizeof(*a)];
    auto pos = copy(begin(a), end(a), b);
    //三点说明：
    //1. sizeof在编译时计算，所以支持用来定义数组b的大小
    //2. begin(a),end(a)指向a的第一个元素，以及尾后位置
    //3. 返回值pos指向目标迭代器递增后的值，此例中pos恰好指向b的尾后迭代器
}

2.3 替代replace

void replace_display(){
    vector<int> vi = { 1, 2, 1, 4, 1, 6, 1, 8, 1 };
    int nOld = 1, nNew = 10;
    replace(vi.begin(), vi.end(), nOld, nNew);
}
//将vi中所有1替换为10

3 重排算法

某些算法会重排容器中元素的顺序，例如sort和unique，前者对元素进行排序，后者将唯一的元素移至前段，重复的元素移至后端。常见的用法如下：

3.1 sort/stable_sort

bool compare_int(int& a, int& b){
    return a > b;
}
void sort_display(){
    vector<int> vi = { 3, 1, 4, 2, 4, 2, 1, 3, 5, 6, 8, 4, -5 };
    sort(vi.begin(), vi.end());//升序重排
    sort(vi.rbegin(), vi.rend());//降序重排
    sort(vi.begin(), vi.end(), compare_int);//支持二元谓词
}
//三点说明：
//1. `sort`用快速排序实现，是不稳定的排序算法，`stable_sort`用归并排序实现，是稳定的排序算法
//2. `sort`和`stable_sort`都支持二元谓词，来重新定义元素间的比较
//3. 基本数据类型的降序重排，可以直接使用`rbegin()`和`rend()`实现

3.2 unique/unique_copy

void unique_display(){
    vector<int> vi = { -5, 3, 1, 4, 2, 4, 2, 1, 3, 5, 6, 8, 4 };
    sort(vi.begin(), vi.end());//升序重排
    auto pos = unique(vi.begin(), vi.end());
    for (size_t i = 0; i < vi.size(); ++i){
        cout << vi[i] << " ";
    }
    cout << endl<<*pos << endl;
    //vi此时为{-5,1,2,3,4,5,6,8,4,4,5,6,8};
    //pos指向不重复区域的下一个迭代器，此处指向vi[4] = 4;
}
//unique_copy是unique的“_copy”版本，返回的是生成的序列的最后一个元素的下一个位置

4 定制操作

4.1 谓词

谓词（predicate）是一个可调用的表达式，其返回结果是一个能用做条件的值，标准库算法将谓词分为一元谓词和二元谓词两类。谓词可以作为参数传递进函数，如上例3.1所示。

4.2 lambda表达式

使用谓词给算法传递参数时，受到严格的限制。当需要传递更多参数给算法时，可以使用lambda表达式。lambda 表达式是一个可调用的代码单元，我们可以将它理解为一个匿名的内联函数。

C++11 的 lambda 表达式规范如下。其中，capture表示捕获列表，它可以捕获所在函数的定义的局部变量。params，ret ，body和普通函数一样，代表参数、返回类型和函数体。

(1) [ capture ] ( params ) mutable exception attribute -> ret { body }   
(2)    [ capture ] ( params ) -> ret { body }        
(3) [ capture ] ( params ) { body }  
(4) [ capture ] { body }

下面通过几个简单的实例来了解其用法

• (1) 忽略参数列表和返回类型

void lambda_dispaly1(){
    auto f = [] {return 10; };
    cout << f() << endl;
}
//capture，返回类型为空，只定义了body

• (2) 向lambda传参

void lambda_dispaly2(){
    auto f = [](const string a, const string b) {return a <b; };
    cout << f("1", "2") << endl;
}
//capture为空，定义了params和body

• (3) 使用捕获列表

void lambda_dispaly3(size_t size){
    auto f = [size](const string a) {return a.size() >= size; };
    cout << f("123") << endl;
}
//从所定义的函数体中捕获局部变量size

• (4) 引用捕获

//与普通函数相同，lambda表达式传递参数时也有传值和传引用两种，前述的都是传值捕获，下例为引用捕获
void lambda_dispaly4(size_t &size){
    auto f = [&size](const string a) {return a.size() >= size; };
    cout << f("123") << endl;
}
//从所定义的函数体中捕获局部变量size的引用

• (5) 隐式捕获、混合捕获

void lambda_dispaly5(vector<string>&words, size_t size){
    stable_sort(words.begin(), words.end(),
        [](const string& a, const string & b)
            {return a.size() < b.size(); });
    //查找第一个满足size()>size的元素
    auto pos = find_if(words.begin(), words.end(), 
        [&](string & a)
            {return a.size() > size; });
    int count = words.end() - pos;
    cout << count << endl;
}
//说明三点：
//1. 除显示捕获外，我们还可以让编译器来推断我们要捕获的变量。
//2. 我们需要在capture捕获列表中填写 = 或 & 指示编译器采用值捕获还是引用捕获
//3. 当我们想混合使用隐式和显示捕获时，捕获列表的一个元素必须是 = 或 &，此符号指定了默认捕获方式为引用和值。

• (6) 可变lambda

void lambda_dispaly6(){
    size_t vi = 10;
    auto f = [vi]()mutable{return  ++vi; };
    cout << f() << endl;
}
//默认情况下，对于一个值被拷贝的对象，lambda表达式不会改变其值，因此必须加上mutable来申请，其捕获的变量值可变。

• (7) 指定返回类型lambda

void lambda_dispaly7(){
    auto f = [](const string &a, const string &b)->bool 
    {if (a < b) return true; else return false; };
    cout << f("1", "2") << endl;
}
//默认情况下，如果lambda函数体包含return之外的任何语句，编译器则返回void。
//此时，当我们需要为lambda定义返回类型，必须使用尾置返回类型。

4.3 参数绑定

对于只在一两个地方使用的简单操作，lambda表达式是最高效的，如果需要在多个地方使用相同的定制操作，我们可以使用标准库bind函数。bind可以重排参数顺序。

bind函数定义在头文件functional中，使用格式如下：

auto newFun = bind(Fun, arg_list);

newFun本身是一个可调用对象，arg_list是一个用逗号分隔的参数列表，其中可能包含"_n"的名字（定义在std::placeholders中），此为”占位符“，表示newFun中的参数。_1与newFun的第一个参数对应，_2与newFun第二参数对应，依次类推。

• (1) 重排参数

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std::placeholders;
using namespace std;
auto bind_display1 = bind(lambda_dispaly5, _2, _1);//lambda_dispaly5定义参见4.2
int main(){
    vector<string> vecStr = { "abc", "bscd", "tsed" };
    bind_display1(4, vecStr);
    return 0;
}

• (2) 参数个数修改

auto bind_display2 = bind(lambda_dispaly5, _1, 4);
int main(){
    vector<string> vecStr = { "abc", "bscd", "tsed" };
    bind_display2(vecStr);
    return 0;
}
//将lambda_dispaly5中第二参数设置为4
//注意，bind中第2个到第n个函数与lambda_dispaly5相对应。"_1","_2"与bind_display函数对应。

5 迭代器

除了为每个容器定义的迭代器之外，标准库在头文件iterator中还定义了额外几种迭代器。这些迭代器包括以下几种：

• 1）插入迭代器：
  这些迭代器被绑定到一个容器上，可用来向容器插入元素
• 2）流迭代器：
  这些迭代器被绑定到输入或输出上，可用来遍历所有关联的IO流
• 3）反向迭代器：
  这些迭代器向后而不是向前移动。除了forward_list之外的标准库容器都有反向迭代器
• 4）移动迭代器：
  这些专用的迭代器不是拷贝其中的元素，而是移动它们。

1）插入迭代器

插入迭代器接受一个容器，生成一个迭代器，能够为给定容器添加元素。其根据插入位置不同，分为以下三种类型：

• back_inserter创建一个使用push_back的迭代器
• front_inserter创建一个使用push_front的迭代器
• inserter创建一个使用insert的迭代器。

2）流迭代器

虽然iostream类型不是容器，但标准库定义了用于这些IO类型对象的迭代器。istream_iterator读取输入流，ostream_iterator向一个输出流写数据。通过使用流迭代器，我们可以用泛型算法从流对象读取数据以及向其写入数据。

3）反向迭代器

反向迭代器就是在容器中从尾元素向首元素反向移动的迭代器。对于反向迭代器，递增（以及递减）操作的含义会颠倒过来。递增一个反向迭代器（++it）会移动到前一个元素；递减一迭代器（--it）会移动到下一个元素。

除了forward_list之外，其他容器都支持反向迭代器。我们可以通过调用rbegin、rcend、crbegin和crend成员函数来获得反向迭代器。这些成员函数返回指向容器尾元素和首元素之前一个位置的迭代器。与普通迭代器一样，反向迭代器也有const和非const版本。