《C++ Primer》学习笔记（十）：泛型算法

╰半夏微凉° 2023-03-13 13:50 24阅读 0赞

### 《C++ Primer》学习笔记（十）：泛型算法 ###

*  初识泛型算法
 *   *  只读算法
     *  写容器元素的算法
     *  重排容器元素的算法
 *  定制操作
 *   *  向算法传递函数
     *  lambda表达式
     *  参数绑定
 *  再探迭代器
 *   *  插入迭代器
     *  iostream迭代器
     *   *  istream\_iterator操作
         *  ostream\_iterator操作
     *  反向迭代器
     *   *  反向迭代器与普通迭代器的转换
 *  泛型算法结构
 *   *  迭代器类别
     *  算法参数模式
     *   *  if版本的算法
         *  区分拷贝元素的版本和不拷贝元素的版本
 *  特定容器算法
 *  练习

泛型算法是一组公共接口，可以用于不同类型的元素和多种容器类型。

**泛型算法本身不会执行容器的操作，只会运行于特定迭代器上，执行迭代器的操作，即不会改变底层容器的大小。但是标准库定义了一类特殊的迭代器：插入器（inserter)。与普通迭代器只能遍历所绑定的容器相比，插入器能做更多的事情。当给这类迭代器赋值时，它们会在底层的容器上执行插入操作。因此当一个算法操作这样的迭代器时，迭代器可以完成向容器添加元素的操作，但算法自身则不会做插入操作。**

# 初识泛型算法 #

## 只读算法 ##

**对于只读取而不改变元素的算法，最好使用`cbegin()`和`cend()`。但是，如果你计划使用算法返回的迭代器来改变元素的值，就需要使用`begin()`和`end()`的结果作为参数。**

//对vec中的元素求和，和的初值是0
    int sum = accumulate(vec.cbegin(), vec.cend(), 0);//accumulate的第三个参数的类型决定了函数中使用哪个加法运算符以及返回值的类型
    
    string sum = accumulate(v.cbegin(), v.cend(), string("") );//正确
    string sum accumulate(v.cbegin(), v.cend(), "" );//错误：const char*上没有定义+运算符

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

//确定两个序列是否保存相同的值
    //roster2中的元素数目应该至少与roster1一样多
    equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());

## 写容器元素的算法 ##

向目的位置迭代器写入数据的算法假定目的位置足够大，能容纳要写入的元素。要保证这一点，可以使用**插入迭代器（insert iterator)**。当我们通过一个插入迭代器赋值时，一个与赋值号右侧值相等的元素被添加到容器中。

vector<int> vec; //空容器
    //灾难：修改vec中的10个（不存在）元素
    fill_n(vec.bigin(), 10, 0);
    
    auto it = back_inserter(vec);//back_inserter()返回与该容器绑定的插入迭代器
    *it = 42; //vec中现在有一个元素42
    
    fill_n(back_inserter(vec), 10, 0);//添加10个元素0到vec

**拷贝（copy）算法**是另一个向目的位置迭代器指向的输出序列中的元素写入数据的算法。传递给`copy`的目的序列至少要包含与输入序列一样多的元素。

int a1[] = {
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int a2[sizeof(a1)/sizeof(*a1)];//a2与a1大小一样
    //ret指向拷贝到a2的尾元素之后的位置
    auto ret = copy(begin(a1), end(a1), a2);//把a1的内容拷贝给a2
    
    //将所有值为0的元素改为42
    replace(ilst.begin(), ilst.end(), 0, 42);
    
    //使用back_inserter按需要增长目标序列
    replace_copy(ilst.cbegin(), ilst.cend(), back_inserter(ivec), 0, 42);
    //此调用后，ilst并未改变，ivec包含ilst的一份拷贝，不过原来在ilst中值为0的元素在ivec中都变为42

## 重排容器元素的算法 ##

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());
    }

![在这里插入图片描述][20200514170032162.png]  
完成`sort`操作后：  
![在这里插入图片描述][20200514170053894.png]  
使用`unique`消除相邻重复项后：  
![在这里插入图片描述][20200514170131440.png]

# 定制操作 #

标准库允许我们为某些算法提供自己定义的操作来代替默认运算符。

## 向算法传递函数 ##

加入我们希望对一个单词序列进行重排，首先按长度排序，大小相同的再按字典序排序。那么默认的`sort`就无法完成这个操作，需要我们使用重载的`sort`版本，它接受一个**谓词**作为第三个参数。

**谓词**是一个可调用的表达式，其返回结果是一个能用作条件的值。**一元谓词**只接受单一参数，**二元谓词**接受两个参数。接受谓词作为参数的算法会对输入序列中的元素调用谓词。因此元素类型必须能够转换为谓词的参数类型。

bool isShorter(const string &s1, const string &s2)
    {
        
    	return s1.size() < s2.size(); //长度较短的单词排在更前面
    }
    
    //按长度由短至长排序words
    sort(words.begin(), words.end(), isShorter);

elimDups(words); //将words按字典序重排，并消除重复单词
    //按长度重新排序，长度相同的单词维持字典序
    stable_sort(words.begin(), words.end(), isShorter);

## lambda表达式 ##

标准库`find_if`算法接受一对表示范围的迭代器和一个谓词，对范围内的每个元素调用给定的这个谓词，函数返回第一个使谓词返回非0值的元素。如果不存在这样的元素则返回尾迭代器。

一个`lambda`表达式 表示一个可调用的代码单元，具有如下形式：

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

可以忽略参数列表和返回类型，但是必须包含捕获列表和函数体：

//定义一个可调用对象f, 它不接受参数，返回42
    auto f = [] {
        return 42;} ;
    
    cout << f() << endl; //输出42

`lambda`表达式不能有默认参数。

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

一个`lambda`只有在其捕获列表中捕获一个它所在函数中的局部非`static`变量，才能在函数体中使用该变量。但是对于局部`static`变量和它所在函数之外声明的名字，它可以直接使用。

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

`lambda`的变量捕获形式可以是值或引用。采用值捕获的前提是变量可以拷贝。与参数不同，被捕获的变量的值是在`lambda`创建时拷贝，而不是调用时拷贝：

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

在引用捕获或者返回引用的时候需要注意，必须确保被引用的对象在`lambda`执行的时候时存在的。

当定义一个`lambda`时，编译器生成一个与`lambda`对应的新的（未命名的）类类型。因此函数可以返回一个`lambda`，但是要注意与不能返回一个局部变量的引用类似，这个返回的`lambda`不能包含引用捕获。

除了显示列出我们需要捕获的变量外，还可以采用**隐式捕获**形式，在捕获列表中写一个`&`（表示采用引用捕获方式）或者`=`（表示采用值捕获方式）。让编译器来推断需要捕获哪些变量。也**可以混合使用隐式捕获和显式捕获**，但是当混合使用时，捕获列表的第一个元素必须是`&`或`=`，它指定了默认捕获方式。

//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;});

我们应该**尽可能减少捕获的数据量**，来避免潜在的捕获导致的问题。如果可能，避免捕获指针或引用。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70]

## 参数绑定 ##

通过标准库`bind`函数，可以为一个已有的函数绑定一个参数列表。`bind`定义在头文件`functional`中。

auto newCallable = bind(callable, arg_list);

`arg_list`是一个逗号分隔的参数列表，当我们调用`newCallable`时 ，`newCallable`会调用`callable`，并传递给它`arg_list`中的参数。

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

//check6是一个可调用对象，接受一个string类型的参数
    //并用此string和值6来调用check_size
    auto check6 = bind(check_size, _1, 6);
    //此bind调用只有一个占位符，表示check6只接受单一参数。占位符出现在arg_list的第一个位置，表明check6的此参数对应check_size的第一个参数，此参数是一个const string&
    
    string s = "hello";
    bool b1 = check6(s); //check6(s)会调用check_size(s, 6)
    
    //g是一个有两个参数的可调用对象
    auto g = bind(f, a, b, _2, c, _1);
    
    则g(X, Y)等效于调用f(a, b, Y, c, X)

名字`_n`都定义在一个名为`placeholders`的命名空间中，而这个命名空间本身定义在`std`命名中间中，因此在使用占位符名字前，我们需要做一个`using`声明：

using namespace std::placeholders;

还可以使用`bind`来**重排参数顺序**：

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

由于默认情况下，`bind`的那些不是占位符的参数被拷贝到`bind`返回的可调用对象中。但是有些情况我们需要绑定引用参数，那么这时就必须使用标准库`ref`函数：

//os是一个局部变量，引用一个输出流
    //c是一个局部变量，类型为char
    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;
    }
    
    //错误：不能拷贝os
    for_each(words.begin(), words.end(), bind(print, os, _1, ' '));
    
    for_each(words.begin(), words.end(), bind(print, ref(os), _1, ' '));

`ref`返回一个对象，包含给定的引用，此对象是可拷贝的。类似的，`cref`生成一个保存`const`引用的类。

# 再探迭代器 #

除了为每个容器定义的迭代器外，标准库在头文件`iterator`中还定义了额外的几种迭代器：

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

## 插入迭代器 ##

根据插入元素的位置不同，分为三种：

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

![在这里插入图片描述][20200515171302587.png]

list<int> 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()) );

## iostream迭代器 ##

`istream_iterator`读取输入流，`ostream_iterator`向一个输出流写数据。通过使用流迭代器，我们可以用泛型算法从流对象读数据以及向其写入数据。

我们可以为任何定义了输入运算符（`>>`）的类型创建`istream_iterator`对象。类似的，可以为任何定义了输出运算符(`<<`)的类型创建`ostream_iterator`对象。

### istream\_iterator操作 ###

istream_iterator<int> int_iter(cin); //从cin读取int
    istream_iterator<int> int_eof; //默认初始化的迭代器可以当作尾后迭代器来使用
    
    while(int_iter != int_eof) //当有数据可供读取时
        vec.push_back(*int_iter++);
    
    ifstream in("afile");
    istream_iterator<string> str_in(in);//从"afile"读取字符串

`istream_iterator`更有用的地方如下：

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 1]

//使用算法操作流迭代器
    istream_iterator<int> in(cin), eof;
    //计算从标准输入读取的值的和
    cout << accumulate(in, eof, 0) << endl;

### ostream\_iterator操作 ###

![在这里插入图片描述][20200515180411769.png]

ostream_iterator<int> out_iter(cout, " ");
    for(auto e : vec)
    	*out_iter++ = e; //赋值语句实际上将元素写到cout
    cout << endl;
    
    //通过调用copy来打印vec中的元素，相比于编写循环更简单
    copy(vec.begin(), vec.end(), out_iter);
    cout << endl;

## 反向迭代器 ##

对于反向迭代器，递增和递减的操作含义会反过来。

除了`forward_list`外，其他容器都支持反向迭代器。可通过`rbegin`、`rend`、`crbegin`和`crend`来获取。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 2]  
可以通过向`sort`传递一对反向迭代器来实现递减排序：

sort(vec.begin(), vec.end());//递增排序
    
    sort(vec.rbegin(), vec.rend());//递减排序

### 反向迭代器与普通迭代器的转换 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 3]

//在一个逗号分隔的列表中查找第一个元素
    auto comma = find(line.cbegin(), line.cend(), ',');
    cout << string(line.cbegin(), comma) << endl; //打印第一个单词
    
    //如果希望打印最后一个单词，可以改用反向迭代器
    //在一个逗号分隔的列表中查找最后一个元素
    auto rcomma = find(line.crbegin(), line.crend(), ',');
    //错误：将输出逆序单词。例如如果我们输入的是first,mid,last  则输出是tsal
    cout << string(line.crbegin(), rcomma) << endl;
    //我们需要调用base成员函数将rcomma转换为一个普通迭代器（即正向迭代器）
    //正确：得到一个正向迭代器，则输出是last
    cout << string(rcomma.base(), line.cend()) << endl;

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

# 泛型算法结构 #

每个算法都会对它的每个迭代器参数指明必须提供哪类迭代器。

一个高层类别的迭代器支持低层类别的迭代器的所有操作。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 4]  
C++标准指明了泛型和数值算法的每个迭代器参数的最小类别。

## 迭代器类别 ##

**输入迭代器**必须支持：

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

**输出迭代器**必须支持：

*  用于推进迭代器的前置和后置递增运算(`++`)
 *  解引用运算符（`*`），只能出现在赋值运算符左侧（向一个已经解引用的输出迭代器赋值，就是将值写入它所指向的元素）

**前向迭代器**支持所有输入和输出迭代器的操作，而且可以多次读写同一个元素（即可以对序列进行多遍扫描）。

**双向迭代器**除了支持所有前向迭代器的操作外，还支持前置和后置递减运算符(`--`)。

**随机访问迭代器**支持双向迭代器的所有操作，并且还支持下列操作：

*  用于比较两个迭代器相对位置的关系运算符(`<`、`<=`、`>`和`>=`)
 *  迭代器和一个整数值的加减运算(`+`、`+=`、`-`和`-=`)，计算结果是迭代器在序列中前进（或后退）给定整数个元素后的位置。
 *  用于两个迭代器上的减法运算符(`-`)，得到两个迭代器间的距离。
 *  下标运算符(`iter[n]`)，与`*(iter[n])`等价。

## 算法参数模式 ##

alg(beg, end, other args);
    alg(beg, end, dest, other args); //假定目标空间足够容纳写入的数据
    alg(beg, end, beg2, other args); //假定从beg2开始的范围与[beg end)表示的范围至少一样大
    alg(beg, end, beg2, end2, other args);

### if版本的算法 ###

接受谓词算法的参数附加`_if`后缀。

find(beg, end, val); //查找输入范围中val第一次出现的位置
    find_if(beg, end, pred); //查找第一个令pred为真的元素

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

写到额外目的空间的算法在名字后面附加一个`_copy`。

reverse(beg, end); //反转输入范围中元素的顺序
    reverse_copy(beg, end, dest); //将元素按逆序拷贝到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;});

# 特定容器算法 #

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][20200516104254110.png]  
`splice`算法是链表数据结构所特有的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 6]  
多数链表特有的版本与通用版本间一个至关重要的区别是**链表版本会改变底层的容器**。

# 练习 #

1.  **头文件`algorithm`中定义了一个名为`count`的函数，类似于`find`，接受一对迭代器参数和一个值作为参数。`count`返回给定值在序列中出现的次数。编写程序，读取`int`序列存入`vector`中，打印有多少个元素的值等于给定值。**

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        
    	vector<int> vi;
    	int num;
    
    	while(cin>>num){
        
    		vi.push_back(num);
    	}
    
    	int value = 3;
    	cout<< value <<" appears "<< count(vi.begin(), vi.end(), value) << " times" << endl;
    	
    	system("pause");
    	return 0;
    }

![在这里插入图片描述][20200517100352823.png]

1.  **用`accumulate`求一个`vector<int>`中的元素之和**

#include <iostream>
    #include <vector>
    #include<numeric>
    
    using namespace std;
    
    
    int main()
    {
        
    	vector<int> vi{
        1, 2, 3, 4, 5};
    
    	cout <<" The sum is "<< accumulate(vi.begin(), vi.end(), 0) << endl;
    	
    	system("pause");
    	return 0;
    }

![在这里插入图片描述][20200517103033424.png]

1.  **假定`v`是一个`vector<double>`，那么调用`accumulate(v.cbegin(), v.cend(), 0)`有何错误？**

因为`accumulate`的第三个参数指定了求和的初值，若将初值设定为0，表明返回值为`int`类型，那么在实际求和时会将`double`转换为`int`，会引起精度损失。

1.  **编写程序,使用`fill_n`将一个序列中的`int`值都设置为0**

#include <iostream>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    
    int main()
    {
        
    	vector<int> vi{
        1, 2, 3, 4, 5};
    
    	cout << "Before change: " << endl;
    	for(auto a : vi){
        
    		cout << a << " ";
    	}
    	cout << endl;
    
    	fill_n(vi.begin(), vi.size(), 0);
    
    	cout << "After change: " << endl;
    	for(auto a : vi){
        
    		cout << a << " ";
    	}
    	cout << endl;
    
    	system("pause");
    	return 0;
    }

![在这里插入图片描述][20200517103800966.png]

1.  **下面的程序是否有错误？如果有，请改正**  
    **(a)**

vector<int> vec;
    list<int> lst;
    int i;
    
    while(cin >> i)
    	lst.push_back(i);
    
    copy(lst.cbegin(), lst.cend(), vec.begin());

错误，这里使用`copy`需要保证`vec`的大小不能小于`lst`，因此需要在`copy`前添加`vec.resize(lst.size)`。

vector<int> vec;
    	list<int> lst;
    	int i;
    
    	while(cin >> i)
    		lst.push_back(i);
    	
    	vec.resize(lst.size());
    	copy(lst.cbegin(), lst.cend(), vec.begin());

**(b)**

vector<int> vec;
    vec.reserve(10);
    fill_n(vec.begin(), 10, 0);

错误，这里不应该用`reserve`，而是应该使用`resize`，因为`reserve`只是分配空间，实际元素个数还是0个。

vector<int> vec;
    vec.resize(10);
    fill_n(vec.begin(), 10, 0);

1.  **实现你自己的`elimDups`，测试在读取输入后、调用`unique`后，调用`erase`后`vector`中的内容分别是什么？**

#include<iostream>
    #include<string>
    #include<vector>
    #include<algorithm>
    
    using namespace std;
     
    void elimDups(vector<string> &s)
    {
        
    	cout<<"Before sort:";
    	for (int i = 0; i<s.size(); ++i)
    	{
        
    		cout<<s[i]<<" ";
    	}
    	cout<<endl<<"After sort():";
    	sort(s.begin(),s.end());//sort排序
    	for (int i = 0; i<s.size(); ++i)
    	{
        
    		cout<<s[i]<<" ";
    	}
    
    	cout<<endl<<"After unique():";
    	vector<string>::iterator ite = unique(s.begin(),s.end());//unique排序
    	for (int i = 0; i<s.size(); ++i)
    	{
        
    		cout<<s[i]<<" ";
    	}
    
    	cout<<endl<<"After erase():";
    	s.erase(ite,s.end());//erase()操作
    	for (int i = 0; i<s.size(); ++i)
    	{
        
    		cout<<s[i]<<" ";
    	}
     
    }
    int main(int argc, char**argv)
    {
        
    	string a[10] = {
        "because","I","Like","Like","C++","very","very","much","that's","why"};
    	vector<string> s(a,a+10);
    	elimDups(s);
     
    	system("pause");
    	return 0;
    }

![在这里插入图片描述][20200517113502396.png]

1.  **编写程序，使用`stable_sort`和`isShorter`将传递给你的`elimDups`版本的`vector`排序。打印`vector`的内容，验证你的程序的正确性。**

#include<iostream>
    #include<string>
    #include<vector>
    #include<algorithm>
    
    using namespace std;
     
    void elimDups(vector<string> &s)
    {
        
    	cout<<"Before sort:";
    	for (int i = 0; i<s.size(); ++i)
    	{
        
    		cout<<s[i]<<" ";
    	}
    	cout<<endl<<"After sort():";
    	sort(s.begin(),s.end());//sort排序
    	for (int i = 0; i<s.size(); ++i)
    	{
        
    		cout<<s[i]<<" ";
    	}
    
    	cout<<endl<<"After unique():";
    	vector<string>::iterator ite = unique(s.begin(),s.end());//unique排序
    	for (int i = 0; i<s.size(); ++i)
    	{
        
    		cout<<s[i]<<" ";
    	}
    
    	cout<<endl<<"After erase():";
    	s.erase(ite,s.end());//erase()操作
    	for (int i = 0; i<s.size(); ++i)
    	{
        
    		cout<<s[i]<<" ";
    	}
     
    }
    
    bool isShorter(const string &s1, const string &s2)
    {
        
    	return s1.size() < s2.size();
    }
    
    int main(int argc, char**argv)
    {
        
    	string a[10] = {
        "because","I","Like","Like","C++","very","very","much","that's","why"};
    	vector<string> s(a,a+10);
    	elimDups(s);
    	cout << endl;
    
    	stable_sort(s.begin(), s.end(), isShorter);//stable_sort保持等值元素间的相对顺序。
    	cout << "After stable_sort():";
    	for(auto a:s){
        
    		cout << a << " ";
    	}
    	cout << endl;
     
    	system("pause");
    	return 0;
    }

![在这里插入图片描述][20200517115255216.png]

1.  **标准库定义了一个名为`count_if`的算法，接受一对表示输入范围的迭代器，还接受一个谓词，会对输入范围中每个元素执行。`count_if`返回一个计数值，表示谓词有多少次为真。使用`count_if`统计有多少个单词长度超过6.**

#include<iostream>
    #include<string>
    #include<vector>
    #include<algorithm>
    
    using namespace std;
     
    
    int main(int argc, char**argv)
    {
        
    	
    	vector<string> vec1{
        "sfsaferqwr","aaa","bbbbbbbbbbb","s","ddd","w"};
    	cout << count_if(vec1.begin(), vec1.end(), [](const string&s){
        return s.size() > 6;}) << endl;
     
     	system("pause");
    	return 0;
    }

![在这里插入图片描述][20200517122414510.png]

1.  **分别使用`inserter`、`back_inserter`和`front_inserter`向容器添加元素，看输出序列有何不同**

#include<iostream>  
    #include<list>  
    #include<algorithm>  
    #include<iterator>
    
    using namespace std;
    
     
    int main(int argc, char**argv)  
    {
          
    	list<int> lst1{
        1,2,3,4,5,6,7,8,9};
    	list<int> lst2;
    	list<int> lst3;
    	list<int> lst4;
     
    	//实现包含头文件iterator
    	copy(lst1.cbegin(),lst1.cend(),back_inserter(lst2));
    	copy(lst1.cbegin(),lst1.cend(),front_inserter(lst3));
    	copy(lst1.cbegin(),lst1.cend(),inserter(lst4,lst4.begin()));
     
    	cout<<"lst2:";
    	for(auto item: lst2){
        
    		cout << item << " ";
    	}
    	cout << endl;
    
    	cout<<endl<<"lst3:";
    	for(auto item: lst3){
        
    		cout << item << " ";
    	}
    	cout << endl;
    
    	cout<<endl<<"lst4:";
    	for(auto item: lst4){
        
    		cout << item << " ";
    	}
    	cout << endl;
    
    	system("pause");
    	return 0;  
    }

![在这里插入图片描述][20200517123840234.png]  
对于`inserter`和`back_inserter`是按原顺序插入，而对于`front_inserter`因为每个元素插入到容器中时，会变成新的首元素，因为插入的元素序列顺序会颠倒过来。

1.  \*\*使用流迭代器、`sort`和`copy`从标准输入读取一个整数序列，将其排序后输出，并使用`unique_sort`保证不输出重复元素。

#include<iostream>  
    #include<fstream>
    #include<vector>  
    #include<algorithm>  
    #include<iterator>
    using namespace std;
     
    int main(int argc, char**argv)  
    {
          
    	vector<int> vec1;
    	//创建流迭代器、尾后迭代器
    	istream_iterator<int> str(cin), end;
     
    // 	while (str != end)
    // 	{
        
    // 		vec1.push_back(*str++);
    // 		
    // 	}//此操作和copy一样的效果，只不过要记得++.
    	unique_copy(str,end,back_inserter(vec1));//存入vec1,unique_copy只会留下不重复元素
     
    	sort(vec1.begin(),vec1.end());
     
    	for (auto item: vec1)
    	{
        
    		cout<<item<<endl;
    	}
     
    	system("pause");
    	return 0;  
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 7]

1.  **编写程序，使用`istream_iterator`读取一个保存着许多整数的输入文件，使用`ostream_iterator`将奇数写入第一个输出文件，每个值后面都跟一个空格；将偶数写入第二个输出文件，每个值都独占一行。**

#include<iostream>  
    #include<fstream>
    #include<vector>  
    #include<algorithm>  
    #include<iterator>
    
    using namespace std;
    
    int main(int argc, char**argv)  
    {
          
    	ifstream in("input.txt");
    	istream_iterator<int> iter1(in), end;
    
    	vector<int> vi;
    	while(iter1 != end){
        
    		vi.push_back(*iter1);
    		++iter1;
    	}
    
    	ofstream out1("even.txt");
    	ofstream out2("odd.txt");
    
    	ostream_iterator<int> iter2(out1, " ");//奇数以空格分割
    	ostream_iterator<int> iter3(out2, "\n");//奇数以换行分割
    
    	for(auto item: vi){
        
    		if(item % 2 != 0)//奇数
    		{
        
    			iter2++ = item;
    		}else{
        
    			iter3++ = item;
    		}
    	}
     
    	system("pause");
    	return 0;  
    }

1.  **使用`find`在一个`int`的`list`中查找最后一个值为0的元素**

#include<iostream>  
    #include<list>  
    #include<algorithm>  
    #include<iterator>
    
    using namespace std;
    
     
    int main(int argc, char**argv)  
    {
          
    	list<int> li{
        1,2,0,3,4,0,5,6};
    
    	auto pos = find(li.crbegin(), li.crend(), 0);
    
    	system("pause");
    	return 0;  
    }

1.  **列出几种常用容器的迭代器属于哪类**

*  `vector`: random access iterator
 *  `list`: bidirectional iterator
 *  `deque`: random access iterator

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

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);

(1)：遍历`beg`到`end`，找到`oldVal`就用`newVal`替换

(2)：遍历`beg`到`end`，找到满足`pred`条件的就用`newVal`替换

(3)：遍历`beg`到`end`，找到`oldVal`就用`newVal`替换，并将其拷贝至`dest`

(4)：遍历`beg`到`end`，找到满足`pred`条件的就用`newVal`替换，并将其拷贝至`dest`

[20200514170032162.png]: /images/20230312/f2407fe5084f46aa99a074244a206193.png
[20200514170053894.png]: /images/20230312/bba2041db5774a09b22a2ab607154cf2.png
[20200514170131440.png]: /images/20230312/6a218e9eba624490971c26ed1b49521c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70]: /images/20230312/edf5408e6eed46f19afc28f8a63d9048.png
[20200515171302587.png]: /images/20230312/b2bc3c105e5f4184aa2869cbf03ba5fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 1]: /images/20230312/cbc55fefba374751a124defbf982b08a.png
[20200515180411769.png]: /images/20230312/23b3a66c8407480abf1a2320a34718f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 2]: /images/20230312/661ebf7b5cc04aa798c4f924d2f854b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200516093900500.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200516094428295.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200516104241805.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx,size_16,color_FFFFFF,t_70
[20200516104254110.png]: https://img-blog.csdnimg.cn/20200516104254110.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200516104451213.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx,size_16,color_FFFFFF,t_70
[20200517100352823.png]: https://img-blog.csdnimg.cn/20200517100352823.png
[20200517103033424.png]: https://img-blog.csdnimg.cn/20200517103033424.png
[20200517103800966.png]: https://img-blog.csdnimg.cn/20200517103800966.png
[20200517113502396.png]: https://img-blog.csdnimg.cn/20200517113502396.png
[20200517115255216.png]: https://img-blog.csdnimg.cn/20200517115255216.png
[20200517122414510.png]: https://img-blog.csdnimg.cn/20200517122414510.png
[20200517123840234.png]: https://img-blog.csdnimg.cn/20200517123840234.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200517130116997.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1ODAwMzEx,size_16,color_FFFFFF,t_70