一、模板编程
1.模板编程的必要性
在c++中，变量的声明必须指出它的类型，提高了编译运行效率，但是在某些场合下就有点缺陷。比如：需要定义计算两个数之和的函数，由于未来计算的数值有可能是整数、也有可能是浮点数，所以需要为这些类型准备对应的函数，但是这些函数的内部逻辑都是一样的，他们的唯一区别就是所接收的数据类型不同而已。那么有没有一种情况使得编码的时候暂时的忽略掉类型这个特性，等运行时在动态决定。
int add(inta ,int b){
return a + b;
}
float add(float x , float y ){
return x + y;
}
2. 函数模板
函数模板是通用函数的描述，使用泛型来定义函数，让编译器暂时忽略掉类型，使用参数把类型传递给模板，进而让编译器生成对应类型的函数。函数模板仅仅是表示一种模型罢了，并不是真正可以直接调用的函数，需要在使用的时候传递对应类型，生成对应类型的函数。
模板的定义以
template关键字开始，后面跟随着参数列表，使用<>包含
template<typename T>
T add(const T& t1 ,const T& t2){
return t1 + t2;
}
int result = add<int>( 3, 5);
cout <<"result = " << result << endl;
int result = add( 3, 5);
cout <<"result = " << result << endl;
- 函数模板重载
如普通函数一般，函数模板也可以重载，以便灵活应对更多的需求
template<typename T>
T add(const T& t1 ,const T& t2){
return t1 + t2;
}
template<typename T>
T add(const T& t1 , const T& t2 , const T& t3){
return t1 + t2 + t3;
}
int result1 = add( 1, 2 );
int result2 = add( 1, 2 ,3);
cout <<"result1 = " << result1 << endl;
cout <<"result2 = " << result2 << endl;
- 模板可变参数
如果一个函数接收的参数个数不确定，并且都是同一种类型的参数，那么可以使用可变参数的写法来简化代码。 可变参数使用 ... 来表示，通常可变参数也称之为 **参数包 ** ，用于表示它可以对多个参数打包成一个整体。
3. 可变参数
在C++ 中一般函数的参数个数都是固定的，但是也有一种特殊的函数，他们的参数个数是可变的。针对这种情况C++中提供了initializer_list和省略号两种方法，其中initializer_list要求可变参数的类型必须都一致，而省略号方式则不具备这种限制，要更加灵活。
- 省略号方式
要处理省略号方式的可变参数，使用四个宏的宏
va_start、va_arg、va_end、va_list需要导入#include <stdarg.h>， 而且这种方式没有办法计算出来可变参数的个数，需要在前面指定，并且可变参数的个数和实际传递的参数个数必须一致，否则可能结果有偏差。省略号的方式，不限定参数个数，也不限定参数类型，可以是不同的数据类型。
//num表示有几个参数, ... 表示右面具体的参数
// 调用：add (3, "aa","bb","cc");
int add(int count, ...) {
//count 表示可变参数个数
va_list vl;//声明一个va_list变量
va_start(vl, count);//初始化，第二个参数为最后一个确定的形参
int sum = 0;
for (int i = 0; i < count; i++)
sum += va_arg(vl, int); //读取可变参数，的二个参数为可变参数的类型
va_end(vl); //清理工作
return sum;
}
- initializer_list 方式
c++ 11引入的一种方式，需要导入
#include <initializer_list>， 参数必须放在一组{}里面，并且元素的类型必须是一样的。
int add(initializer_list<int> il) {
int sum = 0;
for (auto ptr = il.begin(); ptr != il.end(); ptr++){
sum += *ptr;
}
return sum;
}
int main(){
add({10,20,30}); //传递的参数必须放置在一个 {} 里面
return 0 ;
}
4. 可变参数模板
函数模板解决了相同功能、不同数据类型造成多个方法重载的局面，而当模板的参数类型都是一样的，或者有多个一样的参数类型一样，那么使用可变参数来改进模板函数，就显得更为美观。对于参数包来说，除了获取大小之后，程序员更想关注的是，如何获取里面的数据，解构里面的元素，也有个名字：
扩展。
1. 定义可变参数函数模板
//定义一个add函数，表示接受一种类型的可变参数。
// 上面的Args ： 模板参数包，表示可以穿很多种类型的参数这里是用于描述类型
// 下面的args1 : 函数参数包 在调用函数的时候，表示可以传很多数据进来，与上面的类型匹配。
template <typename ...Args>
int add(Args...args1){
int a = sizeof...(args1);
cout <<"传递进来的参数有："<< a << endl;
}
//Args是： int ,int ,int,string ,string ,string
// args1 : 2, 3, 4, a, b, c
add(2,3,4,"a","b","c");
2. 展开参数包
可变参数从设计角度是方便了，但是在获取传递过来的参数却有点棘手，因为索引下标在展开参数包场景下没有用，而且可变参数可以看成是一个包裹，里面包装了传递过来的若干个实参。通常展开参数包的做法是采用递归，不断的调用，每调用一次，减少一个实参，最终把所有实参都捕获出来。
- 递归调用
这是一个有缺陷的代码，因为它陷入了无限递归当中。虽然是错误的代码，但是却为解开参数包提供了一个思路。核心理念就是解开参数包，对第一项处理，再将余下的内容向下传递。这样在每一层的调用中，都能够拿到全新的第一个数字。
int add(Args...args){
add(args...) //args1...表示参数包，就是传递过来的所有参数的包裹。
}
- 递归调用
//这里定义一个空的函数，目的是为最后的递归终止。
int add(){return 0 ;}
template <typename T, typename ...Args>
int add(T t , Args...args){
//int sum = 0;
cout <<"打印的数字时：" << t << endl;
//开始这里循环调用自己，知道最后那个没有参数的，才会调用外面的add()
t += add(args...);
return t;
}
int main(){
cout << add(1,2,3,4,5) << endl;
}
5. 类模板编程
有时候继承、包含并不能满足重用代码的需要，这一般在容器类里面体现的尤为突出。例如： 我们定义了一个容器类，Container， 这个Container类可以实现类似verctor一样的工作，能保存数据，能修改数据，并且数据的类型不限制，但是针对数据的操作都是一样的。那么类模板编程就成了不二之选了。
1. 定义模板类
这里以栈作为参照对象，定义一个模板类，实现栈一样的功能。
- 原始代码
class Stack{
private :
enum{MAX = 10}; //表示这个Stack容器最多只能装10个。
int top =0 ; //表示最顶上的索引位置
string items[MAX]; //定义一个数组，以便一会装10个元素
public:
bool isempty(){
return top == 0;
}
bool isfull(){
return top == MAX;
}
//压栈
int push(string val){
if(isfull()){
return -1;
}
//没有满就可以往里面存
items[top++] = val;
}
//出栈
string pop(){
if (isempty()){
return "";
}
//如果不是空 top 只是指向位置，而数组获取数据，索引从0开始，所以先--
return items[--top] ;
}
string operator[](int index){
if(isempty() || index > --top){
cout <<"容器为空或者超出越界" << endl;
return "";
}
return items[index];
};
};
- 类模板
上面的Stack容器仅仅只能针对string这种数据类型，如果想存自定义的类型或者其他类型，那么Stack就无法满足了。 要定义类模板，需要在类的前面使用
template <typename T>, 然后替换里面的所有string 即可，这样Stack就能为所有的类型工作了。 如果是自定义类型，那么需要自定义类型提供无参构造函数，因为数组的定义会执行对象的构造。若想避免构造的工作发生，可以使用allocator来操作。
template <typename T> class Stack{
private :
enum{MAX = 10}; //表示这个Stack容器最多只能装10个。
int top =0 ; //表示最顶上的索引位置
T items[MAX]; //定义一个数组，以便一会装10个元素
public:
bool isempty(){
return top == 0;
}
bool isfull(){
return top == MAX;
}
//压栈
int push(const T& val){
if(isfull()){
return -1;
}
//没有满就可以往里面存
items[top++] = val;
}
//出栈
T pop(){
if (isempty()){
return "";
}
//如果不是空 top 只是指向位置，而数组获取数据，索引从0开始，所以先--
return items[--top] ;
}
T operator[](int index){
if(isempty() || index > --top){
cout <<"容器为空或者超出越界" << endl;
return "";
}
return items[index];
};
};
- 函数的模板
- 可变参数
- 可变参数的函数模板
6. 练习
模拟vector实现自定义容器
- 底层数组实现
- 数组开辟空间，使用allocator ，否则会一块执行对象构造工作
- 能装任意类型（int， string , stu）
- 构造参数可以接收 可变参数 (init_list)
- 提供push_back函数 接收可变参数，添加元素到容器末端
- 提供pop函数，返回容器的最前端元素
- 提供[]操作符，根据下标可以获取元素
- 提供size函数
- 提供*操作符 ，以便修改指定元素。如： (如果要存储自定义类，可以重载这个函数)
Stu stu = myvector[0];
*stu.name ="张三";
二、容器
在C++ 里面，针对容器的划分有： 顺序容器 和 关联容器
1. 顺序容器
所谓的顺序容器指的是，在容器的内部，元素的摆放是有顺序的。通常
vector已经足以满足大部分开发了。
| 容器 | 描述 |
|---|---|
| string | 与vector相似，尾部插入|删除速度快 |
| array | 固定大小数组，支持快速随机访问，不能添加和删除 |
| vector | 可变大小数组，支持快速随机访问，在尾部之外的位置插入和删除 速度慢 |
| deque | 双端队列，支持快速随机访问，两段插入和删除速度快 |
| forward_list | 单向链表、只支持单向顺序访问，插入和删除快，查询慢 |
| list | 与单向链表不同，它是双向链表，其他一样。 |
2. 迭代器
早前访问数组、vector、字符串时，都可以使用索引下标的方式访问，实际上还有一种更为通用的机制 ： 迭代器 。所有标准库中的容器都可以使用迭代器，但是只有少数几个支持下标索引的方式。与指针相似，迭代器也能对对象进行间接访问，但是不能简单认为，指针就是对象，也不能直接认为迭代器就是对象。只是可以通过迭代获取到对象。
stu s;
s.name s.age s.run();
stu * p = &s;
p->name
- 使用迭代器
迭代器通常都是靠容器的
begin()和end()函数获取。 其中begin 返回的是指向第一个元素的迭代器， 而end函数返回的值指向最后一个元素的下一个位置，也就是指向容器里面不存在的尾后元素。所以一般end（）返回的迭代器仅是一个标记而已，并不用来获取数。
[图片上传失败...(image-2c19b8-1563956966972)]
- 迭代器运算
由于begin() 的返回值只会指向第一个元素，若想获取到后面的元素，可以对迭代器进行运算，它的用法和指针的运算是一样的。通过 + - 的操作，来让返回前后元素对应的迭代器。 在迭代器的内部，提供两种获取迭代器对应的数据，一是
base()返回的是 指向数据的指针， 二是使用*操作符函数，在迭代器里面重载了*运算符函数。通过它可以直接获取到数据
[图片上传失败...(image-236a9a-1563956966972)]
- 使用迭代器
vector<int> s{88,85,90,95,77};
cout <<*s.begin() << endl; //88
cout <<*(s.begin()+1) << endl; //85
//...
cout <<*(s.end()-1) << endl;//77
//遍历容器
for(auto i = s.begin() ; i != s.end() ; i++){
cout << *i << endl;
}
3. 关联容器
关联容器和顺序容器有很大的不同，顺序容器的元素在容器中是有顺序的（按照添加先后计算） ， 而关联容器并不计较顺序的概念，因为他们是按照关键字来访问元素的。C++中常用的关联容器有两个：
map和set, map 有点类似 python 里面的字典，使用键值对的形式来存储
1. pair介绍
pair定义在头文件
#include <utility>中，一个pair保存两个数据成员，它是类模板，所以在创建对象的时候，需要添加泛型参数，以用来表示所保存的数据类型。
- 构建pair
pair<string ,int> p("张三",17) ;
cout << p.first << p.second <<endl;
2. map操作
map 只允许产生一对一的关系，也就是一个关键字对应一个值，如生活中大多数人，一人一套房差不多。但是也有人是名下多套房，这时候可以使用
multimap, 它允许一个关键字对应多个值。 它们都定义在头文件#include<map>中。
- 添加
不允许key 有重复的。
map<string , string> address_map ;
//匹配可变参数列表
address_map.insert({"张三" , "星湖花园1号"});
address_map.insert(make_pair("李四" , "星湖花园1号"));
address_map.insert(pair<string ,string>("王五" , "星湖花园1号"));
//有疑问
address_map.insert({"张三" , "星湖花园2号"}); //与第一个同关键字，会覆盖原有数据
- 访问
map可以使用【】的方式来获取指定的元素，要求传递进来的是
key关键字
//访问指定元素
string address = address["张三"] ;
cout << address << endl;
//使用at函数访问
string address2 = map.at("张三2")
cout << address2 << endl;
- 删除
除了能使用迭代器的方式删除之外，关联容器由于使用了关键了记录数据，所以删除的时候也可以根据关键字来删除数据。
//迭代器方式删除。
for(auto i = address_map.begin() ; i != address_map.end() ; i++){
cout <<i->first << " = "<< i->second << endl;
if(i->first == "李四"){
address_map.erase(i);
}
}
//使用关键字删除
address_map.erase("王五");
//清空整个map
address_map.clear();
- 修改
修改其实就是替换，但是如果还是用insert 是无法起作用的，因为它会执行唯一检查。使用 at函数，对某一个特定关键字的位置修改值。
map<string , int> map;
map.insert( {"张三1" ,18});
map.insert( {"张三2" ,28});
map.insert( {"张三3" ,38});
cout <<map["张三1"] << endl; //18
map.at("张三1") = 99;
cout <<map["张三1"] << endl; //99
- 容量查询
判断是否为空、获取大小、判断是否存在key
map<string , int> map;
map.insert( {"张三1" ,18});
//判断是否为空
bool empty = map.empty();
cout <<"empty = " << empty << endl;
//获取大小
int size = map.size();
cout <<"size = " << size << endl;
//查询该key在map中的个数，可用来判断是否存在该key
int count = map.count("张三1");
cout <<"count = " << count << endl;
3. set操作
set就是关键字的简单集合，并且容器内部元素不可重复且有顺序。当只是想知道一个值是否存在时，set是最有用的。 set 为不可重复容器，而multiset为可重复容器。
在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序。set中元素的值不能直接被改变。set内部采用的是一种非常高效的平衡检索二叉树：红黑树，也称为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树。
- 创建对象
//创建空白set容器
set<int>s ;
//创建容器并初始化，可变参数往里面赋值，但是这里添加了重复的3. 后面的3不会被添加进去。
set<int> s1({3,4,5,6,3});
- 添加元素
set<int> s;
s.insert(6);
s.insert({7,8,9,10}); //也可以接收可变参数
- 遍历set
遍历的逻辑和其他含有迭代器的容器一样。
set<int> s1({3,4,5,6,3});
for(auto p = s1.begin(); p != s1.end() ; p++){
cout <<*p << endl;
}
- 删除指定元素
还是使用
erase函数删除 。
set<int> s1({3,4,5,6,3});
for(auto p = s1.begin(); p != s1.end() ; p++){
cout <<*p << endl;
if(*p == 4){
s1.erase(p);
}
}
//清空这个容器
s1.clear();
- 容量查询
判断是否为空、获取大小、判断是否存在key
set<int> s1({3,4,5,6});
//判断是否为空
bool empty = s1.empty();
cout <<"empty = " << empty << endl;
//获取大小
int size = s1.size();
cout <<"size = " << size << endl;
//查询该key在map中的个数，可用来判断是否存在该key
int count = s1.count("张三1");
cout <<"count = " << count << endl;
三、常用容器函数
到目前为止，容器的操作基本上也就包含了增删改查这些基本的功能，但是有时候可能会面临一些特殊的操作，比如：查找特定元素、替换或删除特定值、对容器进行重新排序等等。标准库并未给每个容器实现这些操作的函数，而是定义一组
泛型算法。 算法大部分包含在#include <algorithm>|#include <numeric>
1. 只读函数
这一类算法只会读取元素，并不胡改变元素。常见的有 ：
find|cout|accumulate
- accumulate
它定义在头文件
numeric中，所以不要忘记了导入头文件，它的功能是对一个容器的所有元素取和。
//参数一：求和的起始范围 迭代器
//参数二：求和的结束范围 迭代器
//参数三：最初的求和值，
int a = accumulate(s1.begin(), s1.end() , 0 );
cout <<a << endl;
//cbegin() 和 cend() 的 c 其实是const的意思。
int a2 = accumulate(s1.begin(), s1.end() , 0 );
cout << a2 << endl;
- qaual
比较两个不同类型的容器是否保存了相同的值，比较的是里面保存的值，容器里面的元素类型要一样。
set<int> s1{1,2,3,4,5};
vector<string> v1{"1","2","3","4","5"};
bool flag = equal(s1.begin(), s1.end(),v1.begin());
cout <<flag << endl;
2. 写入函数
- fill
给定一个范围，把这个范围的元素全部替换成指定的值。实际上也是填充的意思。
vector<int> v {10,20,30,40,50,60,70};
fill(v.begin() ,v.end() , 0 ); //从起始到结束，全部用0替换。
fill(v.begin()+1 ,v.end() , 0 ); //从第一个元素后面开始替换成0
- 拷贝
由于数组是不允许拷贝的，若要对数组进行一次拷贝，通常使用copy 函数来实现
int scores[] {66,77,88,99,100};
int scores2[sizeof(scores) / sizeof(int)];
//参数一，表示起始位置，参数二： 结束为止，参数三：拷贝的目标为止
copy(begin(scores), end(scores) , scores2);
- 替换
对一个容器中，某一段范围的某一个指定元素，替换成指定的值。
vector<int> v1 {30,20,30,40,30,60};
//把容器中，从开始到结束为止，所有的30，替换成100.
replace(v1.begin(),v1.end(),30 , 100);
- 容器元素重新排序
有时候有些容器在存储数据时，并没有排序的概念，如果要排序使之输出有一定的格式，可以选择使用
sort对容器进行排序
vector<string> v2{"ab","bc","aa","abc","ac"};
//默认使用字母表顺序排序
sort(v2.begin(),v2.end());
- 删除重复元素
除了set不接受重复元素之外，其他容器都可以接收重复元素，当然map稍微特殊一点，因为它是键值对形式存储，要求的是key不允许重复，值实际上可以重复。
vector<string> v3{"ab","bc","aa","abc","ac","bc","aa","bc"};
//排序
sort(v3.begin(),v3.end());
//确定唯一值，只要是重复元素的，放到后面去 ，前面是不重复的数据，
//也就是重复的元素，把其中一个放到后面去排列
//返回值 end 指向的最后一个不重复的元素位置
auto end = unique(v3.begin(),v3.end());
//看似是删除了从重复位置到v3的结束位置，实际上并不会删除，只是藏起来了。也不占用size的长度
v3.erase(end , v3.size);
cout <<v3.size() << endl;
v3.erase(end , v3.end());
- 自定义排序
默认情况下容器中的排序算法是按照字母表顺序排序，但有时候，我们希望按照自己定义的规则排序，比如我们希望字数多的字符串排在后面，而不是看字母表顺序。mysort 的参数位置还要一个好听的名字，叫做“谓词” ，一元谓词表示这个函数接收一个参数，二元谓词表示接收两个参数，这个函数还要求有一个返回值，以方便底层排序获取我们的定义的排序规则。
//回调函数，由sort内部调用，并且要求返回结果。
bool mysort(const string& a , const string& b){
return a.size() < b.size();
}
vector<string> v2{"ab","bc","aa","abc","ac"};
//默认使用字母表顺序排序 按照我们规定的排序算法排序
sort(v2.begin(),v2.end() , mysort);
//如果字数一样，长度一样，那么再按字母表顺序排序，可以使用stable_sort
stable_sort(v2.begin(),v2.end() , mysort);
四、函数对象
C++语言中有几种可调用对象：
函数、函数指针、lambda表达式、bind创建的对象以及重载了函数调用运算符的类。
1. function 介绍
在前面讲解函数对象的时候，提过，函数对象也是有类型的，函数对象的类型，由函数的返回值类型和参数共同决定。而function的出现让这个定义更为简化。function是一个模板类，可以用来表示函数的类型，当然需要在定义的时候，表示函数的返回值类型以及参数的类型。 除了能使用函数指针来调用函数之外，其实也可以声明一个
function的对象，接收某一个函数，直接调用function的对象，也等同于调用函数。
//函数
string getMaxString(string str1 ,string str2 ,int num){}
//函数指针
string (*pfs)(string ,string , int ) =getMaxString;
pfs（）；
//使用function对象接收函数 <string (string , string , int)>
//前面的string 表示返回值 <>表示接收的参数类型，个数要对应上。
function<string (string , string , int)> f= getMaxString;
2. function 使用
- 接收全局函数
void print(int a , string b){}
function<void (int ,string)> f = print;
- 接收lambda表达式
function<int (int ,int)> f = [](int a ,int b){return a + b ;};
f(1 ,2 );
- 接收成员函数
接收成员函数时，需要额外提供，调用函数的对象实体，可以是对象，可以是引用，可以是指针。也就是参数的第一个位置写调用这个函数的对象实体
class stu{
public:
int run(string name ,int age){
cout <<"run" << endl;
}
};
//实际上我门想的应该是这样： 因为run 函数的返回值是int, 接收两个参数(string ,int)
//但是不能这么做，因为这个函数是非静态函数，也不是全局函数，它是成员函数，不能直接调用，
//如果编译通过，那么直接使用f("aa" , 18) ; 显然是不允许的。
function <int ( string , int )> f1 = &stu::run; //错误写法
function <int (stu , string , int )> f1 = &stu::run; //正确写法 对象
function <int (stu& , string , int )> f2 = &stu::run; //正确写法 对象引用
function <int (stu* , string , int )> f3 = &stu::run; //正确写法 指针
//真正调用run();
stu s1;
f1(s1 , "张三" , 18 ); //会发生拷贝
stu s2;
f2(s2 , "张三" , 18 ); //避免发生拷贝，引用指向实体
stu s3;
f3(&s3 , "张三" , 18 );
2. bind
c++ 11推出的一套机制
bind，它可以预先把指定可调用实体的某些参数绑定到已有的变量，产生一个新的可调用实体，这种机制常常出现在回调函数中。说的简单点就是，有一个可以直接调用的实体，但是可以对这个实体进行一下包装，包装出来的实体，也可以调用，那么调用这个包装的实体，等同于调用原来的实体。
bind到底绑的是什么呢?1 ，可以理解为把函数、函数的实参。
- 绑定全局函数
int add3(int a ,int b){
cout <<"执行了add函数" << endl;
return a + b;
}
//可以看成是把p 绑定到add3上， 以后使用p() 等同于 add3()
//但是bind的一个好处是，参数不用在后续调用p()的时候传递了，因为在绑定的时候已经传递进来了。
auto p = bind(add3 , 3 ,4 );
int b = p();
cout <<"b = "<< b << endl;
//也可以是用function来接收，但是由于参数的值已经在bind的时候传递进去了，所以接收的时候
//function的参数可以使用() 表示无参。否则在调用p1的时候，还必须传递参数进来
function<int ()> p1 = bind(add3 , 5 ,4 );
int a =p1();
cout <<"a = "<< a << endl;
- 当定成员函数
bind也可以 bind 类中的某个成员函数
