泛型(generic)允许在静态类型语言中使用一些以后才指定的类型,在实例化时作为参数指明这些类型,即类型参数化。在C++中,泛型又称为模板。STL则指标准模板库,是一个C++软件库
模板
- C++另一种编程思想称为泛型编程,主要的技术是模板
- C++提供两种模板机制:函数模板和类模板
函数模板
建立通用函数,返回值类型和形参类型可以不具体指定,用一个虚拟的类型代表
即类型参数化
语法:
template<typename T>
函数声明或定义
解释:
- template 声明创建模板
- typename 表示其后面的符号是一种数据类型,可以用class代替
- T 一个符号,通常使用大写字母,代表通用数据类型
示例:
template<typename T>
void mySwap(T& a,T& b){
T temp = a;
a = b;
b = temp;
}
void test01(){
int a(10),b(20);
//自动类型推导
mySwap(a,b);
//显式类型指定
mySwap<int>(a,b);
}
自动类型推导的注意事项:
必须能够推导出数据类型
template<typename T> void func(){ cout<<"func函数调用"<<endl; } void test02(){ func(); //错误 func<int>(); }
必须推导出一致的数据类型
int a(10);char c('c'); mySwap(a,c); //错误
插入排序模板:
template<typename T>
void mySort(T* a,int n){
for(int i=0;i<n;i++){
int min = i;
for(int j=i+1;j<n;j++)
if(a[j]<a[min]) min=j;
swap(a[min],a[i]);
}
}
普通函数与函数模板的区别:
- 普通函数调用时可以发生隐式类型转换
- 函数模板调用时,如果是自动类型推导,则不会发生隐式类型转换
- 如果是显式类型指定,则可以发生隐式类型转换
普通函数与函数模板的调用规则:
- 如果普通函数与函数模板都可以实现,优先调用普通函数
- 可以通过空模板参数列表来强制调用函数模板
- 函数模板也可以发生重载
- 如果函数模板可以产生更好的匹配,优先调用函数模板
void myPrint(int a,int b){
cout<<"调用的普通函数"<<endl;
}
template<typename T>
void myPrint(T a,T b){
cout<<"调用的模板"<<endl;
}
void test01() {
int a(10),b(20);
myPrint(a,b); //调用普通函数
myPrint<>(a,b); //调用模板--空参数列表
myPrint<int>(a,b); //调用模板
char c('c'),d('d');
myPrint(c,d); //调用模板--更好的匹配
}
函数模板的具体化
//通用函数模板
template<typename T>
bool myCompare(T& a, T& b){
//...
}
//具体化,具体化优先于通用模板
template<> bool myCompare(Person& p1, Person& p2){
//...
}
类模板
建立一个通用类,类中的成员的数据类型可以不具体指定,用一个虚拟的类型代表
语法:
template<typename 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);
}
类模板与函数模板的区别:
- 类模板没有自动类型推导
类模板的参数列表可以有默认参数类型
template<class NameType, class AgeType = int> 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> p1("张三",18); }
类模板中成员函数的创建时机:
- 普通类中的成员函数
- 类模板中的成员函数在调用时创建
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几乎所有代码都采用了模板类或者模板函数
组件:
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个字符为strstring& 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;
string email = "[email protected]";
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与本身的元素互换
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;
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的个数
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>
哇塞,好厉害的说
😡