第10章：泛型算法

• #1.概述
• #2.初始泛型算法
  • 只读算法
  • 写容器元素的算法
  • 重排容器元素的算法
• #3.定制操作
  • 向算法传递函数
  • lambda表达式
  • lambda捕获和返回
  • 参数绑定
• #4.再探迭代器
  • 插入迭代器
  • iostream迭代器
  • 反向迭代器
• #5.泛型算法结构
  • 类迭代器
  • 算法形参模式
  • 算法命名规范
• #6.特定容器算法

---

顺序容器只定义了很少的操作：在多数情况下，我们可以添加和删除元素、访问首尾元素、确定容器是否为空以及获得指向首元素或尾元素之后位置的迭代器。

我们可以想象用户还希望做其他很多有用的操作：查找特地元素、替换或删除一个特定值、重排元素顺序等。

标准库并未给每个容器都定义成员函数来实现这些操作，而是定义了一组泛型算法，这些算法中的大多数都独立于任何特定的容器。

#1. 概述

大多数算法都定义在头文件algorithmn中。标准库还在头文件numeric中定义了一组数值泛型算法。

一般情况下，这些算法并不直接操作容器，而是遍历由两个迭代器指定的一个元素范围来进行操作。通常情况下，算法遍历范围，对其中每个元素进行一些处理。例如，假定我们有一个int的vector，希望知道vector中是否包含一个特定值。回答这个问题最方便的方法是调用标准库算法find：

int val = 42; //我们将查找的值
//如果在vec中找到想要的元素，则返回结果指向它，否则返回结果为vec.cend()
auto result = find(vec.cbegin(),vec.cend(),val);
//报告结果
cout << "The value "<< val << (result == vec.cend()) ?
    " is not present" : " is present") << endl;

传递给find的前两个参数是表示元素范围的迭代器，第三个参数是一个值。find将范围中的元素与给定的值进行比较。它返回指向第一个等于给定值的元素的迭代器。如果范围中无匹配元素，则fand返回第二个参数来表示搜索失败。因此，我们可以通过比较返回值和第二个参数来判断搜索是否成功。

==泛型算法本身不会执行容器的操作，他们只会运行于迭代器之上，执行迭代器的操作。==

---

#2. 初识泛型算法

理解算法结构可以帮助更好地学习和使用算法。除少数例外，标准库算法都对一个范围内的元素进行操作。我们将此范围称为”输入范围“。接受输入范围的算法总是使用前两个参数来表示此范围，两个参数分别是指向要处理的第一个元素和尾元素之后位置的迭代器。

2.1 只读算法

一些算法只会读取其输入范围内的元素，而从不改变元素。find就是这样一种算法。

另一个只读算法是accumulate，它定义在头文件numeric中。accumulate函数接受三个参数，前两个指出需要求和的元素的范围，第三个参数是和的初值。假定vec是一个整数序列，则：

//对vec中元素求和，和的初值是0
int sum = accumulate(vec.cbegin(),vec.cend(),0);

这条语句将sum设置为vec中元素的和，和的初值被设置为0。

==accumulate的第三个参数的类型决定了函数中使用哪个加法运算符以及返回值的类型==

算法和元素类型

accumulate将第三个参数作为求和起点，这蕴含着一个编程假定：将元素类型加到求和的类型上的操作必须是可行的。即，序列中元素的类型必须与第三个参数匹配，或者能够转换为第三个参数的类型。在上例中，vec中的元素可以是int，或者是double、long long或任何其他可以添加到int上的类型。

操作两个序列的算法

另一个只读算法是equal，用于确定两个序列是否保存相同的值。它将第一个序列中的每个元素与第二个序列中的对应元素进行比较。如果所有对应元素都相等，则返回true，否则返回false。此算法接受三个迭代器：前两个表示第一个序列中的元素范围，第三个表示第二个序列的首元素：

//roster2中的元素数目应该至少与roster1一样多
equal(roster1.cbegin(),roster1.cend(),roster2.cbegin());

由于equal利用迭代器完成操作，因此我们可以通过调用equal来比较两个不同类型的容器中的元素。而且，元素类型也不必一样，只要我们能用==来比较两个元素类型即可。

==那些只接受一个单一迭代器来表示第二个序列的算法，都假定第二个序列至少与第一个序列一样长。==

2.2 写容器元素的算法

一些算法将新值赋予序列中的元素。当我们使用这类算法时，必须注意确保序列原大小至少不小于我们要求算法写入的元素数目。记住，算法不会执行容器操作，因此它们自身不可能改变容器的大小。

一些算法会自己向输入范围写入元素。这些算法本质上并不危险，它们最多写入与给定序列一样多的元素。

例如，算法fill接受一对迭代器表示一个范围，还接受一个值作为第三个参数。fill将给定的这个值输入序列中的每个元素。

fill(vec.begin(),vec.end(),0); //将每个元素重置为0
fill(vec.begin(),vec.begin() + vec.size()/2,10); //将容器的一个子序列设置为0

算法不检查写操作

一些算法接受一个迭代器来指出一个单独的目的位置。这些算法将新值赋予一个序列中的元素，该序列从目的位置迭代器指向的元素开始。例如，函数fill_n接受一个单迭代器、一个计数值和一个值。它将给定值赋予迭代器指向的元素开始的指定以元素。我们可以用fill_n将一个新值赋予vector中的元素：

vector<int> vec; //空vector
//使用vec，赋予它不同值
fill_n(vec.begin(),vec.size(),0); //将所有元素重置为0

函数fill_n假定写入指定个元素是安全的。即，如下形式的调用：

fill_n(dest,n,val);

fill_n假定dest指向一个元素，而从dest开始的序列至少包含n个元素。

==向目的位置迭代器写入数据的算法假定目的位置足够大，能容纳要写入的元素。==

介绍back_inserter

一种保证算法有足够元素空间来容纳输出数据的方法是使用插入迭代器，插入迭代器是一种向容器中添加元素的迭代器。通常情况，当我们通过一个迭代器向容器元素赋值时，值被赋予迭代器指向的元素。而当我们通过一个插入迭代器赋值时，一个与赋值号右侧值相等的元素被添加到容器中。

back_inserter接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器。当我们通过此迭代器赋值时，赋值运算符会调用push_back将一个具有给定值的元素添加到容器中：

vector<int> vec; //空向量
auto it = back_inserter(vec); //通过它赋值会将元素添加到vec中
*it = 42; //vec中现在有一个元素，值为42

我们常常使用back_inserter来创建一个迭代器，作为算法的目的位置来使用。例如：

vector<int> vec; //空向量
//正确：back_inserter创建一个插入迭代器，可用来向vec添加元素。
fill_n(back_inserter(vec), 10, 2); //添加10个元素到vec

在每步迭代中，fill_n向给定序列中的一个元素赋值。由于我们传递的参数是back_inserter返回的迭代器，因此每次赋值都会在vec上调用push_back。最终，这条fill_n调用语句向vec的末尾添加了10个元素，每个元素的值都是0。

拷贝算法

拷贝算法是另一个向目的位置迭代器指向的输出序列中的元素写入数据的算法。此算法接受三个迭代器，前两个表示一个输入范围，第三个表示目的序列的起始位置。此算法将输入范围中的元素拷贝到目的序列中。传递给copy的目的序列至少包含与输入序列一样多的元素，这一点很重要。

int a1[] = { 1,2,3,4,5,6,7,8 };
int a2[sizeof(a1) / sizeof(*a1)]; //a2和a1大小一样
//ret指向拷贝到a2的尾元素之后的位置
auto ret = copy(begin(a1), end(a1), a2); //把a1的内容拷贝给a2

此例中我们定义一个名为a2的数组，并使用sizeof确保a2与数组a1包含同样多的元素。接下来我们调用copy完成从a1到a2的拷贝。在调用copy后，两个数组中的元素具有相同的值。

2.3 重排容器元素的算法

void elimDups(vector<string> &words) {
    //按字典序排序words，以便查找重复字符
    sort(words.begin(),words.end());
    //unique重排输入范围，使得每个单词只出现一次
    auto end_unique = unique(words.begin(),words.end());
    //使用向量操作erase删除重复单词
    words.erase(end_unique,words.end());
}

---

#3. 定制操作

很多算法都会比较输入序列中的元素。默认情况下，这类算法使用元素类型的<或==运算符来完成比较。标准库还为这些算法定义了额外的版本，允许我们提供自己定义的操作来代替默认运算符。

3.1 向算法传递函数

作为一个例子，假定希望在调用elimDups后打印vector的内容。此外还假定希望单词按其长度排序，大小相同的再按字典序排序。为了按长度重拍vector，我们将使用sort的第二个版本，此版本是重载过的，它接受第三个参数，此参数是一个谓词。

谓词

谓词是一个可调用的表达式，其返回结果是一个能用作条件的值。标准库算法所使用的谓词分为两类：一元谓词（意味着他们只接受单一参数），二元谓词（意味着它们有两个参数）。接受谓词参数的算法对输入序列中的元素调用谓词。因此，元素类型必须能转换为谓词的参数类型。

排序算法

在我们将words按大小重排的同时，还希望具有相同长度的元素按字典序排序。为了保持相同长度的单词按字典序排序。可以使用stable_sort算法。这种稳定排序算法维持相等元素的原有顺序。

elimDups(words); //将words按字典序重排，并消除重复单词
//按长度重新排序，长度相同的单词维持字典序
stable_sort(words.begin(),words.end(),isShorter);
for(const auto &s : words) // 无须拷贝字符串
{
    cout << s << " "; //打印每个元素，以空格分隔
}
cout << endl;

假定在此调用前words是按字典序排列的，则调用之后，words会按元素大小排序，而长度相同的单词会保持字典序。

3.2 lambda表达式

根据算法接受一元谓词还是二元谓词，我们传递给算法的谓词必须严格接受一个或两个参数。但是，有时我们希望进行的操作需要更多参数，超出了算法对谓词的限制。

介绍lambda

我们可以向一个算法传递任何类别的可调用对象。对于一个对象或一个表达式，如果可以对其使用调用运算符，则称它为可调用的。即，如果e是一个可调用的表达式，则我们可以编写代码e(args)，其中args是一个逗号隔开的一个或多个参数的列表。

到目前为止，我们使用过的仅有的两种可调用对象是函数和指针。还有其他两种可调用对象：重载了函数调用运算符的类，以及lambda表达式。

一个lambda表达式表示一个可调用的代码单元。我们可以将其理解为一个未命名的内联函数。与任何函数类似，一个lambda具有一个返回类型、一个参数列表和一个函数体。但与函数不同，lambda表达式可以定义在函数内部。一个lambda表达式具有如下形式：

[capture list](parameter list) -> return type {function body};

其中，capture list(捕获列表)是一个lambda所在函数中定义的局部变量的列表（通常为空）；return type、parameter list和function body与任何普通函数一样，分别表示返回类型、参数列表和函数体。但是，与普通函数不同，lambda必须使用尾置返回来指定返回类型。

我们可以忽略参数列表和返回类型，但必须永远包含捕获列表和函数体

auto f = [] {return 42; };

此例中，我们定义了一个可调用对象f，它不接受参数，返回42。

lambda的调用方式与普通函数的调用方式相同，都是使用调用运算符：

cout << f() << endl; //打印42

==如果lambda的函数体包含任何单一return语句之外的内容，且未指定返回类型，则返回void。==

向lambda传递参数

与一个普通函数调用类似，调用一个lambda表达式时给定的实参被用来初始化lambda的形参。通常，实参和形参的类型必须匹配。但与普通函数不同，lambda不能有默认参数。因此，一个lambda调用实参数目永远与形参数据相等。一旦形参初始化完毕，就可以执行函数体了。

[](const string &a, const string &b) {
    return a.size() < b.size();
};

空捕获列表表明此lambda不适用它所在函数中的任何局部变量。lambda的参数与isShorter的参数类似，是const string的引用。lambda的函数体也与isShorter类似，比较其两个参数的size()，并根据两者的相对大小返回一个布尔值。

如下所示，可以使用此lambda来调用stable_sort:

//按长度排序，长度相同的单词维持字典序
stable_sort(words.begin(),words.end(),[](const string &a,const string& b) {
    return a.size() < b.size();
});

使用捕获列表

虽然一个lambda可以出现在一个函数中，使用其局部变量，但它只能使用那些明确指明的变量。一个lambda通过将局部变量包含在其捕获列表中来指出将会使用这些变量。捕获列表指引lambda在其内部包含访问局部变量所需的信息。

在本例中，我们的lambda会捕获sz，并只有单一的string参数。其函数体会将string的大小与捕获的sz的值进行比较：

[sz](const string &a) {
    return a.size() > sz;
};

lambda以一对[]开始，我们可以在其中提供一个以逗号分隔的名字列表，这些名字都是它所在函数中定义的。

由于此lambda捕获sz，因此lambda的函数体可以使用sz。lambda不捕获words，因此不能访问此变量。如果我们给lambda提供一个空捕获列表，则代码会编译错误：

//错误：sz未捕获
[](const string &a) {
    return a.size() >= sz;
}

==一个lambda只有在其捕获列表中捕获一个它所在函数中的局部变量，才能在函数体中使用该变量。==

调用find_if

使用此lambda，我们就可以查找第一个长度大于等于sz的元素：

//获取一个迭代器，指向第一个满足size()>=sz是元素
auto wc = find_if(words.cbegin(), words.cend(), 
    [sz](const string &a) {
        return a.size() >= sz;
    })

完整的biggies

void biggies(vector<string> &words,vector<string>::size_type sz) {
    elimDups(words); //将words按字典排序，删除重复单词
    //按长度排序，长度相同的单词维持字典序
    stable_sort(words.begin(),words.end(),
        [](const string &a,const string &b) {
            return a.size() > b.size();
        });
    //获取一个迭代器，指向第一个满足size() >= sz的元素
    auto wc = find_if(words.begin(),words.end(),
        [sz](const string &a) {
            return a.size() > sz;
        });
    //计算满足size >= sz的元素的数目
    auto count = words.end() - wc;
    cout << count << " " << make_plural(count,"word","s")
    << " of length " << sz << " or longer" << endl;
    cout << endl;
}

3.3 lambda捕获和返回

当定义一个lambda时，编译器生成一个与lambda对应的新的（未命名的）类类型。当向一个函数传递一个lambda时，同时定义了一个新类型和该类型的一个对象：传递的参数就是此编译器生成的类类型的未命名对象，类似的，当使用auto定义一个用lambda初始化的变量时，定义了一个从lambda生成的类型的对象。

值捕获

类似参数传递，变量的捕获方式也可以是值或引用。与传值参数类似，采用值捕获的前提是变量可以拷贝。与参数不同，被捕获的变量的值在lambda创建的时候拷贝，而不是调用时拷贝：

void fcn1() {
    size_t v1 = 42;//局部变量
    //将v1拷贝到名为f的可调用对象
    auto f = [v1] {return v1; };
    v1 = 0;
    auto j = f();//j为42;f保存了我们创建它时v1的拷贝
}

由于被捕获的值是在lambda创建时拷贝，因此随后对其修改不会影响到lambda内对应的值。

引用捕获

我们定义lambda时可以采用引用方式捕获变量。例如：

void fcn2() {
    size_t v1 = 42;//布局变量
    //对象f包含v2的引用
    auto f = [&v1] {return v1; };
    v2 = 0;
    auto j = f();//j为0；f保存v2的引用，而非拷贝
}

v1之前的&指出v1应该以引用方式捕获。一个以引用方式捕获的变量与其他任何类型的引用行为类似。当我们在lambda函数体内使用此变量时，实际上使用的是引用所绑定的对象。在本例中，当lambda返回v1时，它返回的是v1指向的对象的值。

==当以引用方式捕获一个变量时，必须保证在lambda执行时变量是存在的。==

隐式捕获

除了显示的使用来自所在函数的变量之外，还可以让编译器根据lambda体中的代码来推断我们需要使用哪些变量。为了指示编译器推断捕获列表，应在捕获列表中写一个&或=。&告诉编译器采用捕获引用方式，=则表示采用值捕获方式。例如，我们可以重写传递给find_if的lambda：

//sz为隐式捕获，值捕获的方式
wc = find_if(words.begin(),words.end(),
    [=](const string &s) {
        return s.size() >= sz;
    });

如果我们希望对一部分变量采用值捕获，对其他变量采用引用捕获，可以混合使用隐式捕获和显式捕获：

void biggies(vector<string> &words,vector<string>::size_type sz,
    ostream &os = cout,char c = ' ') {
    //其他处理与前例一样
    //os隐式捕获，引用捕获方式；c显式捕获，值捕获方式
    for_each(words.begin(),words.end(),
    [&,c](const string &s) {
       os << s << c; 
    });
    //os显式捕获，引用捕获方式，c隐式捕获，值捕获方式
    for_each(words.begin(),words.end(),
    [=,&os](const string &s) {
        os << s << c;
    });
}

当我们混合使用隐式捕获和显式捕获时，捕获列表中的第一个元素必须是一个&或=。此符号指定了默认捕获方式为引用或值。

lambda捕获列表	说明
[]	空捕获列表。lambda不能使用所在函数中的变量。一个lambda只有捕获变量后才能使用它们
[names]	names是一个逗号分隔的名字列表，这些名字不是lambda所在函数的局部变量。默认情况下，捕获列表中的变量都被拷贝。名字前如果使用&，则采用引用捕获方式
[&]	隐式捕获列表，采用引用捕获方式。lambda体中所使用的来自所在函数的实体都采用引用方式使用
[=]	隐式捕获列表，采用值捕获方式。lambda体将拷贝所使用的来自所在函数的实体的值
[&,indentifier_list]	indentifier_list是一个逗号分隔的列表，包含0个或多个来自所在函数的变量。这些变量采用值捕获方式，而任何隐式捕获的变量都采用引用方式捕获。indentifier_list中的名字前面不能使用&
[=,indentifier_list]	indentifier_list中变量都采用引用方式捕获，而任何隐式捕获的变量都采用值方式捕获。indentifier_list中名字不能包括this，且这些名字之前必须使用&

可变lambda

默认情况下，对于一个值被拷贝的变量，lambda不会改变其值。如果希望改变一个被捕获的变量的值，就必须在参数列表首加上关键字mutable。因此，可变lambda能省略参数列表：

void fun3() {
    size_t v3 = 42;
    //f可以改变它所捕获的变量的值
    auto f = [=]()mutable {return ++v3; };//采用隐式值捕获的方式
    v3 = 0;
    auto j = f();
}

一个引用捕获的变量是否（如往常一样）可以修改依赖于此引用指向的是一个const类型还是一个非const类型：

void fcn4() {
    size_t v1 = 42; //局部变量
    //v1是一个非const变量的引用
    //可以通过f2中的引用来改变它
    auto f2 = [&v1]() {return ++v1; };
    v1 = 0;
    auto j = f2(); //j为1
    cout << j << endl;
}

指定lambda返回类型

当需要为一个lambda定义返回类型时，必须使用尾置返回类型。

transform(v1.begin(),v1.end(),v2.begin(),
    [](int i) -> int {
        if(i<0) return -i;else return i;
    });

在此例中，传递给transform的第四个参数是一个lambda，它的捕获列表是空的，接受单一int参数，返回一个int值。它的函数体是一个返回其参数绝对值的if语句。

3.4 参数绑定

对于那种只在一两个地方使用的简单操作，lambda表达式是最有用的。如果我们需要在很多地方使用相同的操作，通常应该定义一个函数。

如果lambda的捕获列表为空，通常可以用函数来代替它。但是，对于捕获局部变量的lambda，用函数来替换它就不那么容易了。例如，我们用在find_if调用中的lambda比较一个string和一个给定大小。我们可以很容易地编写一个完成同样工作的函数：

bool check_size(const string &s,string::size_type sz) {
    return s.size() >= sz;
}

但是，我们不能用这个函数作为find_if的一个参数。

标准库bind函数

可以将bind函数看作一个通用的函数适配器，接受一个可调用对象，生成一个新的可调用对象来“适应”原对象的参数列表。

调用bind的一般形式为:

auto newCallable = bind(callable,arg_list);
arg_list是一个逗号分隔的参数列表

其中，newCallable本身是一个可调用对象，arg_list是一个逗号分隔的参数列表，对应给定的calllable的参数。即，当我们调用newCallable时，newCallable会调用callable，并传递给它arg_list中的参数。

arg_list中参数可能包含形如_n的名字，其中n是一个整数。这些参数是“占位符”，表示newCallable的参数，它们占据了传递给newCallable的参数的“位置”。数值n表示生成的可调用对象中参数的位置：_1为newCallable的第一个参数，_2为第二个参数，依此类推。

绑定check_size的sz参数

作为一个简单的例子，我们将使用bind生成一个调用check_size的对象，如下所示，它用一个定值作为其大小参数来调用check_size：

//check6是一个可调用对象，接受一个string类型的参数
//并用此string和值6来调用check_size
auto check6 = bind(check_size,_1,6);

此bind调用只有一个占位符，表示check6只接受单一参数。占位符出现在arg_list中的第一个位置，表示check6的此参数对应check_size的第一个参数。此参数是一个const string&。因此，调用check6必须传递给它一个string类型的参宿，check6会将此参数传递给check_size。

使用placeholders名字

名字_n都定义在一个名为placeholders的命名空间中，而这个命名空间本身定义在std命名空间中。为了使用这些名字，两个命名空间都要写上。例如，_1对应的using声明为：

using std::placeholders::_1;

对每个占位符名字，我们都必须提供一个单独的using声明。

bind的参数

我们可以用bind修正参数的值。更一般的，可以用bind绑定给定可调用对象中参数或重新安排其顺序。例如，假定f是一个可调用对象，它有5个参数，则下面对bind的调用：

//g是一个有两个参数的可调用对象
auto g = bind(f,a,b,_2,c,_1);

生成一个新的可调用对象，它有两个参数，分别用占位符_2和_1表示。这个新的可调用对象将它自己的参数作为第三个和第五个参数传递给f。f的第一个、第二个和第四个参数分别绑定到给定的值a、b和c上。

传递给g的参数按位置绑定到占位符。即，第一个参数绑定到_1，第二个参数绑定到_2。因此，当我们调用g时，其第一个参数将被传递给f作为最后一个参数，第二个参数将被传递给f作为第三个参数。实际上，这个bind调用会将

g(_1,_2);

映射为

f(a,b,_2,c,_1);

即，对g的调用会调用f,用g的参数代替占位符，再加上绑定的参数a、b和c。例如，调用g(X,Y)会调用

f(a,c,Y,c,X)

用bind重排参数顺序

下面是用bind重排参数顺序的一个具体例子，我们可以用bind颠倒isShorter的含义：

//按单词长度由短至长排序
sort(words.begin(),words.end(),isShorter);
//按单词长度由长至短排序
sort(words.begin(),words.end(),bind(isShorter,_2,_1));

在第一个调用中，当sort需要比较两个元素A和B时，它会调用isShorter(A,B)。在第二个对sort的调用中，传递给isShorter的参数被交换过来了。因此，当sort比较两个元素时，就好像调用isShorter(B,A)一样。

绑定引用参数

默认情况下，bind的那些不是占位符的参数就拷贝到bind返回的可调用对象中。但是，与lambda类似，有时对有些绑定的参数我们希望以引用的方式传递，或是要绑定参数的类型无法拷贝。

例如，为了替换一个引用方式捕获ostream的lambda：

for_each(words.begin(),words.end(),[&os,c](const string &s) {
   os << s << c; 
});

可以很容易地编写一个函数，完成相同的工作：

ostream &print(ostream &os,const string &s,char c) {
    return os << s << c;
}

但是不能直接用bind来代替对os的捕获：

//错误：不能拷贝os
for_each(words.begin(),words.end(),bind(print,os,_1,' '));

原因在于bind拷贝其参数，而我们不能拷贝一个ostream。如果我们希望传递给bind一个对象而又不拷贝它， 就必须使用标准库ref函数：

for_each(words.begin(),words.end(),bind(print,ref(os),_1,' '));

函数ref返回一个对象，包含给定的引用，此对象是可以拷贝的。标准库中还有一个cref函数，生成一个保存const引用的类。

---

#4. 再探迭代器

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

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

4.1 插入迭代器

插入器是一种迭代器适配器，它接受一个容器，生成一个迭代器，能实现向给定容器添加元素。当我们通过一个插入迭代器进行赋值时，该迭代器调用容器操作来向给定容器的指定位置插入一个元素。

插入器有三种类型，差异在于插入的位置：

• back_inserter创建一个使用push_back的迭代器。
• front_inserter创建一个push_front的迭代器。
• inserter创建一个使用insert的迭代器。此函数接受第二个参数，这个参数必须是一个指向给定容器的迭代器。元素将被插入到给定迭代器所表示的元素之前。

front_inserter生成的迭代器的行为与inserter生成的迭代器完全不一样。当我们使用front_inserter时，元素总是插入到容器第一个元素之前。

list<int> lst = { 1,2,3,4 };
list<int> lst2, lst3;
//拷贝完成后，lst2包含4 3 2 1
copy(lst.cbegin(), lst.cend(), front_inserter(lst2));
//拷贝完成后，lst3包含1 2 3 4
copy(lst.cbegin(), lst.cend(), inserter(lst3,lst3.begin()));

当调用front_inserter(c)时，我们得到一个插入迭代器，接下来会调用push_front。当每个元素被插入到容器c中时，它变为c的新的首元素。因此，front_inserter生成的迭代器会将插入的元素序列的顺序颠倒过来，而inserter和back_inserter则不会。

4.2 iostream迭代器

虽然iostream类型不是容器，但标准库定义了可以用于这些IO类型对象的迭代器。istream_iterator读取输入流，ostream_iterator向一个输出流写数据。这些迭代器将它们对应的流当作一个特定类型的元素序列来处理。

istream_iterator操作

当创建一个流迭代器时，必须指定迭代器将要读写的对象类型。一个istream_iterator使用>>来读取流。因此，istream_iterator要读取的类型必须定义了输入运算符。

下面是一个用istream_iterator从标准输入读取数据，存入一个vector的例子：

istream_iterator<int> in_iter(cin);//从cin读取int
istream_iterator<int> eof;//istream尾后迭代器
while (in_iter != eof)
{
    //后置递增运算读取流，返回迭代器的旧值
    //解引用迭代器，获得从流读取的前一个值
    vec.push_back(*in_iter++);
}

此循环从cin读取int值，保存在vec中。在每个循环步中，循环体代码检查in_iter是否等于eof。eof被定义为空的istream_iterator，从而可以当作尾后迭代器来使用。对于一个绑定到流的迭代器，一旦与其关联的流遇到了文件尾或遇到IO错误，迭代器的值就与尾后迭代器相等。

ostream_iterator操作

我们可以对任何具有输出运算符(<<运算符)的类型定义ostream_iterator。当创建一个ostream_iterator时，我们可以提供（可选的）第二参数，它是一个字符串，在输出每个元素后都会打印此字符串。此字符串必须是一个C风格字符串。必须将ostream_iterator绑定到一个指定的流，不允许空的或表示尾后位置的ostream_iterator。

我们可以用ostream_iterator来输出值的序列：

ostream_iterator<int> out_iter(cout," ");
for(auto e : vec) {
    *out_iter = e;//赋值语句将元素写到cout
}
cout << endl;

此程序将vec中的每个元素写到cout，每个元素后加一个空格。每次想out_iter赋值时，写操作就会被提交。

4.3 反向迭代器

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

除forward_list之外，其他容器都支持反向迭代器。通过调用rbegin、rend、crbegin和crend成员函数来获取反向迭代器。这些成员函数返回指向容器尾元素和首元素之前一个位置的迭代器。

下面的循环是一个使用反向迭代器的例子，它按逆序打印vec中的元素：

vector<int> vec = { 0,1,2,3,4,5,6,7,8,9 };
//从尾元素到首元素的反向迭代器
for (auto r_iter = vec.crbegin(); //将r_iter绑定到尾元素
    r_iter != vec.crend(); //crend指向首元素之前的位置
    ++r_iter) { //实际是递减，移动到前一个元素
    cout << *r_iter; //打印9，8，7，...0
}

---

#5. 泛型算法结构

任何算法的最基本特征是它要求其迭代器提供哪些操作。某些算法，如find，只要求通过迭代器访问元素、递增迭代器以及比较两个迭代器是否相等这些能力。算法所要求的迭代器操作可以分为5个迭代器类别。

迭代器类别	说明
输入迭代器	只读，不写；单遍扫描，只能递增
输出迭代器	只写，不读；单遍扫描，只能递增
前向迭代器	可读写；多遍扫描，只能递增
双向迭代器	可读写；多遍扫描，可递增递减
随机访问迭代器	可读写，多遍扫描，支持全部迭代器运算

5.1 5类迭代器

类似容器，迭代器也定义了一组公共操作。一些操作所有迭代器都支持，另外一些只有特定类别迭代器才支持。

c++标准指明了泛型和数值算法的每个迭代器参数的最小类别。例如，find算法在一个序列上进行一遍扫描，对元素只读操作，因此至少需要输入迭代器。

迭代器类别

输入迭代器：可以读取序列中的元素。一个输入迭代器必须支持

• 用于比较两个迭代器的相等和不相等运算符（==、!=）
• 用于推荐迭代器的前置和后置递增运算符（++）
• 用于读取元素的解引用运算符（*）；解引用只会出现在赋值运算符的右侧
• 箭头运算符（->），等价于(*it).member，即，解引用迭代器，并提取对象的成员

输出迭代器：只写而不读元素

前向迭代器：可以读写元素，这类迭代器只能在序列中沿一个方向移动。

双向迭代器：可以正向/反向读写序列中的元素。

随机访问迭代器：提供了在常量时间内访问序列中任意元素的能力。

5.2 算法形参模式

在任何其他算法分类之上，还有一组参数规范。理解这些参数规范对学习新算法很有帮助——通过理解参数的含义，你可以将注意力集中在算法所做的操作上。大多数算法有如下4种形式之一：

alg(beg,end,other args);
alg(beg,end,dest,other args);
alg(beg,end,beg2,other args);
alg(beg,end,beg2,end2,other args);

其中alg是算法的名字，beg和end表示算法所操作的输入范围。

5.3 算法命名规范

除了参数规范，算法还遵循一套命名和重载规范。这些规范诸如：如何提供一个操作代替默认的<或==运算符以及算法是将输出数据写入序列还是一个分离的目的位置等问题。

---

#6. 特定容器算法

对于list和forward_list，应该优先使用成员函数版本的算法而不是通用算法。

splice成员

lst.splice(args)或flst.splice_after(args)

(p,lst2) p是一个指向lst中元素的迭代器，或一个指向flst首前位置的迭代器。函数将lst2的所有元素移动到lst中p之前的位置或是flst中p之后的位置。将元素从lst2中删除。