面向对象编程基础¶

本课程入选教育部产学合作协同育人项目课程主页:http://cpp.njuer.org 课程老师:陈明 http://cv.mchen.org

ppt和代码下载地址
git clone https://gitee.com/cpp-njuer-org/book

第10章¶

泛型算法¶

概述
初识泛型算法
定制操作
再探迭代器
泛型算法结构
特定容器算法

泛型算法¶

标准库给容器提供了一组算法
- 大多数都独立于任何特定的容器
- 这些算法是通用的（generic，或称泛型的）：
    - 它们可用于不同类型的容器和不同类型的元素。

顺序容器只定义了很少的操作,用户可能还希望做其他很多有用的操作
标准库并未给每个容器都定义成员函数来实现这些操作，
而是定义了一组泛型算法（generic algorithm）：
- 称它们为“算法”，是因为它们实现了一些经典算法的公共接口，
    - 如排序和搜索；
- 称它们是“泛型的”，是因为它们可以用于不同类型的元素和多种容器类型
    （不仅包括标准库类型，如vector或list，还包括内置的数组类型），
    以及我们将看到的，还能用于其他类型的序列。

概述¶

- 算法头文件
#include <algorithm> 
#include <numeric> //(算数相关)
- 泛型算法多数是通过遍历两个迭代器标记的一段元素范围来实现其功能。

find
- 输入：两个标记范围的迭代器和目标查找值。
- 返回：如果找到，返回对应的迭代器，否则返回第二个参数，即标记结尾的迭代器。
    vector<int> vec = {27, 210, 12, 47, 109, 83};
    val = 42; // value we'll look for
    auto result2 = find(vec.cbegin(), vec.cend(), val);
    // report the result
    cout << "The value " << val  << (result2 == vec.cend()? 
                    " is not present" : " is present") << endl;

概述¶

- 由于find操作的是迭代器，因此我们可以用同样的find函数在任何容器中查找值。
    list<string> lst = {"val1", "val2", "val3"};
    string sval = "a value";  // value we'll look for
    auto result3 = find(lst.cbegin(), lst.cend(), sval);
    //由于指针就像内置数组上的迭代器一样，我们可以用find在数组中查找值：
    int ia[] = {27, 210, 12, 47, 109, 83};
    int val = 83;
    int* result = find(begin(ia), end(ia), val);
    // search starting from ia[1] up to but not including ia[4]
    result = find(ia + 1, ia + 4, val);

算法如何工作¶

find应执行如下步骤：
- 1.访问序列中的首元素。
- 2.比较此元素与我们要查找的值。
- 3.如果此元素与我们要查找的值匹配，find返回标识此元素的值。
- 4.否则，find前进到下一个元素，重复执行步骤2和3。
- 5.如果到达序列尾，find应停止。
- 6.如果find到达序列末尾，它应该返回一个指出元素未找到的值。
    此值和步骤3返回的值必须具有相容的类型。

迭代器令算法不依赖于容器
但算法依赖于元素类型的操作

泛型算法永远不会执行容器的操作
- 它们只会运行于迭代器之上，执行迭代器的操作。
    - 算法永远不会改变底层容器的大小。

练习¶

头文件algorithm中定义了一个名为count的函数，它类似find，
接受一对迭代器和一个值作为参数。count返回给定值在序列中出现的次数。
编写程序，读取int序列存入vector中，打印有多少个元素的值等于给定值。
重做上一题，但读取 string 序列存入 list 中。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <list>
int main()
{
    std::vector<int> v = { 1, 2, 3, 4, 5, 6, 6, 6, 2 };
    std::cout << std::count(v.cbegin(), v.cend(), 6) << std::endl;

    std::list<std::string> l = { "aa", "aaa", "aa", "cc" };
    std::cout << std::count(l.cbegin(), l.cend(), "aa") << std::endl;

    return 0;
}

初识泛型算法¶

- 标准库提供了超过100个算法，这些算法有一致的结构。
- 理解此结构可以帮助我们更容易地学习和使用这些算法。
- 除了少数例外，标准库算法都对一个范围内的元素进行操作。
- 理解算法的最基本的方法是了解它们是否读取元素、改变元素、重排元素顺序。

只读算法¶

- 一些算法只会读取其输入范围内的元素，而从不改变元素。
    - 如find count
    - 只读算法是accumulate，它定义在头文件numeric中。
      accumulate函数接受三个参数，前两个指出了需要求和的元素的范围，
      第三个参数是和的初值。

vector<int> vec(10);              // default initialized to 0
fill(vec.begin(), vec.end(), 1);  // reset each element to 1
// sum the elements in vec starting the summation with the value 0
int sum = accumulate(vec.cbegin(), vec.cend(), 0);

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

算法和元素类型¶

accumulate将第三个参数作为求和起点，这蕴含着一个编程假定：
- 将元素类型加到和的类型上的操作必须是可行的。
- 即，序列中元素的类型必须与第三个参数匹配，
  或者能够转换为第三个参数的类型。

由于string定义了+运算符，所以我们可以通过调用accumulate来将
vector中所有string元素连接起来：
vector<string> v={"abc","def","ghi","abc"};
string concat = accumulate(v.cbegin(), v.cend(), string(""));

将空串当做一个字符串字面值传递给第三个参数是不可以的，会导致一个编译错误
// 错误 const char* 没有定义+运算符
string concat = accumulate(v.cbegin(), v.cend(), "");

- 对于只读取而不改变元素的算法，通常最好使用cbegin（）和cend（）
- 如果计划使用算法返回的迭代器来改变元素的值，
  就需要使用begin（）和end（）的结果作为参数。

操作两个序列的算法¶

- 只读算法equal，用于确定两个序列是否保存相同的值。
    - 如果所有对应元素都相等，则返回true，否则返回false。
    - 此算法接受三个迭代器: 前两个（与以往一样）表示第一个序列中的元素范围，
      第三个表示第二个序列的首元素
      - 那些只接受一个单一迭代器来表示第二个序列的算法，
        都假定第二个序列至少与第一个序列一样长。
const char* temp1[] = {"hello", "so long"};
string temp2[] = {"hello", "so long", "tata"};
list<const char *> roster1(begin(temp1), end(temp1));
vector<string> roster2(begin(temp2), end(temp2));
auto b =
// roster2 should have at least as many elements as roster1
equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());
(b) ? cout << "true" : cout << "false";
- 元素类型也不必一样，只要我们能用==来比较两个元素类型即可。
- equal基于一个非常重要的假设：它假定第二个序列至少与第一个序列一样长。
  此算法要处理第一个序列中的每个元素，
  它假定每个元素在第二个序列中都有一个与之对应的元素。

练习¶

//用 accumulate求一个 vector<int> 中元素之和。
#include<iostream>
#include<numeric>
#include<vector>
int main(){
    std::vector<int> v={1,2,3};
    int sum =  std::accumulate(v.cbegin(),v.cend(),0);
    std::cout<<sum<<std::endl;
    return 0;
}

练习¶

假定 v 是一个vector<double>，那么
调用 accumulate(v.cbegin(),v.cend(),0) 有何错误（如果存在的话）？
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>

int main()
{
    std::vector<double> vd = { 1.1, 0.5, 3.3 };
    std::cout   << std::accumulate(vd.cbegin(), vd.cend(), 0)
                << std::endl;   
    return 0;
}

结果会是 int 类型。

练习¶

在本节对名册（roster）调用equal的例子中，
如果两个名册中保存的都是C风格字符串而不是string，会发生什么？

C风格字符串是用指向字符的指针表示的，
因此会比较两个指针的值（地址），而不会比较这两个字符串的内容。

写容器元素的算法¶

- 注意确保序列原大小至少不小于我们要求算法写入的元素数目。
- 算法不会执行容器操作，因此它们自身不可能改变容器的大小。
- 一些算法会自己向输入范围写入元素。
    - 算法fill接受一对迭代器表示一个范围，还接受一个值作为第三个参数。
      fill将给定的这个值赋予输入序列中的每个元素
vector<int> vec(10);              // default initialized to 0
fill(vec.begin(), vec.end(), 1);  // reset each element to 1
// set a subsequence of the container to 10
fill(vec.begin(), vec.begin() + vec.size()/2, 10);

迭代器参数¶

从两个序列中读取元素。构成这两个序列的元素可以来自于不同类型的容器。
- 例如，第一个序列vector，第二个序列list、deque、内置数组或其他容器
两个序列中元素的类型也不要求严格匹配。要求能够比较两个序列中的元素。
- 对equal算法，元素类型不要求相同，但是必须能使用==来比较元素。
- 如何传递二个序列
    - 一些算法，例如equal，接受三个迭代器
    - 其他算法接受四个迭代器：
      前两个表示第一个序列的元素范围，后两个表示第二个序列的范围。
    - 用一个单一迭代器表示第二个序列的算法都假定第二个序列至少与第一个一样长
        - 确保算法不会试图访问第二个序列中不存在的元素是程序员的责任。
        - 如果第二个序列是第一个序列的一个子集，则程序会产生一个严重错误
          equal会试图访问第二个序列中末尾之后（不存在）的元素。

算法不检查写操作¶

- 一些算法接受一个迭代器，将新值赋予序列中的元素。
- 函数fill_n接受一个单迭代器、一个计数值和一个值。
  它将给定值赋予迭代器指向的元素开始的指定个元素。

vector<int> vec;
fill_n(vec.begin(), vec.size(), 0);
//函数fill_n假定写入指定个元素是安全的。即，如下形式的调用
fill_n(dest,n,val)
//一个初学者非常容易犯的错误是在一个空容器上调用fill_n
vector<int> vec;
fill_n(vec.begin(), 10, 0);
//这个调用是一场灾难。我们指定了要写入10个元素，但vec中并没有元素
//它是空的。这条语句的结果是未定义的。
- 向目的位置迭代器写入数据的算法假定目的位置足够大，能容纳要写入的元素。

back_inserter¶

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

使用back_inserter,展示如何用算法向容器写入数据，
- 定义在头文件iterator中
- 接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器
- 通过此迭代器赋值时，会调用push_back将一个具有给定值的元素添加到容器中
vector<int> vec;
auto it = back_inserter(vec);//通过它赋值将会将元素添加到vec
*it = 12;

常使用back_inserter来创建一个迭代器，作为算法的目的位置来使用
vector<int> vec;
//正确,参数是back_inserter返回的迭代器，每次赋值都会在vec上调用push_back
fill_n(back_inserter(vec),10,0);//添加10个元素0到vec

拷贝算法¶

向目的位置迭代器指向的输出序列中的元素写入数据
此算法接受三个迭代器，前两个表示一个输入范围，第三个表示目的序列的起始位置。
此算法将输入范围中的元素拷贝到目的序列中。
传递给copy的目的序列至少要包含与输入序列一样多的元素
//用copy实现内置数组的拷贝
int a[]={0,1,2,3,4,5,6,7,8,9};
int a2[sizeof(a)/sizeof(*a1)];//10
//ret 指向拷贝到a2的尾元素之后的位置
auto ret = copy(begin(a1),end(a1),a2);//a1内容拷贝给a2

拷贝算法¶

- 多个算法都提供所谓的“拷贝”版本。这些算法计算新元素的值，
  但不会将它们放置在输入序列的末尾，而是创建一个新序列保存这些结果。
- replace算法读入一个序列，并将其中所有等于给定值的元素都改为另一个值。
  此算法接受4个参数：前两个是迭代器，表示输入序列，
  后两个一个是要搜索的值，另一个是新值。
  它将所有等于第一个值的元素替换为第二个值：
// 将所有0替换为42
replace(ilst.begin(),ilst.end(),0,42);
- 如果我们希望保留原序列不变，可以调用replace_copy。
  此算法接受额外第三个迭代器参数，指出调整后序列的保存位置：
// 使用 back_inserter 按需要增长目标序列
replace_copy(ilst.cbegin(),ilst.end(),
             back_inserter(ivec),0 42);
//调用后，ilst并未改变，ivec包含ilst的一份拷贝，
//不过原来在ilst中值为0的元素在ivec中都变为42。

练习¶

编写程序，使用 fill_n 将一个序列中的 int 值都设置为0。

#include <iostream>
#include <vector>
#include <algorithm>
using std::vector; using std::cout; using std::endl; using std::fill_n;
int main()
{
    vector<int> vec{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    fill_n(vec.begin(), vec.size(), 0);

    for (auto i : vec)
        cout << i << " ";
    cout << endl;
}

练习¶

下面程序是否有错误？如果有，请改正：
(a) vector<int> vec; list<int> lst; int i;
    while (cin >> i)
        lst.push_back(i);
    copy(lst.cbegin(), lst.cend(), vec.begin());
(b) vector<int> vec;
    vec.reserve(10);
    fill_n(vec.begin(), 10, 0);

(a) 应该加一条语句 vec.resize(lst.size()) 。
    copy时必须保证目标目的序列至少要包含与输入序列一样多的元素。
(b) reserve分配了足够的空间，但是不会创建新元素。
    算法可能改变容器中保存的元素的值，也可能在容器内移动元素，
    永远不会直接添加和删除元素，所以此处应该改
    fill_n(back_inserter(vec),10,0);

练习¶

本节提到过，标准库算法不会改变它们所操作的容器的大小。
为什么使用 back_inserter不会使这一断言失效？

back_inserter 是插入迭代器，在 iterator 头文件中，不是标准库的算法。

重排容器元素的算法¶

调用sort会重排输入序列中的元素，使之有序，
- 它是利用元素类型的<运算符来实现排序的

例如
//假定我们想分析一系列儿童故事中所用的词汇。
//假定已有一个vector，保存了多个故事的文本
//希望化简这个vector，使得每个单词只出现一次
输入：the quick red fox jumps over the slow red turtle
生成vector： fox jumps over quick red slow the turtle

消除重复单词¶

//为了消除重复单词，首先将vector排序，使得重复的单词都相邻出现
//排序完毕，我们就可以使用另一个称为unique的标准库算法来重排vector，
//使得不重复的元素出现在vector的开始部分
//由于算法不能执行容器的操作，将使用vector的erase成员来完成真正的删除操作
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());
}
//输入：the quick red fox jumps over the slow red turtle
//sort后：fox jumps over quick red red slow the the turtle//red the 2次

使用unique¶

unique重排输入序列，将相邻的重复项“消除”，
并返回一个指向不重复值范围末尾的迭代器。

//输入：the quick red fox jumps over the slow red turtle
//sort后：fox jumps over quick red red slow the the turtle//red the 2次
//unique后：fox jumps over quick red slow the turtle ??? ???
                                                     ^end_unique

标准库算法对迭代器而不是容器进行操作。算法不能（直接）添加或删除元素。

使用容器操作删除元素¶

为了真正地删除无用元素，我们必须使用容器操作，
- 本例中使用erase
- 删除从end_unique开始直至words末尾的范围内的所有元素。
    - 这个调用之后，words包含来自输入的8个不重复的单词。
    - 即使words中没有重复单词，这样调用erase也是安全的
        - unique会返回words.end（）
        - 传递给erase的两个参数具有相同的值：words.end（）

练习¶

实现你自己的elimDups。
分别在读取输入后、调用unique后以及调用erase后打印vector的内容。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
void println(const std::vector<std::string>& seq)
{
    for (auto const& elem : seq)
        std::cout << elem << " ";
    std::cout<<std::endl;
}

练习¶

auto eliminate_duplicates(std::vector<std::string> &vs) -> std::vector<std::string>&
{
    std::sort(vs.begin(), vs.end());
    println(vs);

    auto new_end = std::unique(vs.begin(), vs.end());
    println(vs);

    vs.erase(new_end, vs.end());
    return vs;
}

int main()
{
    std::vector<std::string> vs{ "abc", "bcd", "bcd", "aaa", "ccc"};
    println(vs);
    println(eliminate_duplicates(vs));

    return 0;
}

练习¶

你认为算法不改变容器大小的原因是什么？

将算法和容器的成员函数区分开。
算法的参数是迭代器，不是容器本身。

定制操作¶

很多算法都会比较输入序列中的元素。
默认情况下，这类算法使用元素类型的<或==运算符完成比较。
标准库还为这些算法定义了额外的版本，允许提供自己定义的操作来代替默认运算符。
- sort算法默认使用元素类型的<运算符。
  但可能我们希望的排序顺序与<所定义的顺序不同，
  或是我们的序列可能保存的是未定义<运算符的元素类型（如Sales_data）。
  在这两种情况下，都需要重载sort的默认行为

向算法传递函数¶

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

谓词¶

谓词是一个可调用的表达式，其返回结果是一个能用作条件的值。
标准库算法所使用的谓词分为两类：
- 一元谓词（unary predicate，意味着它们只接受单一参数）
- 二元谓词（binary predicate，意味着它们有两个参数）。
接受谓词参数的算法对输入序列中的元素调用谓词。
因此，元素类型必须能转换为谓词的参数类型。
//接受一个二元谓词参数的sort版本用这个谓词代替<来比较元素。
//可以将isShorter传递给sort。这样做会将元素按大小重新排序：
bool isShorter(const string & s1,const string & s2){
    return s1.size()<s2.size();
}
sort(words.begin(),words.end(),isShorter);

排序算法¶

为了保持相同长度的单词按字典序排列，可以使用stable_sort算法。
这种稳定排序算法维持相等元素的原有顺序。

//假定在此调用前words是按字典序排列的，
//则调用之后，words会按元素大小排序，而长度相同的单词会保持字典序。
elimDups(words);//将words按字典序重排，并消除单词
//按长度重排 长度相同的位置字典序
stable_sort(words.begin(),words.end(),isShorter);
for(const auto& s:words)
    cout<<s<<" ";
cout<<endl;

练习¶

编写程序，使用 stable_sort 和 isShorter 将传递给你的 elimDups 
版本的 vector 排序。打印 vector的内容，验证你的程序的正确性。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

void println(const std::vector<std::string>& seq)
{
    for (auto const& elem : seq)
        std::cout << elem << " ";
    std::cout<<std::endl;
}

inline bool
is_shorter(std::string const& lhs, std::string const& rhs)
{
    return  lhs.size() < rhs.size();
}

练习¶

auto elimDups(std::vector<std::string> &vs) -> std::vector<std::string>&{
    std::sort(vs.begin(), vs.end());
    println(vs);

    auto new_end = std::unique(vs.begin(), vs.end());
    println(vs);

    vs.erase(new_end, vs.end());
    return vs;
}
int main(){
    std::vector<std::string> vs{ "abce", "bcd", "bcd", "aaae", "ccc"};
    println(vs);
    elimDups(vs);
    println(vs);
    std::stable_sort(vs.begin(), vs.end(), is_shorter);
    println(vs);

    return 0;
}

练习¶

编写名为 compareIsbn 的函数，比较两个 Sales_data 对象的isbn() 成员。
使用这个函数排序一个保存 Sales_data 对象的 vector。

解：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include "Sales_data.h"

练习¶

inline bool compareIsbn(const Sales_data &sd1, const Sales_data &sd2)
{
    return sd1.isbn().size() < sd2.isbn().size();
}

int main()
{
    Sales_data d1("aa"), d2("aaaa"), d3("aaa"), d4("z"), d5("aaaaz");
    std::vector<Sales_data> v{ d1, d2, d3, d4, d5 };

    std::sort(v.begin(), v.end(), compareIsbn);

    for(const auto &element : v)
        std::cout << element.isbn() << " ";
    std::cout << std::endl;

    return 0;
}

练习¶

标准库定义了名为 partition 的算法，它接受一个谓词，对容器内容进行划分，
使得谓词为true 的值会排在容器的前半部分，
而使得谓词为 false 的值会排在后半部分。
算法返回一个迭代器，指向最后一个使谓词为 true 的元素之后的位置。
编写函数，接受一个 string，返回一个 bool 值，
指出 string 是否有5个或更多字符。使用此函数划分 words。
打印出长度大于等于5的元素。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

bool predicate(const std::string &s) 
{ 
    return s.size() >= 5; 
}

练习¶

int main()
{
    auto v = std::vector<std::string>{ "a", "as", "aasss",
                                "aaaaassaa", "aaaaaabba", "aaa" };
    auto pivot = std::partition(v.begin(), v.end(), predicate);

    for (auto it = v.cbegin(); it != pivot; ++it)
        std::cout << *it << " ";
    std::cout << std::endl;

    return 0;
}

lambda表达式¶

根据算法接受一元谓词还是二元谓词，
我们传递给算法的谓词必须严格接受一个或两个参数。

但是，有时我们希望进行的操作需要更多参数，超出了算法对谓词的限制。
//求大于等于一个给定长度的单词有多少。打印
void biggies(vector<string> &words, vector<string>::size_type sz){
    elimDups(words);
    stable_sort(words.begin(),words.end(),isShorter);
    //获取迭代器 指向第一个满足条件的元素
    //计算满足条件元素数目
    //打印
}

lambda表达式¶

使用标准库find_if算法来查找第一个具有特定大小的元素
- find_if的第三个参数是一个谓词
    - find_if接受一元谓词
    - 我们传递给find_if的任何函数都必须严格接受一个参数，
      以便能用来自输入序列的一个元素调用它。
      没有任何办法能传递给它第二个参数来表示长度
- find_if算法对输入序列中的每个元素调用给定的这个谓词。
    - 它返回第一个使谓词返回非0值的元素，
    - 如果不存在这样的元素，则返回尾迭代器。

介绍lambda¶

我们可以向一个算法传递任何类别的可调用对象（callable object）
- 对于一个对象或一个表达式，如果可以对其使用调用运算符,则称它为可调用的
    - 如果e是一个可调用的表达式，则我们可以编写代码e（args）
- 函数和函数指针是可调用对象
- 还有其他两种可调用对象：
    - 重载了函数调用运算符的类
    - lambda表达式（lambda expression）

介绍lambda¶

- lambda表达式表示一个可调用的代码单元，可以理解成是一个未命名的内联函数。
    - 与任何函数类似，一个lambda具有一个返回类型、一个参数列表和一个函数体。
    - 但与函数不同，lambda可能定义在函数内部,lambda必须使用尾置返回
- 形式：[capture list](parameter list) -> return type {function body}。
  - capture list是一个lambda所在函数定义的局部变量列表（通常为空）。不可忽略。
  - return type是返回类型。可忽略。
  - parameter是参数列表。可忽略。
  - function body是函数体。不可忽略。

auto f = [] {return 42;}

//lambda的调用方式与普通函数的调用方式相同，都是使用调用运算符：
cout<<f()<<endl;//42
//在lambda中忽略括号和参数列表等价于指定一个空参数列表。
//如果lambda的函数体包含任何单一return语句之外的内容，
//且未指定返回类型，则返回void。

向lambda传递参数¶

与一个普通函数调用类似，调用一个lambda时给定的实参被用来初始化lambda的形参。
- 与普通函数不同，lambda不能有默认参数。
- 一个lambda调用的实参数目永远与形参数目相等。

//一个带参数的lambda的例子
[](const string& a,const string& b){
 return a.size()<b.size();
}
- 空捕获列表表明此lambda不使用它所在函数中的任何局部变量。
//可以使用此lambda来调用stable_sort
stable_sort(words.begin(),words.end(),
            [](const string& a,const string& b){
                 return a.size()<b.size();});

使用捕获列表¶

解决原来的问题——编写一个可以传递给find_if的可调用表达式。
这个表达式能将输入序列中每个string的长度与biggies函数中的sz参数的值进行比较。

一个lambda通过将局部变量包含在其捕获列表中来指出将会使用这些变量。
捕获列表指引lambda在其内部包含访问局部变量所需的信息。

在本例中，我们的lambda会捕获sz，并只有单一的string参数。
[sz](const string &a ){
    return a.size()>=sz;
}
//如果我们给lambda提供一个空捕获列表，则代码会编译错误：
//错误 sz未捕获
[](const string &a ){
    return a.size()>=sz;
}
一个lambda只有在其捕获列表中捕获一个它所在函数中的局部变量，
才能在函数体中使用该变量。

调用find_if¶

使用此lambda，我们就可以查找第一个长度大于等于sz的元素：
//获取一个迭代器 指向第一个满足条件的元素
auto wc = find_if(words.begin(),words.end(),
                    [sz](const string &a ){return a.size()>=sz;});
//可以使用find_if返回的迭代器来计算从它开始到words的末尾一共有多少个元素
auto count = words.end()-wc;
cout<<count<<" "<<make_plural(count,"word","s")
    << " of length"<<sz<<" or longer"<<endl;

for_each算法¶

打印words中长度大于等于sz的元素。
为了达到这一目的，我们可以使用for_each算法。
此算法接受一个可调用对象，并对输入序列中每个元素调用此对象：
for_each(wc,words.end(),
        [](const string & s){cout<<s<<" "});
cout<< endl;
- 捕获列表只用于局部非static变量，
- lambda可以直接使用局部static变量和在它所在函数之外声明的名字。

完整的biggies¶

void biggies(vector<strin>& words,vector<string>::size_type sz){
    elimDumps();//按字典序排列 删除重复单词
stable_sort(words.begin(),words.end(),
            [](const string& a,const string& b){
                 return a.size()<b.size();});
auto wc = find_if(words.begin(),words.end(),
                    [sz](const string &a ){return a.size()>=sz;});
//可以使用find_if返回的迭代器来计算从它开始到words的末尾一共有多少个元素
auto count = words.end()-wc;
cout<<count<<" "<<make_plural(count,"word","s")
    << " of length"<<sz<<" or longer"<<endl;
for_each(wc,words.end(),
                [](const string &s ){cout<<s<<" "<<endl;}
cout<<endl;

练习¶

编写一个lambda，接受两个int，返回它们的和。

auto f = [](int i, int j) { return i + j; };

练习¶

编写一个 lambda ，捕获它所在函数的 int，并接受一个 int参数。
lambda 应该返回捕获的 int 和 int 参数的和。

int x = 10;
auto f = [x](int i) {return i + x; };

练习¶

 使用 lambda 编写你自己版本的 biggies。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

void elimdups(std::vector<std::string> &vs)
{
    std::sort(vs.begin(), vs.end());
    auto new_end = std::unique(vs.begin(), vs.end());
    vs.erase(new_end, vs.end());
}

练习¶

void biggies(std::vector<std::string> &vs, std::size_t sz)
{
    using std::string;

    elimdups(vs);

    // sort by size, but maintain alphabetical order for same size.
    std::stable_sort(vs.begin(), vs.end(), 
    [](string const& lhs, string const& rhs){
        return lhs.size() < rhs.size();
    });

    // get an iterator to the first one whose size() is >= sz
    auto wc = std::find_if(vs.begin(), vs.end(),
     [sz](string const& s){
            return s.size() >= sz;
    });

    // print the biggies
    std::for_each(wc, vs.end(), [](const string &s){
        std::cout << s << " ";
    }); 
}

练习¶

int main()
{
    std::vector<std::string> v
    {
        "1234","1234","1234","hi~", "alan", "alan", "cp"
    };
    biggies(v, 3);
    std::cout << std::endl;

    return 0;
}

练习¶

重写节练习程序，在对sort的调用中使用 lambda 来代替函数 compareIsbn。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include "Sales_data"
int main(){
    Sales_data d1("aa"), d2("aaaa"), d3("aaa"), d4("z"), d5("aaaaz");
    std::vector<Sales_data> v{ d1, d2, d3, d4, d5 };
    std::sort(v.begin(), v.end(), [](const Sales_data &sd1, const Sales_data &sd2){
        return sd1.isbn().size() < sd2.isbn().size();
    });
    for(const auto &element : v)
        std::cout << element.isbn() << " ";
    std::cout << std::endl;
    return 0;
}

练习¶

重写 biggies，用 partition 代替 find_if。我们在练习中介绍了 partition 算法。
用 stable_partition 重写前一题的程序，与 stable_sort 类似，
在划分后的序列中维持原有元素的顺序。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

void elimdups(std::vector<std::string> &vs)
{
    std::sort(vs.begin(), vs.end());
    auto new_end = std::unique(vs.begin(), vs.end());
    vs.erase(new_end, vs.end());
}

练习¶

void biggies_partition(std::vector<std::string> &vs, std::size_t sz){
    elimdups(vs);
    auto pivot = partition(vs.begin(), vs.end(), [sz](const std::string &s){
        return s.size() >= sz;}
    );
    for(auto it = vs.cbegin(); it != pivot; ++it)
        std::cout << *it << " ";
}

void biggies_stable_partition(std::vector<std::string> &vs, std::size_t sz){
    elimdups(vs);
    auto pivot = stable_partition(vs.begin(), vs.end(), [sz](const std::string& s){
        return s.size() >= sz;
    });
    for(auto it = vs.cbegin(); it != pivot; ++it)
        std::cout << *it << " ";
}

练习¶

int main()
{
    std::vector<std::string> v{
        "the", "quick", "red", "fox", "jumps", "over", "the", "slow", "red", "turtle"
    };

    std::vector<std::string> v1(v);
    biggies_partition(v1, 4);
    std::cout << std::endl;

    std::vector<std::string> v2(v);
    biggies_stable_partition(v2, 4);
    std::cout << std::endl;

    return 0;
}

lambda捕获和返回¶

当定义一个lambda时，编译器生成一个与lambda对应的新的（未命名的）类类型。
- 当向一个函数传递一个lambda时，同时定义了一个新类型和该类型的一个对象
- 传递的参数就是此编译器生成的类类型的未命名对象。
    - 类似的，当使用auto定义一个用lambda初始化的变量时，
      定义了一个从lambda生成的类型的对象。
默认情况下，从lambda生成的类都包含一个对应该lambda所捕获的变量的数据成员。
- 类似任何普通类的数据成员，lambda的数据成员也在lambda对象创建时被初始化。
当以引用方式捕获一个变量时，必须保证在lambda执行时变量是存在的。

值捕获¶

类似参数传递，变量的捕获方式也可以是值或引用
- 采用值捕获的前提是变量可以拷贝。
- 与参数不同，被捕获的变量的值是在lambda创建时拷贝，而不是调用时拷贝：
void fcn1()
{
    size_t v1 = 42;  // local variable
    // copies v1 into the callable object named f
    auto f = [v1] { return v1; };
    v1 = 0;
    auto j = f(); // j is 42; f stored a copy of v1 when we created it
    cout << j << endl;
}

引用捕获¶

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

void fcn2()
{
    size_t v1 = 42;  // local variable
    // the object f2 contains a reference to v1
    auto f2 = [&v1] { return v1; };
    v1 = 0;
    auto j = f2(); // j is 0; f2 refers to v1; it doesn't store it
    cout << j << endl;
}
引用捕获与返回引用有着相同的问题和限制。
如果采用引用方式捕获一个变量，
就必须确保被引用的对象在lambda执行的时候是存在的。

引用捕获¶

引用捕获有时是必要的。
例如，我们可能希望biggies函数接受一个ostream的引用，
用来输出数据，并接受一个字符作为分隔符：
void biggies(vector<string> &words,
            vector<string>::size_type sz,
            ostream &os = cout,char c=' '){
    //与之前一样的重排words代码
    //打印cout改为打印到os
    for_each(words.begin(),words.end(),
            [&os,c](const string &s){os<<s<<c;});
}

不能拷贝ostream对象
因此捕获os的唯一方法就是捕获其引用（或指向os的指针）。

如果函数返回一个lambda，则与函数不能返回一个局部变量的引用类似，
此lambda也不能包含引用捕获。

尽量保持lambda的变量捕获简单化¶

一个lambda捕获从lambda被创建（即，定义lambda的代码执行时）
到lambda自身执行（可能有多次执行）这段时间内保存的相关信息。
- 确保lambda每次执行的时候这些信息都有预期的意义，是程序员的责任。
- 捕获普通变量，如int、string或其他非指针类型，通常可以采用简单的值捕获方式
- 如果我们捕获一个指针或迭代器，或采用引用捕获方式，
  就必须确保在lambda执行时，绑定到迭代器、指针或引用的对象仍然存在。
  而且，需要保证对象具有预期的值。
- 一般来说，我们应该尽量减少捕获的数据量，来避免潜在的捕获导致的问题。
  而且，如果可能的话，应该避免捕获指针或引用。

隐式捕获¶

可以让编译器根据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体中所使用
                        的来自所在函数的实体都采用引用方式使用。 
[=]                     隐式捕获列表，采用值捕获方式。 
[&, identifier_list]    identifier_list是一个逗号分隔的列表，包含0个或
                        多个来自所在函数的变量。这些变量采用值捕获方式，
                        而任何隐式捕获的变量都采用引用方式捕获。
                        identifier_list中的名字前面不能使用& 
[=, identifier_list]    identifier_list中的变量采用引用方式捕获，而任何
                        隐式捕获的变量都采用值方式捕获。identifier_list中
                        的名字不能包括this，且前面必须使用&

可变lambda¶

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

void fcn3()
{
    size_t v1 = 42;  // local variable
    // f can change the value of the variables it captures
    auto f = [v1] () mutable { return ++v1; };
    v1 = 0;
    auto j = f(); // j is 43
    cout << j << endl;
}

可变lambda¶

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

void fcn4()
{
    size_t v1 = 42;  // local variable
    // v1 is a reference to a nonconst variable
    // we can change that variable through the reference inside f2
    auto f2 = [&v1] { return ++v1; };
    v1 = 0;
    auto j = f2(); // j is 1
    cout << j << endl;
}

指定lambda返回类型¶

如果一个lambda体包含return之外的任何语句，则编译器假定此lambda返回void。
与其他返回void的函数类似，被推断返回void的lambda不能返回值。

使用标准库transform算法和一个lambda来将一个序列中的每个负数替换为其绝对值：
transform(vi.begin(),vi.end(),vi.begin(),
            [](int i){return i<0?-i:i});
//函数transform接受三个迭代器和一个可调用对象。
//前两个迭代器表示输入序列，第三个迭代器表示目的位置。
//当输入迭代器和目的迭代器相同时，
//transform将输入序列中每个元素替换为可调用对象操作该元素得到的结果。

我们传递给transform一个lambda，它返回其参数的绝对值。
lambda体是单一的return语句，返回一个条件表达式的结果。
我们无须指定返回类型，因为可以根据条件运算符的类型推断出来。

但是，如果我们将程序改写为看起来是等价的if语句，就会产生编译错误：
//错误 不能推断lambda返回类型
transform(vi.begin(),vi.end(),vi.begin(),
            [](int i){if(i<0)return -i;else return i;});
编译器推断这个版本的lambda返回类型为void，但它返回了一个int值。

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

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

练习¶

标准库定义了一个名为 count_if 的算法。类似 find_if，此函数接受一对迭代器，
表示一个输入范围，还接受一个谓词，会对输入范围中每个元素执行。
count_if返回一个计数值，表示谓词有多少次为真。
使用count_if重写我们程序中统计有多少单词长度超过6的部分。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>


using std::vector;
using std::count_if;
using std::string;

std::size_t bigerThan6(vector<string> const& v)
{
    return count_if(v.cbegin(), v.cend(), [](string const& s){
        return s.size() > 6;
    });
}

练习¶

int main()
{
    vector<string> v{
        "alan","moophy","1234567","1234567","1234567","1234567"
    };
    std::cout <<  bigerThan6(v) << std::endl;


    return 0;
}

练习¶

编写一个 lambda，捕获一个局部 int 变量，并递减变量值，直至它变为0。
一旦变量变为0，再调用lambda应该不再递减变量。
lambda应该返回一个bool值，指出捕获的变量是否为0。


    int i = 10;
    auto f = [&i]() -> bool { return (i == 0 ? true : !(i--)); };
    while (!f()) cout << i << endl;

参数绑定¶

如果lambda的捕获列表为空，通常可以用函数来代替它
对于捕获局部变量的lambda，用函数来替换它就不是那么容易了。

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

不能用这个函数作为find_if的一个参数。
如前文所示，find_if接受一个一元谓词，
因此传递给find_if的可调用对象必须接受单一参数。
为了用check_size来代替此lambda，必须解决如何向sz形参传递一个参数的问题。

标准库bind函数¶

可以解决向check_size传递一个长度参数的问题，
方法是使用一个新的名为bind的标准库函数，
它定义在头文件functional中。

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

标准库bind函数¶

调用bind的一般形式为：

auto newCallable = bind(callable,arg_list);
- newCallable本身是一个可调用对象，
- arg_list是一个逗号分隔的参数列表，对应给定的callable的参数。
调用newCallable时，newCallable会调用callable，并传递给它arg_list中的参数。

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

绑定check_size的sz参数¶

作为一个简单的例子，我们将使用bind生成一个调用check_size的对象
//check6是一个可调用对象 接受string参数
//并用此string和6来调用check_size
auto check6 = bind(check_size,_1,6);

string s = "hello";
bool b1 = check6(s);//check6(s)会调用check_size(s,6)
//使用bind可将原来lambda的find_if
auto wc = find_if(words.begin(),words.end(),[sz](const string& a));
//替换为
auto wc = find_if(words.begin(),words.end(),bind(check_size,_1,sz));

使用placeholders名字¶

名字_n都定义在一个名为placeholders的命名空间中，
而这个命名空间本身定义在std命名空间
对bind的调用代码假定之前已经恰当地使用了using声明。_1对应的using声明为
using std::placeholders::_1;
using namespace std::placeholders;
//使得由placeholders定义的所有名字都可用。
//与bind函数一样，placeholders命名空间也定义在functional头文件中。

bind的参数¶

可以用bind修正参数的值
可以用bind绑定给定可调用对象中的参数或重新安排其顺序。

假定f是一个可调用对象，它有5个参数，则下面对bind的调用：
//g是有两个参数的可调用对象
auto g=bind(f,a,b,_2,c,_1);


生成一个新的可调用对象，它有两个参数，分别用占位符_2和_1表示。
这个新的可调用对象将它自己的参数作为第三个和第五个参数传递给f。
bind调用会将
g(_1,_2 )映射为f(a,b,_2,c,_1);
调用g(X,Y)会调用

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

我们可以用bind颠倒isShroter的含义：
//单词长度升序
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）一样。

绑定引用参数¶

有时对有些绑定的参数我们希望以引用方式传递，或是要绑定参数的类型无法拷贝。
例如，为了替换一个引用方式捕获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一个对象而又不拷贝它，就必须使用标准库ref函数：

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

函数ref返回一个对象，包含给定的引用，此对象是可以拷贝的。
标准库中还有一个cref函数，生成一个保存const引用的类。
与bind一样，函数ref和cref也定义在头文件functional中。

向后兼容：参数绑定¶

旧版本C++提供的绑定函数参数的语言特性限制更多，也更复杂。
标准库定义了两个分别名为bind1st和bind2nd的函数。
类似bind，这两个函数接受一个函数作为参数，生成一个新的可调用对象，
该对象调用给定函数，并将绑定的参数传递给它。
但是，这些函数分别只能绑定第一个或第二个参数。
由于这些函数局限太强，在新标准中已被弃用（deprecated）。
所谓被弃用的特性就是在新版本中不再支持的特性。新的C++程序应该使用bind。

练习¶

重写统计长度小于等于6的单词数量的程序，使用函数代替lambda。
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using std::string;
using namespace std::placeholders;
bool isLesserThanOrEqualTo6(const string &s, string::size_type sz)
{
    return s.size() <= sz;
}
int main()
{
    std::vector<string> authors{ "Mooophy", "pezy",
                                "Queequeg90", "shbling", "evan617" };
    std::cout << count_if(authors.cbegin(), authors.cend(),
                                bind(isLesserThanOrEqualTo6, _1, 6));
}

练习¶

bind 接受几个参数？

假设被绑定的函数接受 n 个参数，那么bind 接受n + 1个参数。

练习¶

给定一个string，使用 bind 和 check_size 在一个 int 的vector 中
查找第一个大于string长度的值。
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::find_if;
using std::bind;
using std::size_t;

auto check_size(string const& str, size_t sz)
{
    return str.size() < sz;
}

练习¶

int main()
{
    vector<int> vec{ 0, 1, 2, 3, 4, 5, 6, 7 };
    string str("123456");
    auto result = find_if(vec.begin(), vec.end(), 
                    bind(check_size, str, std::placeholders::_1));
    if (result != vec.end())
        cout << *result << endl;
    else
        cout << "Not found" << endl;

    return 0;
}

练习¶

在练习中，编写了一个使用partition 的biggies版本。
使用 check_size 和 bind 重写此函数。
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using std::string; using std::vector;
using namespace std::placeholders;
void elimdups(vector<string> &vs)
{
    std::sort(vs.begin(), vs.end());
    vs.erase(unique(vs.begin(), vs.end()), vs.end());
}
bool check_size(const string &s, string::size_type sz)
{
    return s.size() >= sz;
}

练习¶

void biggies(vector<string> &words, vector<string>::size_type sz)
{
    elimdups(words);
    auto iter = std::stable_partition(words.begin(), words.end(), 
                                    bind(check_size, _1, sz));
    for_each(words.begin(), iter,
                    [](const string &s){ std::cout << s << " "; });
}

int main()
{
    std::vector<std::string> v{
        "the", "quick", "red", "fox", "jumps", "over", "the", "slow", "red", "turtle"
    };
    biggies(v, 4);
}

再探迭代器¶

除了为每个容器定义的迭代器之外，标准库在头文件iterator中还定义了额外几种迭代器。
- 插入迭代器（insert iterator）：
  这些迭代器被绑定到一个容器上，可用来向容器插入元素。
- 流迭代器（stream iterator）：
  这些迭代器被绑定到输入或输出流上，可用来遍历所关联的IO流。
- 反向迭代器（reverse iterator）：
  这些迭代器向后而不是向前移动。除了forward_list之外的标准库容器都有反向迭代器。
- 移动迭代器（move iterator）：
  这些专用的迭代器不是拷贝其中的元素，而是移动它们。

插入迭代器（insert iterator）¶

插入器是一种迭代器适配器,它接受一个容器生成一个迭代器，能实现向给定容器添加元素。
- 三种类型,差异在于元素插入的位置：
  - back_inserter：创建一个使用push_back的迭代器。
  - front_inserter创建一个使用push_front的迭代器。
  - inserter创建一个使用insert的迭代器。接受第二个参数，即一个指向给定容器的
            迭代器，元素会被插到迭代器所指向的元素之前。

- 插入迭代器操作
it=t  在it指定的当前位置插入值t。假定c是it绑定的容器，依赖于插入迭代器的不同种类，
      此赋值会分别调用c.push_back(t)、c.push_front(t)、c.insert(t, p)，
      其中p是传递给inserter的迭代器位置 
*it, ++it, it++  这些操作虽然存在，但不会对it做任何事情，每个操作都返回it  

只有在容器支持push_front的情况下，我们才可以使用front_inserter。
类似的，只有在容器支持push_back的情况下，我们才能使用back_inserter。

插入迭代器（insert iterator）¶

插入器的工作过程是很重要的：
当调用inserter（c，iter）时，我们得到一个迭代器，
接下来使用它时，会将元素插入到iter原来所指向的元素之前的位置。
如果it是由inserter生成的迭代器，则下面这样的赋值语句

*it = val;
//其效果与下面代码一样
it=c.insert(it,val);//it指向新加入的元素
++it;

插入迭代器（insert iterator）¶

front_inserter生成的迭代器的行为与inserter生成的迭代器完全不一样。
当我们使用front_inserter时，元素总是插入到容器第一个元素之前。
//即使我们传递给inserter的位置原来指向第一个元素，
//只要我们在此元素之前插入一个新元素，此元素就不再是容器的首元素了：
list<ins> lst = {1,2,3,4};
list<int> lst2,lst3;//空list
//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则不会。

练习¶

解释三种插入迭代器的不同之处。

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

练习¶

除了 unique 之外，标准库还定义了名为 unique_copy 的函数，
它接受第三个迭代器，表示拷贝不重复元素的目的位置。
编写一个程序，使用 unique_copy将一个vector中不重复的元素
拷贝到一个初始化为空的list中。

#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
#include <iterator>

int main()
{
    std::vector<int> vec{ 1, 1, 3, 3, 5, 5, 7, 7, 9 };
    std::list<int> lst;
    std::unique_copy(vec.begin(), vec.end(), back_inserter(lst));
    for (auto i : lst)
        std::cout << i << " ";
    std::cout << std::endl;
}

练习¶

一个vector 中保存 1 到 9，将其拷贝到三个其他容器中。
分别使用inserter、back_inserter 和 front_inserter 将元素添加到三个容器中。
对每种 inserter，估计输出序列是怎样的，运行程序验证你的估计是否正确。

#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
#include <iterator>
using std::list; using std::copy; using std::cout; using std::endl;

template<typename Sequence>
void print(Sequence const& seq)
{
    for (const auto& i : seq)
        std::cout << i << " ";
    std::cout << std::endl;
}

练习¶

int main()
{
    std::vector<int> vec{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    // uses inserter
    list<int> lst1;
    copy(vec.cbegin(), vec.cend(), inserter(lst1, lst1.begin()));
    print(lst1);

    // uses back_inserter
    list<int> lit2;
    copy(vec.cbegin(), vec.cend(), back_inserter(lit2));
    print(lit2);

    // uses front_inserter
    list<int> lst3;
    copy(vec.cbegin(), vec.cend(), front_inserter(lst3));
    print(lst3);
}

前两种为正序，第三种为逆序，输出和预计一样。

iostream迭代器¶

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

istream_iterator操作¶

当创建一个流迭代器时，必须指定迭代器将要读写的对象类型。
一个istream_iterator使用>>来读取流。
因此，istream_iterator要读取的类型必须定义了输入运算符。
当创建一个istream_iterator时，我们可以将它绑定到一个流。
默认初始化迭代器，创建可以当作尾后值使用的迭代器。

istream_iterator<int> int_it(cin); // reads ints from cin
istream_iterator<int> int_eof;     // end iterator value
ifstream in("afile");
istream_iterator<string> str_it(in);//从afile读字符串

istream_iterator操作¶

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

istream_iterator<int> int_iter(cin); // reads ints from cin
istream_iterator<int> eof;     // end iterator value
while(in_iter!=eof)
    //后置递增运算读取流，返回迭代器旧值
    //解引用迭代器 获得从流读取的前一个值
    vec.push_back(*in_iter++);
//此循环从cin读取int值，保存在vec中。在每个循环步中，循环体代码检查in_iter
//是否等于eof。eof被定义为空的istream_iterator，从而可以当作尾后迭代器来使用。
//对于一个绑定到流的迭代器，一旦其关联的流遇到文件尾或遇到IO错误，
//迭代器的值就与尾后迭代器相等。

//此程序最困难的部分是传递给push_back的参数，
//其中用到了解引用运算符和后置递增运算符。
//该表达式的计算过程与我们之前写过的其他结合解引用和后置递增运算的表达式一样
//后置递增运算会从流中读取下一个值，向前推进，但返回的是迭代器的旧值。
//迭代器的旧值包含了从流中读取的前一个值，对迭代器进行解引用就能获得此值。

istream_iterator操作¶

我们可以将程序重写为如下形式，这体现了istream_iterator更有用的地方：

istream_iterator<int> in_iter(cin),eof;//从cin读取int 
vector<int> vec(in_iter,eof);//从迭代器范围构造vec

//本例中我们用一对表示元素范围的迭代器来构造vec。
//这两个迭代器是istream_iterator，
//这意味着元素范围是通过从关联的流中读取数据获得的。
//这个构造函数从cin中读取数据，直至遇到文件尾或者遇到一个不是int的数据为止。
//从流中读取的数据被用来构造vec。

istream_iterator操作¶

 istream_iterator<T> in(is);in从输入流is读取类型为T的值 
 istream_iterator<T> end;   读取类型是T的值的istream_iterator迭代器，
                            表示尾后位置 
 in1 == in2                 in1和in2必须读取相同类型。
                            如果他们都是尾后迭代器，或绑定到相同的输入，
                            则两者相等。 
 in1 != in2                 类似上条 
 *in                        返回从流中读取的值 
 in->mem                    与*(in).mem含义相同 
 ++in, in++                 使用元素类型所定义的>>运算符从流中读取下一个值。
                            前置版本返回一个指向递增后迭代器的引用，
                            后置版本返回旧值。

使用算法操作流迭代器¶

由于算法使用迭代器操作来处理数据，而流迭代器又至少支持某些迭代器操作，
因此我们至少可以用某些算法来操作流迭代器

下面是一个例子，我们可以用一对istream_iterator来调用accumulate：
istream_iterator<int> in(cin),eof;
cout<<accumulate(in,eof,0)<<endl;
//此调用会计算出从标准输入读取的值的和。

istream_iterator允许使用懒惰求值¶

当我们将一个istream_iterator绑定到一个流时，
标准库并不保证迭代器立即从流读取数据。
具体实现可以推迟从流中读取数据，直到我们使用迭代器时才真正读取。

标准库中的实现所保证的是，在我们第一次解引用迭代器之前，
从流中读取数据的操作已经完成了。

对于大多数程序来说，立即读取还是推迟读取没什么差别。
- 但是，如果我们创建了一个istream_iterator，没有使用就销毁了，
- 或者我们正在从两个不同的对象同步读取同一个流，那么何时读取可能就很重要了。

ostream_iterator操作¶

我们可以对任何具有输出运算符（<<运算符）的类型定义ostream_iterator。
当创建一个ostream_iterator时，我们可以提供（可选的）第二参数，
它是一个字符串，在输出每个元素后都会打印此字符串。
此字符串必须是一个C风格字符串
（即，一个字符串字面常量或者一个指向以空字符结尾的字符数组的指针）。

必须将ostream_iterator绑定到一个指定的流，
不允许空的或表示尾后位置的ostream_iterator。

ostream_iterator操作¶

 ostream_iterator<T> out(os);   out将类型为T的值写到输出流os中 
 ostream_iterator<T> out(os, d);out将类型为T的值写到输出流os中，每个值后面
                                都输出一个d。d指向一个空字符结尾的字符数组。 
 out = val                      用<<运算符将val写入到out所绑定的ostream中。
                                val的类型必须和out可写的类型兼容。 
 *out, ++out, out++             这些运算符是存在的，
                                但不对out做任何事情。每个运算符都返回out。

ostream_iterator操作¶

我们可以用ostream_iterator来输出值的序列：
ostream_iterator<int> out_iter(cout," ");
for(auto e:vec)
    *out_iter++=e;//赋值语句实际将元素写到cout
cout<<endl;
//此程序将vec中的每个元素写到cout，每个元素后加一个空格。
//每次向out_iter赋值时，写操作就会被提交。

ostream_iterator操作¶

//值得注意的是，当我们向out_iter赋值时，可以忽略解引用和递增运算。
//即，循环可以重写成下面的样子：
for(auto e:vec)
    out_iter=e;//赋值语句将元素写到cout
cout<<endl;
//运算符*和++实际上对ostream_iterator对象不做任何事情，
//因此忽略它们对我们的程序没有任何影响。但是，推荐第一种形式。
//在这种写法中，流迭代器的使用与其他迭代器的使用保持一致。
//如果想将此循环改为操作其他迭代器类型，修改起来非常容易。
//而且，对于读者来说，此循环的行为也更为清晰。

ostream_iterator操作¶

//可以通过调用copy来打印vec中的元素，这比编写循环更为简单：
copy(vec.begin(),vec.end(),out_iter);
cout<<endl;

使用流迭代器处理类类型¶

我们可以为任何定义了输入运算符（>>）的类型创建istream_iterator对象。
类似的，只要类型有输出运算符（<<），我们就可以为其定义ostream_iterator。
由于Sales_item既有输入运算符也有输出运算符，
因此可以使用IO迭代器重写书店程序：
    // iterators that can read and write Sales_items
    istream_iterator<Sales_item> item_iter(cin), eof;
    ostream_iterator<Sales_item> out_iter(cout, "\n");
    // store the first transaction in sum and read the next record
    Sales_item sum = *item_iter++;
    while (item_iter != eof) {
        // if the current transaction (which is in item_iter)
        // has the same ISBN
        if (item_iter->isbn() == sum.isbn())
            sum += *item_iter++; // add it to sum
                                 // and read the next transaction
        else {
            out_iter = sum;      // write the current sum
            sum = *item_iter++;  // read the next transaction
        }
    }
    out_iter = sum;  // remember to print the last set of records

使用流迭代器处理类类型¶

//此程序使用item_iter从cin读取Sales_item交易记录，并将和写入cout，
//每个结果后面都跟一个换行符。
//定义了自己的迭代器后，我们就可以用item_iter读取第一条交易记录，
//用它的值来初始化sum：

    // store the first transaction in sum and read the next record
    Sales_item sum = *item_iter++;
//此处，我们对item_iter执行后置递增操作，对结果进行解引用操作。
//这个表达式读取下一条交易记录，并用之前保存在item_iter中的值来初始化sum。
//while循环会反复执行，直至在cin上遇到文件尾为止。
//在while循环体中，我们检查sum与刚刚读入的记录是否对应同一本书。
//如果两者的ISBN不同，我们将sum赋予out_iter，这将会打印sum的当前值，
///并接着打印一个换行符。在打印了前一本书的交易金额之和后，
//我们将最近读入的交易记录的副本赋予sum，并递增迭代器，这将读取下一条交易记录。
//循环会这样持续下去，直至遇到错误或文件尾。
//在退出之前，记住要打印输入中最后一本书的交易金额之和。

练习¶

编写程序，使用流迭代器读取一个文本文件，存入一个vector中的string里。
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <iterator>
using std::string;
int main()
{
    std::ifstream ifs("in.txt");
    std::istream_iterator<string> in(ifs), eof;
    std::vector<string> vec;
    std::copy(in, eof, back_inserter(vec));

    // output
    std::copy(vec.cbegin(),
            vec.cend(), std::ostream_iterator<string>(std::cout, "\n"));
    return 0;
}

练习¶

使用流迭代器、sort 和 copy 从标准输入读取一个整数序列，
将其排序，并将结果写到标准输出。
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

int main()
{
    vector<int> v;
    istream_iterator<int> int_it(cin), int_eof;

    copy(int_it, int_eof, back_inserter(v));
    sort(v.begin(), v.end());

    copy(v.begin(), v.end(), ostream_iterator<int>(cout," "));
    cout << endl;
    return 0;
}

练习¶

修改前一题的程序，使其只打印不重复的元素。你的程序应该使用 unique_copy。
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

int main()
{
    vector<int> v;
    istream_iterator<int> int_it(cin), int_eof;

    copy(int_it, int_eof, back_inserter(v));
    sort(v.begin(), v.end());
    unique_copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));
    cout << endl;
    return 0;
}

练习¶

重写书店程序，使用一个vector保存交易记录，使用不同算法完成处理。
使用 sort 和 compareIsbn 函数来排序交易记录，然后使用 find 和 accumulate 求和。
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <numeric>
#include "Sales_item.h"
int main(){
    std::istream_iterator<Sales_item> in_iter(std::cin), in_eof;
    std::vector<Sales_item> vec;
    while (in_iter != in_eof)
        vec.push_back(*in_iter++);
    sort(vec.begin(), vec.end(), compareIsbn);
    for (auto beg = vec.cbegin(), end = beg; beg != vec.cend(); beg = end) {
        end = find_if(beg, vec.cend(), 
        [beg](const Sales_item &item){ return item.isbn() != beg->isbn(); });
        std::cout << std::accumulate(beg, end, Sales_item(beg->isbn()))
                    << std::endl;
    }
    return 0;
}

练习¶

编写程序，接受三个参数：一个输入文件和两个输出文件的文件名。
输入文件保存的应该是整数。使用 istream_iterator 读取输入文件。
使用 ostream_iterator 将奇数写入第一个输入文件，每个值后面都跟一个空格。
将偶数写入第二个输出文件，每个值都独占一行。
#include <fstream>
#include <iterator>
#include <algorithm>

int main(int argc, char **argv)
{
    if (argc != 4) return -1;
    std::ifstream ifs(argv[1]);
    std::ofstream ofs_odd(argv[2]), ofs_even(argv[3]);
    std::istream_iterator<int> in(ifs), in_eof;
    std::ostream_iterator<int> out_odd(ofs_odd, " "), out_even(ofs_even, "\n");
    std::for_each(in, in_eof, [&out_odd, &out_even](const int i)
    {
        *(i & 0x1 ? out_odd : out_even)++ = i;
    });
    return 0;
}

反向迭代器¶

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

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

 vec.cbegin()     ->     vec.cend()
 v                       v
 [][][][][][][][][][][][]
^                       ^
vec.crend()      <-     vec.crbegin()

反向迭代器¶

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

    vector<int> vec = {0,1,2,3,4,5,6,7,8,9};
    // reverse iterator of vector from back to front
    for (auto r_iter = vec.crbegin(); // binds r_iter to the last element
              r_iter != vec.crend();  // one before first element
              ++r_iter)          // decrements the iterator one element
        cout << *r_iter << endl; // prints 9, 8, 7, . . . 0

//虽然颠倒递增和递减运算符的含义可能看起来令人混淆，
//但这样做使我们可以用算法透明地向前或向后处理容器。
//例如，可以通过向sort传递一对反向迭代器来将vector整理为递减序：

    sort(vec.begin(), vec.end()); // sorts vec in ``normal'' order
    // sorts in reverse: puts the smallest element at the end of vec
    sort(vec.rbegin(), vec.rend());

反向迭代器需要递减运算符¶

只能从既支持++也支持--的迭代器来定义反向迭代器。
- 毕竟反向迭代器的目的是在序列中反向移动。
- 除了forward_list之外，标准容器上的其他迭代器都既支持递增运算又支持递减运算。
- 但是，流迭代器不支持递减运算，因为不可能在一个流中反向移动。
    - 因此，不可能从一个forward_list或一个流迭代器创建反向迭代器。

反向迭代器和其他迭代器间的关系¶

假定有一个名为line的string，保存着一个逗号分隔的单词列表，
我们希望打印line中的第一个单词。使用find可以很容易地完成这一任务：
    // 在一个逗号分隔的列表中查找第一个元素
    // find the first element in a comma-separated list
    auto comma = find(line.cbegin(), line.cend(), ',');
    cout << string(line.cbegin(), comma) << endl;
//如果line中有逗号，那么comma将指向这个逗号；否则，它将等于line.cend（）。
//当我们打印从line.cbegin（）到comma之间的内容时，将打印到逗号为止的字符，
//或者打印整个string（如果其中不含逗号的话）。

反向迭代器和其他迭代器间的关系¶

//如果希望打印最后一个单词，可以改用反向迭代器：

    // find the last element in a comma-separated list
    auto rcomma = find(line.crbegin(), line.crend(), ',');
//由于我们将crbegin（）和crend（）传递给find，find将从line的最后一个字符
//开始向前搜索。当find完成后，如果line中有逗号，则rcomma指向最后一个逗号
//即，它指向反向搜索中找到的第一个逗号。如果line中没有逗号，则rcomma指向
//line.crend（）。当我们试图打印找到的单词时，最有意思的部分就来了。
//看起来下面的代码是显然的方法

    // WRONG: will generate the word in reverse order
    cout << string(line.crbegin(), rcomma) << endl;
    // FIRST,MIDDLE,LAST -> TSAL
//但它会生成错误的输出结果。
//例如，如果我们的输入是FIRST,MIDDLE,LAST则这条语句会打印TSAL！

反向迭代器和其他迭代器间的关系¶

cbegin() comma    rcomma.base()  cend()
v    ->   v               v ->   v
F I R S T , M I D D L E , L A S T
                        ^   <-  ^
                    rcomma      crbegin()

问题所在：我们使用的是反向迭代器，会反向处理string。
因此，上述输出语句从crbegin开始反向打印line中内容。
而我们希望按正常顺序打印从rcomma开始到line末尾间的字符。
但是，我们不能直接使用rcomma。因为它是一个反向迭代器，意味着它会反向朝着
string的开始位置移动。需要做的是，将rcomma转换回一个普通迭代器，
能在line中正向移动。我们通过调用reverse_iterator的base成员函数来完成这一转换，
此成员函数会返回其对应的普通迭代器：

    // ok: get a forward iterator and read to the end of line
    cout << string(rcomma.base(), line.cend()) << endl;
给定和之前一样的输入，这条语句会如我们的预期打印出LAST。

反向迭代器和其他迭代器间的关系¶

cbegin() comma    rcomma.base()  cend()
v    ->   v               v ->   v
F I R S T , M I D D L E , L A S T
                        ^   <-  ^
                    rcomma      crbegin()


这里显示了普通迭代器与反向迭代器之间的关系。
例如，rcomma和rcomma.base（）指向不同的元素，line.crbegin和line.cend（）
也是如此。这些不同保证了元素范围无论是正向处理还是反向处理都是相同的。

从技术上讲，普通迭代器与反向迭代器的关系反映了左闭合区间的特性。
关键点在于[line.crbegin（），rcomma）和[rcomma.base（），line.cend（））
指向line中相同的元素范围。
为了实现这一点，rcomma和rcomma.base（）必须生成相邻位置而不是相同位置，
crbegin（）和cend（）也是如此。

反向迭代器的目的是表示元素范围，而这些范围是不对称的，
这导致一个重要的结果：当我们从一个普通迭代器初始化一个反向迭代器，
或是给一个反向迭代器赋值时，结果迭代器与原迭代器指向的并不是相同的元素。

练习¶

使用 reverse_iterator 逆序打印一个vector。
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    for (auto it = v.crbegin(); it != v.crend(); ++it)
    {
        cout << *it << endl;
    }

    return 0;
}

练习¶

使用普通迭代器逆序打印一个vector。
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    for (auto it = std::prev(v.cend()); true; --it)
    {
        std::cout << *it << " ";
        if (it == v.cbegin()) break;
    }
    std::cout << std::endl;

    return 0;
}

练习¶

使用 find 在一个 int 的list 中查找最后一个值为0的元素。
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int main()
{
    list<int> l = { 1, 2, 0, 4, 5, 6, 7, 0, 9 };
    auto it = find(l.crbegin(), l.crend(), 0);

    cout << distance(it, l.crend()) << endl;
    return 0;
}

练习¶

给定一个包含10 个元素的vector，将位置3到7之间的元素按逆序拷贝到一个list中。
#include <iostream>
#include <list>
#include <algorithm>
#include <vector>
#include <iterator>
using namespace std;
int main()
{
    vector<int> v = { 0,1, 2, 3, 4, 5, 6, 7, 8, 9 };
    list<int> l;

    copy(v.crbegin() + 2, v.crbegin() + 7, back_inserter(l));

    for (auto i : l) std::cout << i << " ";
    cout << endl;
    return 0;
}

泛型算法结构¶

任何算法的最基本的特性是它要求其迭代器提供哪些操作。
- 某些算法，如find，只要求通过迭代器访问元素、递增迭代器以及
  比较两个迭代器是否相等这些能力。
- 其他一些算法，如sort，还要求读、写和随机访问元素的能力。
算法所要求的迭代器操作可以分为5个迭代器类别（iterator category）
每个算法都会对它的每个迭代器参数指明须提供哪类迭代器。

 输入迭代器  只读，不写；单遍扫描，只能递增  ==,!=,++,*,-> 
 输出迭代器  只写，不读；单遍扫描，只能递增  ++,* 
 前向迭代器  可读写；多遍扫描，只能递增  ==,!=,++,*,-> 
 双向迭代器  可读写；多遍扫描，可递增递减  ==,!=,++,--,*,-> 
 随机访问迭代器  可读写，多遍扫描，支持全部迭代器运算 
                 ==,!=,<,<=,>,>=,++,--,+,+=,-,-=,*,->,iter[n]==*(iter[n]) 

第二种算法分类的方式是按照是否读、写或是重排序列中的元素来分类。
附录A按这种分类方法列出了所有算法。
算法还共享一组参数传递规范和一组命名规范。

5类迭代器¶

类似容器，迭代器也定义了一组公共操作。
一些操作所有迭代器都支持，另外一些只有特定类别的迭代器才支持。
- ostream_iterator只支持递增、解引用和赋值。
- vector、string和deque的迭代器除了这些操作外，还支持递减、关系和算术运算。
迭代器是按它们所提供的操作来分类的，而这种分类形成了一种层次。
除了输出迭代器之外，一个高层类别的迭代器支持低层类别迭代器的所有操作。

C++标准指明了泛型和数值算法的每个迭代器参数的最小类别。
- 例如，find算法在一个序列上进行一遍扫描，对元素进行只读操作，
    因此至少需要输入迭代器。
- replace函数需要一对迭代器，至少是前向迭代器。
- 类似的，replace_copy的前两个迭代器参数也要求至少是前向迭代器。
    其第三个迭代器表示目的位置，必须至少是输出迭代器。
    其他的例子类似。
对每个迭代器参数来说，其能力必须与规定的最小类别至少相当。
向算法传递一个能力更差的迭代器会产生错误。

对于向一个算法传递错误类别的迭代器的问题，很多编译器不会给出任何警告或提示。

迭代器类别输入迭代器 input iterator¶

输入迭代器（input iterator）：可以读取序列中的元素。
一个输入迭代器必须支持
- 用于比较两个迭代器的相等和不相等运算符（==、！=）
- 用于推进迭代器的前置和后置递增运算（++）
- 用于读取元素的解引用运算符（*）；解引用只会出现在赋值运算符的右侧
- 箭头运算符（->），等价于（*it）.member，即，解引用迭代器，并提取对象的成员

输入迭代器只用于顺序访问。对于一个输入迭代器，
*it++保证是有效的，但递增它可能导致所有其他指向流的迭代器失效。
其结果就是，不能保证输入迭代器的状态可以保存下来并用来访问元素。
因此，输入迭代器只能用于单遍扫描算法。
- 算法find和accumulate要求输入迭代器；
- 而istream_iterator是一种输入迭代器。

输出迭代器（output iterator）：¶

可以看作输入迭代器功能上的补集——只写而不读元素。输出迭代器必须支持
- 用于推进迭代器的前置和后置递增运算（++）
- 解引用运算符（*），只出现在赋值运算符的左侧
    （向一个已经解引用的输出迭代器赋值，就是将值写入它所指向的元素）

我们只能向一个输出迭代器赋值一次。
类似输入迭代器，输出迭代器只能用于单遍扫描算法。
用作目的位置的迭代器通常都是输出迭代器。
- 例如，copy函数的第三个参数就是输出迭代器。
- ostream_iterator类型也是输出迭代器。

前向迭代器（forward iterator）¶

可以读写元素。这类迭代器只能在序列中沿一个方向移动。
前向迭代器支持所有输入和输出迭代器的操作，而且可以多次读写同一个元素。
因此，我们可以保存前向迭代器的状态，使用前向迭代器的算法可以对序列进行多遍扫描。
- 算法replace要求前向迭代器
- forward_list上的迭代器是前向迭代器。

双向迭代器（bidirectional iterator）¶

可以正向/反向读写序列中的元素。
除了支持所有前向迭代器的操作之外，双向迭代器还支持前置和后置递减运算符（--）。
- 算法reverse要求双向迭代器
- 除了forward_list之外，其他标准库都提供符合双向迭代器要求的迭代器。

随机访问迭代器（random-access iterator）¶

提供在常量时间内访问序列中任意元素的能力。
此类迭代器支持双向迭代器的所有功能，此外还支持
- 用于比较两个迭代器相对位置的关系运算符（<、<=、>和>=）
- 迭代器和一个整数值的加减运算（+、+=、-和-=），
    计算结果是迭代器在序列中前进（或后退）给定整数个元素后的位置
- 用于两个迭代器上的减法运算符（-），得到两个迭代器的距离
- 下标运算符（iter[n]），与＊（iter[n]）

等价算法sort要求随机访问迭代器。
array、deque、string和vector的迭代器都是随机访问迭代器，
    用于访问内置数组元素的指针也是。

练习¶

列出5个迭代器类别，以及每类迭代器所支持的操作。

输入迭代器 : ==,!=,++,*,->
输出迭代器 : ++,*
前向迭代器 : ==,!=,++,*,->
双向迭代器 : ==,!=,++,--,*,->
随机访问迭代器 : ==,!=,<,<=,>,>=,++,--,+,+=,-,-=,*,->,iter[n]==*(iter[n])

练习¶

list 上的迭代器属于哪类？vector呢？

list 上的迭代器是 双向迭代器
vector 上的迭代器是 随机访问迭代器

练习¶

你认为 copy 要求哪类迭代器？reverse 和 unique 呢？

copy 需要两个输入迭代器，一个输出迭代器
reverse 需要双向迭代器
unique需要随机访问迭代器

算法形参模式¶

在任何其他算法分类之上，还有一组参数规范。
理解这些参数规范对学习新算法很有帮助——通过理解参数的含义，
可以将注意力集中在算法所做的操作上。大多数算法具有如下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表示算法所操作的输入范围。
几乎所有算法都接受一个输入范围，是否有其他参数依赖于要执行的操作。
这里列出了常见的一种——dest、beg2和end2，都是迭代器参数。
顾名思义，如果用到了这些迭代器参数，它们分别承担指定目的位置和第二个范围的角色。
除了这些迭代器参数，一些算法还接受额外的、非迭代器的特定参数。

接受单个目标迭代器的算法¶

dest参数是一个表示算法可以写入的目的位置的迭代器。
算法假定（assume）：按其需要写入数据，不管写入多少个元素都是安全的。

向输出迭代器写入数据的算法都假定目标空间足够容纳写入的数据。
如果dest是一个直接指向容器的迭代器，那么算法将输出数据写到容器中已存在的元素内。
- 更常见的情况是，dest被绑定到一个插入迭代器或是一个ostream_iterator
- 插入迭代器会将新元素添加到容器中，因而保证空间是足够的。
- ostream_iterator会将数据写入到一个输出流，同样不管要写入多少个元素都没有问题。

接受第二个输入序列的算法¶

接受单独的beg2或是接受beg2和end2的算法用这些迭代器表示第二个输入范围。
这些算法通常使用第二个范围中的元素与第一个输入范围结合来进行一些运算。

如果一个算法接受beg2和end2，这两个迭代器表示第二个范围。
这类算法接受两个完整指定的范围：
- [beg，end）表示的范围和[beg2 end2）表示的第二个范围。

只接受单独的beg2（不接受end2）的算法将beg2作为第二个输入范围中的首元素。
此范围的结束位置未指定，
这些算法假定从beg2开始的范围与beg和end所表示的范围至少一样大。

接受单独beg2的算法假定从beg2开始的序列与beg和end所表示的范围至少一样大。

算法命名规范¶

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

一些算法使用重载形式传递一个谓词¶

接受谓词参数来代替<或==运算符的算法，
以及那些不接受额外参数的算法，通常都是重载的函数。
- 函数的一个版本用元素类型的运算符来比较元素；
- 另一个版本接受一个额外谓词参数，来代替<或==：

unique(beg,end);
unique(beg,end,comp);

两个调用都重新整理给定序列，将相邻的重复元素删除。
- 第一个调用使用元素类型的==运算符来检查重复元素；
- 第二个则调用comp来确定两个元素是否相等。
由于两个版本的函数在参数个数上不相等，因此具体应该调用哪个版本不会产生歧义

_if版本的算法¶

接受一个元素值的算法通常有另一个不同名的（不是重载的）版本，
该版本接受一个谓词代替元素值。接受谓词参数的算法都有附加的_if前缀：

find(beg,end,val);
find_if(beg,end,pred);

这两个算法都在输入范围中查找特定元素第一次出现的位置。
- 算法find查找一个指定值；
- 算法find_if查找使得pred返回非零值的元素。

这两个算法提供了命名上差异的版本，而非重载版本，
因为两个版本的算法都接受相同数目的参数。
因此可能产生重载歧义，虽然很罕见，
但为了避免任何可能的歧义，标准库选择提供不同名字的版本而不是重载。

区分拷贝元素的版本和不拷贝的版本¶

默认情况下，重排元素的算法将重排后的元素写回给定的输入序列中。
这些算法还提供另一个版本，将元素写到一个指定的输出目的位置。
如我们所见，写到额外目的空间的算法都在名字后面附加一个_copy

reverse(beg,end);
reverse_copy(beg,end,dest);

一些算法同时提供_copy和_if版本。这些版本接受一个目的位置迭代器和一个谓词：

//从v1删除奇数
remove_if(v1.begin(),v1.end(),
            [](int i){return i%2;});
//将偶数元素从v1拷贝到v2，v1不变
remove_copy_if(v1.begin(),v1.end(),back_inserter(v2),
            [](int i){return i%2;});
两个算法都调用了lambda来确定元素是否为奇数。
- 在第一个调用中，我们从输入序列中将奇数元素删除。
- 在第二个调用中，我们将非奇数（亦即偶数）元素从输入范围拷贝到v2中。

练习¶

仅根据算法和参数的名字，描述下面每个标准库算法执行什么操作：

replace(beg, end, old_val, new_val);
replace_if(beg, end, pred, new_val);
replace_copy(beg, end, dest, old_val, new_val);
replace_copy_if(beg, end, dest, pred, new_val);

replace 在迭代器范围内用新值替换所有原来的旧值。
replace_if 在迭代器范围内，满足谓词条件的元素用新值替换。
replace_copy 复制迭代器范围内的元素到目标迭代器位置，
             如果元素等于某个旧值，则用新值替换
replace_copy_if 复制迭代器范围内的元素到目标迭代器位置，
                满足谓词条件的元素用新值替换

特定容器算法¶

与其他容器不同，链表类型list和forward_list定义了几个成员函数形式的算法
- 特别是，它们定义了独有的sort、merge、remove、reverse和unique。
- 通用版本的sort要求随机访问迭代器，因此不能用于list和forward_list，
    因为这两个类型分别提供双向迭代器和前向迭代器。

链表类型定义的其他算法的通用版本可以用于链表，但代价太高。
这些算法需要交换输入序列中的元素。
一个链表可以通过改变元素间的链接而不是真的交换它们的值来快速“交换”元素。
因此，这些链表版本的算法的性能比对应的通用版本好得多。

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

list和forward_list成员函数版本的算法¶

 lst.merge(lst2)  将来自lst2的元素合并入lst，二者都必须是有序的，
                    元素将从lst2中删除。 
 lst.merge(lst2, comp)  同上，给定比较操作。 
 lst.remove(val)  调用erase删除掉与给定值相等(==)的每个元素 
 lst.remove_if(pred)  调用erase删除掉令一元谓词为真的每个元素 
 lst.reverse()  反转lst中元素的顺序 
 lst.sort()  使用<排序元素 
 lst.sort(comp)  使用给定比较操作排序元素 
 lst.unique()  调用erase删除同一个值的连续拷贝。使用==。 
 lst.unique(pred)  调用erase删除同一个值的连续拷贝。使用给定的二元谓词。 

- 上面的操作都返回void

splice成员¶

链表类型还定义了splice算法，此算法是链表数据结构所特有的，因此不需要通用版本。
lst.splice(args) 或 flst.splice_after(args)
(p, lst2)  p是一个指向lst中元素的迭代器，或者一个指向flst首前位置的迭代器。
           函数将lst2中的所有元素移动到lst中p之前的位置或是flst中p之后的位置。
           将元素从lst2中删除。lst2的类型必须和lst相同，而且不能是同一个链表。 
(p, lst2, p2)   同上，p2是一个指向lst2中位置的有效的迭代器，
                将p2指向的元素移动到lst中，
                或将p2之后的元素移动到flst中。lst2可以是于lst或flst相同的链表。 
(p, lst2, b, e) b和e表示lst2中的合法范围。
                将给定范围中的元素从lst2移动到lst或first中。
                lst2与lst可以使相同的链表，但p不能指向给定范围中的元素。

链表特有的操作会改变容器¶

多数链表特有的算法都与其通用版本很相似，但不完全相同。
链表特有版本与通用版本间的一个至关重要的区别是链表版本会改变底层的容器。
- 例如，remove的链表版本会删除指定的元素。
- unique的链表版本会删除第二个和后继的重复元素。
类似的，merge和splice会销毁其参数。
- 通用版本的merge将合并的序列写到一个给定的目的迭代器；两个输入序列是不变的。
- 而链表版本的merge函数会销毁给定的链表——元素从参数指定的链表中删除，
    被合并到调用merge的链表对象中。
    在merge之后，来自两个链表中的元素仍然存在，但它们都已在同一个链表中。

练习¶

使用 list 代替 vector 重新实现除重复单词的程序。
#include <iostream>
#include <string>
#include <list>

using std::string; using std::list;

void elimDups(list<string> &words)
{
    words.sort();
    words.unique();
}

int main()
{
    list<string> l = { "aa", "aa", "aa", "aa", "aasss", "aa" };
    elimDups(l);
    for (const auto& e : l)
        std::cout << e << " ";
    std::cout << std::endl;
}

实践课¶

从课程主页 cpp.njuer.org 打开《面向对象编程基础》实验课 cloud shell界面 https://developer.aliyun.com/adc/scenario/476f2ff6afad4221bac08e33cf6984fc
使用g++编译代码
编辑一个 readme.md 文档,键入本次实验心得.

使用git进行版本控制可使用之前的gitee代码仓库

  - 云服务器（elastic compute service,简称ecs）
  - aliyun linux 2是阿里云推出的 linux 发行版
  - vim是从vi发展出来的一个文本编辑器.
  - g++ 是c++编译器

习题1
给定一个包含10 个元素的vector，将位置1到6之间的元素按逆序拷贝到一个list中。

习题2
编写程序，接受三个参数：一个输入文件和两个输出文件的文件名。
输入文件保存的应该是整数。使用 istream_iterator 读取输入文件。
使用 ostream_iterator 将奇数写入第一个输入文件，每个值后面都跟一个空格。
将偶数写入第二个输出文件，每个值都独占一行。

习题3
重写书店程序，使用一个vector保存交易记录，使用不同算法完成处理。
使用 sort 和10.3.1节中的 compareIsbn 函数来排序交易记录，
然后使用 find 和 accumulate 求和。

编辑c++代码和markdown文档,使用git进行版本控制
yum install -y git gcc-c++
使用git工具进行版本控制
git clone你之前的网络git仓库test(或其它名字)
cd test 进入文件夹test
(clone的仓库,可移动旧文件到目录weekN:  mkdir -p weekN ; mv 文件名 weekN;)

vim test1.cpp
g++ ./test1.cpp 编译
./a.out 执行程序

vim test2.cpp
g++ ./test2.cpp 编译
./a.out 执行程序

vim test3.cpp
g++ ./test3.cpp 编译
./a.out 执行程序

git add . 加入当前文件夹下所有文件到暂存区
git config --global user.email "you@example.com"
git config --global user.name "Your Name"
vim readme.md 键入新内容（实验感想),按ESC 再按：wq退出
git add .
git commit –m "weekN" 表示提交到本地,备注weekN

git push 到你的git仓库

git log --oneline --graph 可看git记录
键入命令并截图或复制文字,并提交到群作业.
cat test* readme.md

提交¶

截图或复制文字,提交到群作业.
填写阿里云平台（本实验）的网页实验报告栏,发布保存.本次报告不需要分享提交
填写问卷调查 https://rnk6jc.aliwork.com/o/cppinfo

关于使用tmux¶

sudo yum install -y tmux
cd ~ && wget https://cpp.njuer.org/tmux && mv tmux .tmux.conf
tmux 进入会话 .
前缀按键prefix= ctrl+a, 
prefix+c创建新面板,
prefix+"分屏,
prefix+k选上面,prefix+j选下面,
prefix+1选择第一,prefix+n选择第n,
prefix+d脱离会话
tmux attach-session -t 0 回到会话0

vim 共分为三种模式¶

- 命令模式
  - 刚启动 vim,便进入了命令模式.其它模式下按ESC,可切换回命令模式
    - i 切换到输入模式,以输入字符.
    - x 删除当前光标所在处的字符.
    - : 切换到底线命令模式,可输入命令.
- 输入模式
  - 命令模式下按下i就进入了输入模式.
    - ESC,退出输入模式,切换到命令模式
- 底线命令模式
  - 命令模式下按下:（英文冒号）就进入了底线命令模式.
    - wq 保存退出

vim 常用按键说明¶

除了 i, Esc, :wq 之外,其实 vim 还有非常多的按键可以使用.命令模式下：
- 光标移动
  - j下 k上 h左 l右
  - w前进一个词 b后退一个词
  - Ctrl+d 向下半屏  ctrl+u 向上半屏
  - G 移动到最后一行 gg 第一行 ngg 第n行
- 复制粘贴
  - dd 删一行 ndd 删n行
  - yy 复制一行 nyy复制n行
  - p将复制的数据粘贴在下一行 P粘贴到上一行
  - u恢复到前一个动作 ctrl+r重做上一个动作
- 搜索替换
  - /word 向下找word     ？word 向上找
  - n重复搜索 N反向搜索
  - :1,$s/word1/word2/g从第一行到最后一行寻找 word1 字符串,并将该字符串
    取代为 word2

vim 常用按键说明¶

底线命令模式下：
- :set nu   显示行号
- :set nonu 取消行号
- :set paste    粘贴代码不乱序
【注：把caps lock按键映射为ctrl,能提高编辑效率.】

Markdown 文档语法¶

# 一级标题
## 二级标题
*斜体* **粗体**
- 列表项
  - 子列表项
> 引用
[超链接](http://asdf.com)
![图片名](http://asdf.com/a.jpg)

|表格标题1|表格标题2|
 |-|-|
|内容1|内容2|