模板

函数模板

建立通用函数，返回值类型和形参类型可以不具体指定，用一个虚拟的类型代表，即类型参数化

语法
1
2
template<typename T> ret-type func-name(parameter list)
- T 一个符号，通常使用大写字母，代表通用数据类型
- 可以有默认类型 template<typename T = int>

示例

定义

template<typename T>
T myAdd(T a, T b){
    return a + b;
}

调用

1 2	`myAdd<int>(0, 1); // 显式类型指定 myAdd(1, 2); // 自动类型推导`

注意事项

必须能够推导出数据类型

template<typename T>
void func(){
    cout<<"func函数调用"<<endl;
}

func();	// 错误

必须推导出一致的数据类型

template<typename T>
T myAdd(T a, T b){
    return a + b;
}

int a = 10;
char c = 'c';
myAdd(a,c);  // 错误，推导出不一致的类型 T

普通函数与函数模板的区别：
- 普通函数调用时可以发生隐式类型转换
- 函数模板调用时，如果是自动类型推导，则不会发生隐式类型转换
  如果在调用时使用显式类型指定(myAdd<int>)，则可以发生隐式类型转换

普通函数与函数模板的调用规则：

如果普通函数与函数模板都可以实现，优先调用普通函数
但是可以通过空模板参数列表来强制调用函数模板
如果函数模板可以产生更好的匹配，优先调用函数模板

void foo(int a,int b){
    cout<< "调用普通函数" <<endl;
}

template<typename T>
void foo(T a,T b){
    cout<< "调用模板" <<endl;
}

int main() {
    int a(10), b(20);
    
    foo(a,b);			   //调用普通函数
    foo<>(a,b);			//调用模板--空参数列表
    foo<int>(a,b);		//调用模板

    char c('c'),d('d');
	 foo(c,d);			   //调用模板--更好的匹配
}

类模板

建立一个通用类，类中的成员的数据类型可以不具体指定，用一个虚拟的类型代表

语法：

1 2	`template<class T> 类`

类模板也可以有默认类型

举例：

template<class NameType, class AgeType>
class Person
{
public: 
    Person(NameType name, AgeType age){
        this->m_Name = name;
        this->m_Age = age;
    }
    
    NameType m_Name;
    AgeType m_age;
};

void test01(){
    Person<string, int> p1("张三",18);
}

类模板的自动类型推导 (Since C++17)

能通过构造函数推导出类型参数

template<typename T>
class Test{
public:
	Test(T a) : value(a){}
    const T & value;
};

Test t {1};

模板类成员函数的创建

类模板中成员函数的创建时机：

普通类的成员函数一开始就创建
模板类的成员函数在调用时才创建

class Person1{
public:
    void showPerson1(){cout<<"showPerson1调用"<<endl;}
};

class Person2{
public:
    void showPerson2(){cout<<"showPerson2调用"<<endl;}
};

template<class T>
class show{
public:
    T obj;

    void func1(){obj.showPerson1();}
    void func2(){obj.showPerson2();}
};
void test01(){
    show<Person1> s1;
    s1.func1();
    show<Person2> s2;
    s2.func2();
}

类模板对象做函数参数

指定传入的类型
参数模板化
整个类模板化

template<class T1, class T2 = int>
class Person{
public:
    Person(T1 name, T2 age){
        this->mName = name;
        this->mAge = age;
    }
    void showPerson(){
        cout<<"name:"<<this->mName<<" "<<"age:"<<this->mAge<<endl;
    }
public:
    T1 mName;
    T2 mAge;
};

void printPerson1(Person<string, int>&p){
    p.showPerson();
}
template<typename T1, typename T2>
void printPerson2(Person<T1, T2>&p){
    p.showPerson();
}
template<class T>
void printPerson3(T & p){
    p.showPerson();
}
void test01(){
    Person<string, int> p1("孙悟空", 100);
    printPerson1(p1);
    printPerson2(p1);
    printPerson3(p1);
}

类模板与继承

当父类是类模板时，如果子类不是模板，就要指出父类中T的类型
class Son:public Base<数据类型>

如果想灵活指出父类中T的类型，子类也需变为类模板

template<class T1, class T2>
class Son:public Base<T2>
{
public:
    T1 obj;
};

类模板成员函数类外实现

//构造函数类外实现
template<class T1, class T2>
Person<T1, T2>::Person(T1 name, T2 age){
    this->m_Name;
    this->m_Age;
}
//成员函数类外实现
template<class T1, class T2>
void Person<T1, T2>::showPerson(){
    cout<< this->m_Name << " " << this->m_Age <<endl;
}

类模板分文件编写

问题：

类模板中成员函数的创建时机是在调用阶段，导致分文件编写时链接不到

解决：

方式一：直接包含.cpp源文件

方式二：将声明和实现写到同一个文件中，例如都写到一个.hpp文件中

#pragma once
#include <iostream>
#include <string>
using namespace std;

template<class T1, class T2>
class Person{
//...
}
//类外实现的函数
//...

类模板与友元

//2.类外实现
template<class T1, class T2> class Person;
//2.如果声明了函数模板，可以将实现写到后面，否则需要将实现体写到类的前面
//template<class T1, class T2> void printPerson2(Person<T1, T2> &p);
template<class T1, class T2>
void printPerson2(Person<T1, T2> &p){
    cout<<"类外实现--name:"<<p.m_Name<<" "<<"age:"<<p.m_Age<<endl;
}

template<class T1, class T2>
class Person{
    //1.全局函数配合友元 类内实现
    friend void printPerson(Person<T1, T2> &p){
        cout<<"类内实现--name:"<<p.m_Name<<" "<<"age:"<<p.m_Age<<endl;
    }

    //2.全局函数配合友元 类外实现
    //需要空参数列表
    friend void printPerson2<>(Person<T1, T2> &p);

public:
    Person(T1 name, T2 age){
        this->m_Name = name;
        this->m_Age = age;
    }
public:
    T1 m_Name;
    T2 m_Age;
};

STL

基本概念：

STL(Standard Template Library, 标准模板库)
STL从广义上分为：容器(container)、算法(algorithm)、迭代器(iterator)
容器和算法之间通过迭代器进行无缝连接

组件：

STL大体分为六大组件，分别是：容器、算法、迭代器、仿函数、适配器(配接器)、空间配置器

容器：各种数据结构，如vector、list、deque、set、map等，用来存放数据
算法：各种常用的算法，如sort、find、copy、for_each等
迭代器：扮演了容器与算法之间的胶合剂
仿函数：行为类似函数，可作为算法的某种策略
适配器：一种用来修饰容器或者仿函数或迭代器接口的东西
空间配置器：负责空间的配置与管理

容器 (container)

用于存放数据的类模板

分类：

顺序容器：向量容器vector、双端队列deque、双向链表list
关联容器：单重集合set、多重集合multiset、单重映射表map、多重映射表multimap
容器适配器：栈stack、队列queue、优先级队列priority_queue

string

string是C++风格的字符串，本质是一个类
string类内部封装了char*，管理这个字符串，是一个char*型的容器
string类内部封装了很多成员方法，例如size,find,copy,delete,replace,insert

构造和赋值

构造：

string();
string(const char* s);
string(const string& str);
string(int n, char c);

赋值：

string& operator=(const char* s); //str1 = "Hello";
string& operator=(const string &s); //str2 = str1;
string& operator=(char c); //str3 = 'a';
string& assign(const char* s); //str4.assign("Hello");
string& assign(const char* s, int n); //str5.assign("Hello",2);
string& assign(const string &s);
string& assign(int n, char c);

大小比较：

int compare(const string &s) const;
int compare(const char *s) const;

返回值：

相等：0

大于：1

小于：-1

字符串拼接

string& operator+=(const char* str/const string& str/const char c);
string& append(const char *s);
string& append(const char *s, int n); //拼接s的前n个字符
string& append(const string &s);
string& append(const string &s, int pos, int n); //拼接s的pos位置后的n个位置

查找和替换

查找：

int find(const string& str, int pos = 0) const; //从pos位置开始，查找str第一次出现的位置
int find(const char* s, int pos = 0) const;
int find(const char* s, int pos, int n) const; //从pos位置开始查找s的第n个字符第一次出现的位置
int find(const char c, int pos = 0) const; //查找字符c第一次出现位置
rfind函数：从右向左查找，用法同上，默认起始位置是最后一个

string str1 = "abcdefg";
int pos = str1.find("df");
if(pos == -1)cout<<"未找到"<<endl;
else cout<<"找到字符串，位置是"<<pos<<endl;

替换：

string& replace(int pos, int n, const string& str); //替换从pos开始的n个字符为str
string& replace(int pos, int n, const char* s); //替换从pos开始的n个字符为s

字符存取：

char& operator[](int n);
char& at(int n);

字符数目：

size();

插入和删除

string& insert(int pos, const char* s);
string& insert(int pos, const string& str);
string& insert(int pos, int n, char c);
string& erase(int pos, int n = npos);

子串获取

string substr(int pos = 0, int n = npos) const;

1
2
3

string email = "zhangsan@sina.com";
int pos = email.find("@");
string username = email.substr(0, pos);

vector

vector数据结构和数组类似，也称为单端数组

与普通数组的区别

vector可以动态扩展

动态扩展：

并不是在原空间之后续接新空间，而是找更大的空间，然后将数据拷贝到新空间，释放原空间

vector容器的迭代器是支持随机访问的迭代器，可以像数组一样用[]访问数据

构造和赋值

构造函数：

vector<T> v; //默认构造函数
vector(v.begin(), v.end()); //将v[begin(), end())区间中的元素复制给本身
vector(n, elem); //将n个elem复制给本身
vector(const vector &vec); //复制构造

vector<int> v1;
for(int i=0;i<10;i++)
    v1.push_back(i);

vector<int> v2(v1.begin(), v1.end());
vector<int> v3(10, 100);
vector<int> v4(v3);

赋值操作：

vector& operator=(const vector &vec)
assign(begin, end)
assign(n,elem)

遍历数据

算法： for_each

迭代器：vector<int>::iterator

void test01(){

    vector<int> v;
    v.push_back(10);v.push_back(20);v.push_back(30);

    //通过迭代器访问数据
    vector<int>::iterator itBegin = v.begin();  //起始迭代器 指向容器中第一个元素
    auto itEnd = v.end();  //使用auto定义迭代器 结束迭代器 指向最后一个元素的下一位

    //第一种遍历方式
    while(itBegin != itEnd){
        cout<< *itBegin <<endl;
        itBegin++;
    }
    
    //for循环
    for(vector<int>::iterator it = v.begin();it!=v.end();it++)
        cout<< *itBegin <<endl;
    
    //第二种遍历方式 使用基于范围的for循环
    for(int & it : v)
        cout<< it <<endl;
    
    //第三种遍历方式
    for_each(v.begin(), v.end(), myPrint);
}

数据存取：

at(int idx); //返回索引idx指向的数据
operator[]; //返回下标对应的元素
front(); //返回容器中第一个数据元素
back(); //返回容器中最后一个数据元素

//[]遍历数据
for(int i=0;i<v.size();i++)
    cout<<v[i]<<" ";
//at遍历数据
for(int i=0;i<v.size();i++)
    cout<<v.at(i)<<" ";

容量和大小：

empty(); //返回一个bool值，判断容器是否为空
capacity(); //容器的容量，大于等于size()
size(); //返回容器中元素的个数
resize(int num); //重设长度，若变长以默认值填充，若变短从尾部删除
resize(int num, elem); //重设长度，若变长以elem值填充，若变短从尾部删除

插入和删除

注：提供的位置pos都是迭代器

函数原型	作用
`push_back(ele);`	尾插
`pop_back();`	尾删

`insert(pos, elem);`	在pos位置插入elem元素，返回新数据的位置
`insert(pos, n, elem);`	在pos位置插入n个elem数据，无返回值

`erase(begin, end);`	删除[begin,end)区间的数据，返回下一个数据的位置
`erase(pos);`	删除pos位置的数据，返回下一个数据的位置
`clear();`	清空容器内的所有数据

互换容器：

swap(vec); //将vec与本身的元素互换

1	`v1.swap(v2);`

用途：收缩内存空间

vector<int> v;
for(int i=0;i<100000;i++)
    v.push_back(i);

cout<<"大小"<<v.size()<<"容量"<<v.capacity()<<endl;    //输出10万和13万(大约)

v.resize(3);  //重设大小为3，容量不会减少
cout<<"大小"<<v.size()<<"容量"<<v.capacity()<<endl;    //输出3和13万(大约)

vector<int>(v).swap(v);//使用复制构造创建匿名对象，与v交换
//这里也可用v.shrink_to_fit();自动收缩
cout<<"大小"<<v.size()<<"容量"<<v.capacity()<<endl;    //输出3和3

预留空间：

减少vector在动态扩展容量时的扩展次数

函数原型：

reserve(int len); //预留len个元素长度，预留位置不初始化，元素不可访问

容器嵌套

vector<vector<int>> v;

1
2
3

for (vector<vector<int>>::iterator it = v.begin();it != v.end();it++)
    for(vector<int>::iterator vit = (*it).begin();vit != (*it).end();vit++)
        cout<<*vit<<" ";

deque

双端数组，可以对头端进行插入删除操作

deque与vector的区别：

vector对头部的插入删除效率低，数据量越大，效率越低
相对而言，deque对头部的插入删除速度比vector快
vector访问元素时的速度会比deque快，这和两者的内部实现有关

deque工作原理：

在缓冲区存放数据，使用中控器维护每段缓冲区的地址，使得使用deque时就像一片连续的空间

deque容器的迭代器也是支持随机访问的

构造和赋值

构造函数：

deque<T> deq
deque(begin, end);
deque(n, elem);
deque(const deque &deq);

deque<int> d;

for(int i=0;i<10;i++)
    d.push_back(i);

deque<int>d2(d.begin(),d.end());
deque<int>d3(10,100);
deque<int>d4(d3);

赋值操作与vector类似

deque& operator=(const deque &deq)
assign(begin, end)
assign(n,elem)

数据存取同vector

at(int idx); //返回索引idx指向的数据
operator[]; //返回下标对应的元素
front(); //返回容器中第一个数据元素
back(); //返回容器中最后一个数据元素

大小操作：

deque.empty();
deque.size();
deque.resize(num);
deque.resize(num, elem);

deque与vector不同，没有容量概念，所以没有capacity();函数

void printDeque(const deque<int>& d){
	for(deque<int>::const_iterator it = d.begin();it != d.end();it++)
        cout<<*it<<" ";
    cout<<endl;
}

插入和删除

注：提供的位置pos都是迭代器

函数原型	作用
`push_back(elem);`	尾插
`push_front(elem);`	头插
`pop_back();`	尾删
`pop_front();`	头删

`insert(pos, elem);`	在pos位置插入elem元素，返回新数据的位置
`insert(pos, n, elem);`	在pos位置插入n个elem数据，无返回值
`insert(pos, begin, end);`	在pos位置插入[begin, end)区间的数据，无返回值

`erase(begin, end);`	删除[begin,end)区间的数据，返回下一个数据的位置
`erase(pos);`	删除pos位置的数据，返回下一个数据的位置
`clear();`	清空容器内的所有数据

数据排序

头文件：<algorithm>

sort(iterator begin, iterator end)

stack

栈是一种先进后出 (FILO, First In Last Out)的数据结构，它只有一个出口

只有顶端的元素才能被使用，因此栈不允许有遍历行为

常用接口

构造函数：

stack<T> stk;
stack (const stack &stk);

赋值操作：

stack& operator=(const stack &stk);

数据存取：

push(elem);
pop();
top();

大小操作：

empty();
size();

queue

队列是一种先进先出 (FIFO, First In First Out)的数据结构，它有两个出口

队列容器允许从一端新增元素，从另一端移除元素

栈不可遍历

常用接口

构造函数：

queue<T> que;
queue (const queue &que);

赋值操作：

queue& operator=(const queue &que);

数据存取：

push(elem);
pop();
back();
top();

大小操作：

empty();
size();

list

STL中的链表是双向循环链表

优点：在任意位置插入或删除元素的速度较快

缺点：容器的遍历速度没有数组快

由于链表的存储方式并不是连续的内存空间，因此list中的迭代器只支持前移和后移，属于双向迭代器

构造和赋值

构造函数：

list<T> ls;
list(begin, end);
list(n, elem);
list(const list &ls);

赋值和交换：

assign(begin, end);
assign(n, elem);
list& operator=(const list &ls);
swap(ls);

大小操作：

size();
empty();
resize(num);
resize(num, elem);

数据存取：

front();
back();

插入和删除

注：提供的位置pos都是迭代器

函数原型	作用
`push_back(elem);`	尾插
`push_front(elem);`	头插
`pop_back();`	尾删
`pop_front();`	头删

`insert(pos, elem);`	在pos位置插入elem元素，返回新数据的位置
`insert(pos, n, elem);`	在pos位置插入n个elem数据，无返回值
`insert(pos, begin, end);`	在pos位置插入[begin, end)区间的数据，无返回值

`erase(begin, end);`	删除[begin,end)区间的数据，返回下一个数据的位置
`erase(pos);`	删除pos位置的数据，返回下一个数据的位置
`clear();`	清空容器内的所有数据
`remove(elem);`	删除容器中所有与elem值匹配的元素

反转和排序

reverse(); //反转
sort(); //排序

注意：不支持随机访问迭代器的容器，不可以用标准算法

sort(l.begin(), l.end()); //错误，应该使用内部提供的算法l.sort();

降序排列：

bool myCompare(int v1, int v2){
    return v1 > v2;
}
void test01{
    L1.sort(myCompare);
}

set / multiset

set/multiset属于关联式容器，底层结构是用二叉树实现的
元素会在插入时自动排序

构造和赋值

构造：

set<T> st;
set(const set &st);

赋值：

set& operator=(const set &st);

大小和交换：

size();
empty();
swap(st);

插入和删除：

insert(elem);
clear();
erase(pos);
erase(begin, end);
erase(elem);

查找和统计

find(elem); //返回值是迭代器，找不到则返回s.end()
count(elem); //返回elem的个数

1 2	`set<int>::iterator pos = s1.find(30); if(pos != s1.end()) cout<<*pos<<endl;`

set和multiset的区别

set不允许插入重复的元素
multiset允许重复的元素

set的插入操作会返回一个对组(迭代器, bool值)

set<int> s;

pair<set<int>::iterator, bool> ret = s.insert(10);

if(ret.second) cout<<"插入成功"<<endl;

multiset的插入操作会返回一个迭代器

注：对组的创建：

pair<type, type> p (value1, value2);
pair<type, type> p = make_pair(value1, value2);

指定排序规则

set存放内置数据类型：

class MyCompare{
public:
    bool operator()(int v1, int v2){
        return v1 > v2;
    }
};

void test01(){
    set<int, MyCompare> s1;
    s1.insert(10);
    s1.insert(20);
    
    for(set<int, MyCompare>::iterator it = s1.begin(); it != s1.end(); it++)
        cout<<*it;
}

set存放自定义数据类型：

class Person
{
public:
    Person(string name,int age){
        this->m_Name=name;
        this->m_Age=age;
    }

    string m_Name;
    int m_Age;
};

class PersonCompare{
public:
    bool operator()(const Person& p1,const Person& p2){
        return p1.m_Age > p2.m_Age;
    }
};


void test02(){

    Person p1("张飞",18),
    p2("刘备",20),
    p3("关羽",19);

    set<Person,PersonCompare> s;
    s.insert(p1);
    s.insert(p2);
    s.insert(p3);

    for(const auto & it : s) cout<<it.m_Name;
}

map / multimap

map中的元素是键值对pair(key:value)
元素根据key自动排序
map/multimap属于关联式容器，底层结构是用二叉树实现

map与multimap的区别：

键是否唯一

构造和赋值：

map<T1, T2> mp;
map(const map &mp);

赋值：

map& operator=(const map &mp);

插入和删除：

insert
- insert(pair<__keyType, __valueType>(__key, __value));
- insert(make_pair(__key,__value));
- insert(map<__keyType, __valueType>::value_type(__key, __value));
- m[__key] = __value;
clear();
erase(pos);
erase(begin, end);
erase(key);

大小和交换：

size();
empty();
swap(st);

查找和统计：

find(key); //返回值是迭代器，找不到返回set.end()
count(key); //返回key的个数

函数对象 (仿函数)

函数对象

概念：

函数对象是一个类，类中重载了函数调用操作符，也叫仿函数

特点：

函数对象在使用时，可以像普通函数一样，可以有参数、有返回值
函数对象超出普通对象的概念，函数对象可以有自己的状态
函数对象可以作为参数传递

谓词

概念：

返回bool类型的仿函数称为谓词
如果operator()接受一个参数，那么叫做一元谓词
如果operator()接受两个参数，那么叫做二元谓词

一元谓词：

class GreaterThan5{
public:
    bool operator()(int v){
        return v > 5;
    }
};

void test03(){
    vector<int> v;
    v.reserve(10);
    for(int i=0;i<10;i++){
        v.push_back(i);
    }

    auto it = find_if(v.begin(),v.end(),GreaterThan5());
    if(it == v.end())cout<<"未找到";
    else cout<<"找到："<<*it;
}

二元谓词：

class myCompare{
public:
    bool operator()(int v1, int v2){
        return v1 > v2;
    }
};

void test04(){
    vector<int> v;
    v.reserve(10);
    for(int i=0;i<10;i++){
        v.push_back(i);
    }

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

    for(auto i : v)cout<<i;
}

内建函数对象

STL内建了一些函数对象
使用内建函数对象，需要引入头文件<functional>

算术仿函数

template<class T> T plus<T>
template<class T> T minus<T>
template<class T> T multiplies<T>
template<class T> T divides<T>
template<class T> T modulus<T>
template<class T> T negate<T>

关系仿函数

template<class T> bool equal_to<T>
template<class T> bool not_equal_to<T>
template<class T> bool greater<T>
template<class T> bool greater_equal<T>
template<class T> bool less<T>
template<class T> bool less_equal<T>

逻辑仿函数

template<class T> bool logical_and<T>
template<class T> bool logical_or<T>
template<class T> bool logical_not<T>

「C++」 泛型编程和 STL

模板

函数模板

类模板

类模板的自动类型推导 (Since C++17)

模板类成员函数的创建

类模板对象做函数参数

类模板与继承

类模板成员函数类外实现

类模板分文件编写

类模板与友元

STL

容器 (container)

string

构造和赋值

字符串拼接

查找和替换

插入和删除

子串获取

vector

构造和赋值

遍历数据

插入和删除

容器嵌套

deque

构造和赋值

插入和删除

数据排序

stack

常用接口

queue

常用接口

list

构造和赋值

插入和删除

反转和排序

set / multiset

构造和赋值

查找和统计

set和multiset的区别

指定排序规则

map / multimap

构造和赋值：

插入和删除：

函数对象 (仿函数)

函数对象

谓词

内建函数对象

算术仿函数

关系仿函数

逻辑仿函数

「C++」泛型编程和 STL