《C++ Primer》读书笔记—第十章泛型算法

---恢复内容开始---

声明：

文中内容收集整理自《C++ Primer 中文版（第5版）》，版权归原书所有。
学习一门程序设计语言最好的方法就是练习编程

一、概述

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

2、假定有一个int类型的vector，希望知道vector中是否包含一个特定的值，用find：

1 int val = 42;
2 auto result = find(vec.cbegin(),vec.cend(),val);
3 cout<< "The value " << (result == vec.cend() ? " is not present":" is present")<<endl;

　　find返回指向第一个等于给定值的元素的迭代器。

3、和find函数一样，其他的泛型算法也不直接操作容器，而是遍历由两个迭代器指定的范围内的元素，由迭代器完成元素操作。

4、find作用于string:

1 string val = "a value";  
2 list<string> lst = {"a value", "xxx", "yyy" };  
3 auto result = find(lst.cbegin(), lst.ceng(), val);

　　find作用于数组：

1 int ia[] = {32, 3};  
2 int val = 83;  
3 int *result = find(begin(ia), end(ia), val);

5、count函数接受一对迭代器和一个值作为参数，count返回给定值在序列中出现的次数。

6、算法永远不会改变底层容器的大小。

7、泛型算法

　　·独立于特定的容器

　　·和迭代器的联系非常紧密

　　·并不直接操作容器

二、初始泛型算法

1、只读算法

find
accumulate
equal

　　写算法

fill
fill_n
copy
replace
replace_copy
sort
unique

2、accumulate

　　定义在numeric头文件中，用于求和

1 int sum = accumulate(vec.begin(), vec.end(), 0);

　　算法的前两个参数用于表示一个迭代器范围，第3个参数表示求和的初始值。

　　返回值是迭代器范围内元素的和（以第三个参数为初始值）。

　　第三个参数的类型特别重要，因为算法并不知道元素的类型，所以它会根据第3个参数的类型来推断使用哪种加法。

　　比如下面的调用就是错误的

1 string sum = accumulate(v.cbegin(), v.cend(), "");

　　表面上看第三个参数是一个string，但实际会被看作是一个字符数组，所以第3个参数的类型是const char*，由于const char*没有加法运算，所以调用是错误的。

　　正确的写法是：

1 string sum = accumulate(v.cbegin(), v.ceng(), string(""));

3、equal

　　作用于两个序列，它将第一个序列中的元素与第二个序列中的对应元素进行比较。

1 bool bIsEqual = equal(v1.cbegin(), v1.cend(), v2.cbegin());

　　它只接受三个参数，并没有指定第二个容器的结尾位置，这就要求第二个容器至少和第一个容器一样长，否则算法会发生错误。

　　这里并不要求两个容器的元素类型相同，只要能使用比较运算符==就可以了。

　　比如vector<string>和list<const char*>

　　操作两个序列的算法还有另外一种形式，就是传递四个参数，分别代码两个迭代器范围。

4、fill 和 fill_n

　　将给定的值赋予输入范围内的元素：

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

　　fill_n只接受一个迭代器：

1 fill_n(iter, n, val);//将从iter开始的n个元素赋值为val

　　要知道泛型算法并不操作容器。

1 vector<int> vec;  
2 fill_n(vec.begin(), 10, 0);//这个调用是错误的，fill_n并不是向容器中插入元素，它只负责更新元素的值。

　　想要在空容器上使用fill_n也是有方法的，需要借助插入迭代器 : back_inserter

vector<int> vec;  
auto it = back_inserter(vec);  
*it = 42;

　　back_inserter的参数是容器的引用，返回值是一个特殊的迭代器。

1 vector<int> vec;  
2 fill_n(back_inserter(vec), 10, 0);

　　这个调用是合法的，因为back_inserter返回的一个特殊的迭代器，它会执行push_back操作。

5、copy：向目的位置迭代器指向的输出序列中的元素写入数据的算法。

　　类似于equal，copy也接受三个迭代器，长度同样需要由程序员来保证。

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

6、replace：后两个一个是要搜索的值，另一个是新值。它将所有等于第一个值的元素替换为第二个值。将指定范围内的所有0替换为42。

1 replace(v.begin(), v.end(), 0, 42);

保留原序列不变，此算法额外接受第三个迭代器参数，指出调整后序列的保存位置。

1 replace_copy(ilst.cbegin(),ilist.cend(), back_inserter(ivec),0,42);

7、sort：

将指定范围内的元素重排，它是利用元素类型的<运算符来实现排序的

1 sort(v.begin(), v.end());

8、unique：

　　很容易把unique理解为“去重”，这是不正确的。unique实际也只是执行重排的操作，并不包含“去”的过程（即不会删除元素，算法不会改变容器大小）

1 auto itr1 = unique(v.begin(), v.end());

　　unique会重排元素，容器中和其他元素重复的元素会被排到后面。

　　itr1是一个迭代器，itr1之前的元素都是不重复的，因为unique把和其他元素重复的那些内容挪到了itr1之后

　　我们可以用erase操作来删除这些元素，这个才是真正意义上的“去重”

1 v.erase(itr1, v.end());

9、删除一个空范围没有影响。

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

三、定制操作***这一节看的不是很懂，很抽象。之前没接触过lambda什么的。

1、

函数适用的情况下向算法传递函数
参数个数不匹配时，可以使用lambda表达式
如果很多地方要用到同一个lambda表达式，可以通过bind解决

2、排序函数，用来按长度重新排序单词

1 bool isShorter(const string &s1, const string &s2)  
2 
3 {  
4 
5     return s1.size() < s2,size();  
6 
7 }  
8 
9 sort(v.begin(), v.end(), isShorter);

3、谓词是一个可调用的表达式，其返回结果是一个能用作条件的值。

接受谓词参数的算法对输入序列中的元素调用谓词。因此，元素类型必须能转换为谓词的参数类型。

谓词分为两类：

一元谓词（只接受一个参数）
二元谓词

4、lambda表达式：

　　它是一个可调用对象

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

　　可以省略参数列表和返回类型：

auto f = []{ return 42; };  

cout << f() << endl;

　　理解时，可以把lambda表达式理解为未命名的内联函数。

　　lambda表达式可以捕获和它属于同一个局部作用域的变量。

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

　　这样它就成了一个一元谓词，可以被find_if调用。

string::size_type sz = 10;  

find_if(v.begin(), v.end(), [sz](const string &a){ return a.size() >= sz; } );

　　lambda可以直接使用定义在当前函数之外的名字。

1 for_each(v.begin(), v.end(), [](const string &s){ cout << s << " "; });

　　cout就是定义在函数体之外的名字。

5、lambda捕获和返回：

值捕获

与参数的值传递类似
区别在于：拷贝过程发生在lambda创建时，而不是调用时。

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

引用捕获

与参数的引用传递类似
同样要保证lambda调用时捕获的引用指向的局部变量还在

尽量减少捕获的数据，来避免潜在的问题。如果可能的话，避免捕获指针或引用。

1 void fcn2(){
2     size_t v1 = 42;//局部变量
3     auto f = [&v1]{return v1;};//对象v2包含v1的引用
4     v1 = 0;
5     auto j = f(); j=0，f2保存了v1的引用而非拷贝    
6  }

隐式捕获

不指明捕获哪个局部变量，而是让编译器自己去推断。

为了指示编译器需要推断捕获列表，需要在捕获列表中写一个&或=

1 find_if(v.begin(), v.end(), [=](const string &s){ return s.size() >= sz; });

隐式捕获sz，且是一种值捕获。

混合捕获

如果混合使用显式捕获和隐式捕获

必须把隐式捕获放在前面
显式和隐式必须采用不同的捕获方式。

返回类型：

如果lambda体中包含除return语句之外的任何语句，则编译器假定此lambda返回void

1 [](int i){ if(i<0) return -i; else return i;};

该lambda包括return之外的语句(if)，又没有指明返回类型，因此编译器推断它返回void，但实际函数体中返回的却是int，因此报错

此时应当指明返回类型。

1 [](int i) -> int { if(i<0) return -i; else return i;};

lambda使用尾置返回类型。

6、参数绑定bind 跳过了。==、

四、再探迭代器

1、除了在每个容器中定义迭代器以外，标准库在头文件iterator中定义了额外的几种迭代器。包括：

插入迭代器：向容器中插入元素。

流迭代器：绑定到输入或输出流，用来遍历所关联的IO流。

反向迭代器：向后而不是向前移动。除了forward_list之外的标准库容器都有反向迭代器。

移动迭代器：不是拷贝其中的元素，而是移动它们。

2、插入迭代器有三种

back_inserter
front_inserter 元素总是插入到容器第一个元素之前
inserter 将元素插入到iter原来所指向的元素之前的位置

根据插入迭代器的不同，分别调用push_back、push_front、insert

*it,++it,it++ 也是合法的操作，但不会对it做任何事情

1 copy(lst.begin(), lst.end(), front_inserter(lst1));

实际的执行过程是

front_inserter返回一个插入迭代器(it)
copy算法遍历给定范围内的元素，执行it=t操作
根据插入迭代器的特性，实际执行lst1.push_front(t)

3、iostream迭代器

　　当创建一个流迭代器时，必须制定迭代器将要读写的对象类型。

　　注意：back_inserter等是插入器，它们的返回值是迭代器。

　　而istream_iterator和ostream_iterator本身就是迭代器，它们是模板类。

1 istream_iterator<int> int_it(cin);
2 istream_iterator<int> int_eof;

　　它的入参是一个流，和其他迭代器类似，iostream迭代器会把传入的流当作一个特定类型元素的序列来处理。

　　默认构造函数返回尾后迭代器，如int_eof。

　　可以发现，第一句得到了开始迭代器，第二句得到了尾后迭代器，而且这类迭代器同时也支持递增操作，所以我们可以像使用其他迭代器一样来使用iostream迭代器：

1 istream_iterator<int> in_iter(cin), eof;
2 vector<int> vec(in_iter, eof);

　　可以很方便的把cin中的内容存到一个vector中。

1 istream_iterator<int> in_iter(cin);
2 istream_iterator<int> eof;
3 while(in_iter != eof){
4     vec.push_back(*in_iter++);
5 }

　　类似的，也可以用前面的算法库来处理

1 accumulate(in_iter, eof, 0);

　　istream_iterator允许使用懒惰求值：并不保证在创建迭代器时立刻从流中读取值，保证在第一次解引用迭代器之前，从流中读取数据的操作已经完成。

　　ostream_iterator

　　和istream_iterator不同，构造时必须绑定到一个指定的流

1 ostream_iterator<T> out(os);
2 ostream_iterator<T> out(os, d);

　　d是字符串常量或指向以空字符结尾的字符数组的指针，比如空格" "

　　如果指定了d，则会在每个输出值后面都输出一个d

ostream_iterator<int> out_iter(cout, " ");
for(auto e : vec)
{
   *out_iter++ = e;
}
cout << endl;

　　实际上解引用和递增运算并不对ostream_iterator迭代器进行任何操作，这里加上有两个好处：

1. 如果想将此循环改为操作其他迭代器类型，修改起来会很容易。
2. 方便读者理解此循环的意图。

　　也可以使用算法

1 copy(v.begin(), v.end(), out_iter);
2 cout << endl;

　　对于支持输入运算符或输出运算符的类，同样也可以使用流迭代器。

　　反向迭代器

　　从尾元素向首元素反向移动的迭代器：

　　递增一个反向迭代器会移动到前一个元素；
　　递减一个反向迭代器会移动到下一个元素。

1 sort(v.begin(), v.end());
2 sort(v.rbegin(), v.rend());

　　逆序打印vector中的元素：

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

　　sort需要迭代器支持递增操作，第一个sort会按照正常序进行排序，而第二个sort的排序结果刚好是第一个的逆序。

　　对于一个以逗号分隔的字符串，如果我们想要打印最后一个单词，可以使用反向迭代器找到该单词的位置。

1 auto rcomma = find(line.crbegin(), line.crend(), ',');

　　但是当我们试图使用返回的迭代器rcomma来打印最后一个单词时，问题就来了

1 cout << string(line.crbegin(), rcomma) << endl;

　　这样打印出来的单词会是反的，比如想要加印的是LAST，实际则是TSAL。

　　正确的做法是将rcomma转换成一个普通的迭代器。base成员函数可以辅助我们完成这一操作：

1 cout << string(rcomma.base(), line.cend()) << endl;

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

五、泛型算法结构

1、除了输出迭代器之外，一个高层类别的迭代器支持低层类别迭代器的所有操作。

2、输出迭代器只能用于单遍扫描算法。用作目的位置的迭代器通常都是输出迭代器。

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

4、向输出迭代器写入数据的算法都是假定目标空间足够容纳写入的数据。

5、

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

6、默认状态下，重排元素的算法将重排后的元素写回给定的输入序列中，这些算法还提供另外一个版本，将元素写到一个指定的输出目的位置。

　　常见的写入额外目的空间的算法都在名字后面加上_copy

1 reverse(beg,end);//反转输入范围中元素的顺序
2 
3 reverse_copy(beg,end,dest);//将元素按逆序拷贝到dest

7、一些算法同时提供_copy和_if版本，这些版本接收一个目的为止迭代器和一个谓词：

1 remove_if(v1.begin(),v1.end(),[](int i){return i%2;});//从v1中删除奇数元素
2 remove_copy_if(v1.begin(),v1.end(),back_inserter(v2),[](int i){return i%2;});//将偶数元素拷贝到v2,v1不变

六、特定容器算法

1、一个链表可以通过改变元素间的链接而不是真的交换它们的值来快速“交换”元素。

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

1 lst.merge(lst2)  //lst2合并入lst，两者必须为有序
2 lst.merge(lst2, comp)  //合并之后lst2为空
3 lst.remove(val)  //调用erase删除与定值等的每个元素
4 lst.remove_if(pred)  
5 lst.reverse()  反转lst中的元素顺序
6 lst.sort()  //排序
7 lst.sort(comp)  
8 lst.unique()  //使用erase删除同一个值的连续拷贝
9 lst.unique(pred)

3、链表还定义了splice成员函数，可以将lst2指定范围内的元素移动到lst指定位置之前或之后。

1 lst.splice(args)  
2 lst.splice_after(args)

4、链接的操作和通用算法的最大区别是，链表操作会改变容器。

　　如unique，通用版本并不做删除重复元素的操作，但是链接会做。

　　3.15上午，重装了系统。笔记本爆炸了要。啥都不能做，只好重装。下午，改好了fu的文章，查重12%，算是过了。应该不会再大改动了，只有小改动。华为开发者挑战赛的人开了波会，初步谈了一下需求和分工安排，感觉Android这一块都要我做了。重拾旧货，不知道能不能胜任。感觉事儿好多，突然压到身上了。做一点是一点吧，但愿能做出来，不求获奖，只求学点东西，长长经验。绿卡什么的，无所谓，我两年前能进，两年后也能进。不要忘记自己的初衷，且随疾风前行。

　　3.16晚上，小超哥10点回去就开始打电话，两个人开始飙歌了，打到睡觉才结束，第二天早上7点多又开始了。真是小年轻坠入爱河。

　　3.17早：第十章结束。且随疾风前行。