模版编程 (9小节)
约 3999 字大约 13 分钟
2026-11-11
1.模板函数
定义
模板函数:建立一个通用函数,函数返回类型、形参类型不具体指定。 只要函数体逻辑相同,就可以用同一个模板代替,只定义一次。 调用时编译器根据实参类型替换模板里的虚拟类型,生成对应版本函数。
原来写法(函数重载,重复代码)
int max(int a, int b);
float max(float a, float b);
int max(int a, int b)
{
if(a>b){
return a;
}
return b;
}
float max(float a, float b)
{
if(a>b){
return a;
}
return b;
}改成模板函数写法
template<typename T> //模板声明,T是虚拟类型,typename可以换成class
T max(T a, T b )
{
if(a>b){
return a;
}
return b;
}补充:普通函数 和 模板函数同时存在
#include<iostream>
using namespace std;
//普通int加法函数
int Add(int left, int right)
{
printf("当然是直接用现成的啦+");
return left + right;
}
//通用加法模板函数
template<class T>
T Add(T left, T right)
{
printf("T");
return left + right;
}
int main()
{
Add(1, 2); //优先调用普通函数
return 0;
}规则:编译器调用时,有现成普通函数就调用现成的,没有就用模板生成
✅总结
模板函数用来解决逻辑相同、类型不同的函数重复定义问题;用template<class T>或template<typename T>声明;当同名字普通函数和模板函数都匹配时,优先匹配普通函数。
2.模板类
格式
template <class 类型名>
class 类名
{
// 类实现
};
class也可以写成typename,效果一样
示例代码
#include <iostream>
using namespace std;
template <class T>
class A
{
public:
// 构造函数参数使用模板类型
A(T t){
this->t = t;
}
// 成员函数返回值使用模板类型
T& getT(){
return t;
}
private:
// 成员变量使用模板类型
T t;
};
int main() {
// 模板类创建对象,必须显式指定类型
A<int> a(666);
cout << a.getT() << endl;
return 0;
}普通类对照例子
#include <iostream>
using namespace std;
class A{
public:
A(int score){
this->score=score;
}
int getScore(){
return this->score;
}
private:
int score;
};
class B{
public:
B(double score){
this->score=score;
}
double getScore(){
return this->score;
}
private:
double score;
};
int main() {
A a(22);
B b(22.2);
cout<<a.getScore()<<endl;
cout<<b.getScore()<<endl;
return 0;
}- 普通类B:写死了只能存
double类型 - 模板类A:T可以换成int、double等任意类型,一套代码复用
重点规则
模板类实例化对象必须显式写出类型:A<int> a(666);,不能直接写 A a(666);(和模板函数不一样,模板函数可以自动类型推导)
✅总结
模板类是给类用的模板,把类里面的成员变量、成员函数的类型抽象成虚拟类型T;普通类的成员类型是固定死的,模板类灵活可变。模板类在创建对象时,必须显式指定模板参数类型,编译器根据这个类型生成对应的真实类。
3.STL概念
STL:Standard Template Library,标准模板库 由容器 + 算法组成
- 容器:封装好的数据结构,如 vector、list、map、stack,用来存放数据
- 算法:通用算法,如 sort、find、copy、for_each
3.1、vector(动态数组,模板容器)
头文件:#include <vector> 作用:存放一串连续数据,可以替代原生数组
1. 初始化
vector<int> vec1; // 空容器
vector<float> vec2(3); // 3个元素,默认0
vector<char> vec3(3, 'a'); // 3个'a'
vector<char> vec4(vec3); // 拷贝构造2. 插入删除
push_back(ele); // 尾部插入
pop_back(); // 删除末尾元素
insert(迭代器位置, ele); // 指定位置插入一个元素
insert(迭代器位置, count, ele); // 指定位置插入count个ele
clear(); // 清空所有元素
erase(迭代器); // 删除迭代器指向元素
erase(begin, end); // 删除区间内元素3. 遍历方式
// 下标遍历
for(int i=0;i<vec.size();i++){
cout << vec[i];
}
// range-for
for(auto v : vec3){
cout << v;
}
// 迭代器遍历
for(vector<Person>::iterator it = vec.begin(); it != vec.end(); it++){
cout << (*it).m_Name;
}4. 常用API
empty(); // 判断是否为空
capacity(); // 容器容量
size(); // 实际元素个数
resize(num); // 修改有效元素数量5. 存放自定义类型示例
class Person
{
public:
Person(string name, int age)
{
m_Name = name;
m_Age = age;
}
public:
string m_Name;
int m_Age;
};
vector<Person> vec;
Person p1("aaa",81);
vec.push_back(p1);3.2、list(双向循环链表)
头文件:#include <list> 特点:链式存储,双向循环链表;相比vector,支持头部快速增删
list<int> L;
L.push_back(10); // 尾插
L.push_front(100); // 头插
L.pop_back(); // 尾删
L.pop_front(); // 头删其他insert、erase、遍历、size、empty接口和vector用法基本一致
3.3、map(键值对集合)
头文件:#include <map> 特点:存储key-value键值对,key自动排序、key不重复
1. 初始化
map<int,int> maps1;
map<int,int> maps2{{1,2},{3,4}};
map<int,int> maps3(maps2); //拷贝2. 插入
map4.insert(pair<int,string>(1,"hello"));
map4.insert(map<int,string>::value_type(2,"hi"));
map4[10] = "hello"; //数组方式插入/修改3. 遍历
map<int,int>::iterator it;
for(it = a.begin(); it != a.end(); it++){
cout << it->first << "=" << it->second;
}
// first是key,second是value4. 常用API
begin()
end()
clear()
count(key) // 判断key是否存在
empty()
size()
find(key) // 查找key,返回迭代器
erase(迭代器) // 删除指定键值对
swap() // 交换两个map3.4、stack(栈)
头文件:#include <stack> 特点:先进后出(LIFO),只有栈顶一个出入口
stack<int> s;
s.push(10); //入栈(压栈)
s.pop(); //出栈(弹出栈顶,不返回值)
s.top(); //获取栈顶元素
s.empty(); //判空
s.size(); //元素数量3.5、queue 队列(先进先出 FIFO)
✅ 头文件:#include <queue> ✅ 核心特点:先进先出,一端入队、一端出队;没有迭代器,不能随机访问
- 队尾:
push()入队;back()获取队尾元素 - 队头:
pop()出队(只删除,无返回值);front()获取队头元素 - 容量判断:
empty()判断是否为空;size()返回元素个数
⚠️ 重点坑点:
pop()不会返回元素,要先front()拿到队头,再 pop- 队列不支持下标访问、不支持遍历(只能循环取队头再弹出)
- 可以存放自定义类对象(比如示例里的Person)
示例逻辑:
queue<Person> q;
q.push(p1); // 队尾入队
while(!q.empty())
{
cout << q.front().name; // 取队头
q.pop(); // 删除队头
}3.6、string 字符串(封装好的字符串类,替代char[])
✅ 头文件:#include <string> ✅ 本质:类,封装大量字符串操作,下标从0开始
1. 构造
string str; // 空串
string str("hello"); // C风格字符串初始化
string str2(str); // 拷贝构造2. 赋值 & 拼接
- 赋值:
=/assign(字符指针, n)取前n个字符赋值 - 拼接:
+=、`append()
str.append("abc");
str.append("abcd",2); // 追加ab3. 查找 find / rfind
find(子串,pos):从pos向后找,第一次出现位置,找不到返回string::npos(-1)rfind(子串,pos):从pos向前找,最后一次出现位置
4. 替换 replace
replace(pos, n, newStr):从pos开始,删掉n个字符,替换成新字符串
5. 比较 compare
compare() 按ASCII码逐字符对比
- 返回 0 → 相等
- 返回 >0 → 当前串更大
- 返回 <0 → 当前串更小>
也可以直接用
> < == !=比较string对象
6. 存取、插入、删除、子串
- 取字符:
str.at(idx)(越界抛异常,比[]安全) - 插入:
insert(pos, "xxx")在pos位置插入字符串 - 删除:
erase(pos, n)从pos删除n个字符,缺省n删到末尾 - 截取子串:
substr(pos, n)从pos取n个字符,返回新string
⚠️ 重点坑点:
- 所有下标 从0开始
- find找不到是
string::npos,不要直接写 == -1(虽然很多编译器兼容) - substr是得到新字符串,原字符串不变
4、sort 排序算法(快速排序)
✅ 头文件:#include <algorithm> ✅ 特点:随机访问迭代器才能用sort(vector、string可以;list不可以!list自带.sort()成员函数) ✅ 区间:[first, last) 左闭右开,sort(begin, end)
两种重载:
sort(首迭代器, 尾迭代器):默认升序从小到大sort(首, 尾, 比较函数comp):自定义排序规则
常用写法
vector<int> v = {9,6,3};
sort(v.begin(),v.end()); // 升序
sort(v.begin(),v.end(), greater<int>());// 降序,内置仿函数自定义比较函数(最常用,排自定义对象)
// 返回 true:代表 a 应该排在 b 前面
bool cmp(Person &a, Person &b)
{
if(a.age == b.age)
return a.height > b.height; // 年龄相同,身高降序
return a.age < b.age; // 年龄升序
}✅ 规则口诀:
return a < b→ 升序;return a > b→ 降序
⚠️ 重点坑点:
- ❌ list不能用std::sort!list是双向迭代器,没有随机访问,要用
list对象.sort(比较函数) - 比较函数必须是严格弱序,不要写
>=/<=,只用>/< - sort是原地排序,直接修改原容器
✅总结
vector:连续内存动态数组,随机访问快,中间插入删除慢; list:双向链表,头尾插入删除快,不支持下标随机访问; map:有序键值对容器,key唯一自动排序,适合查找; stack:栈,先进后出,只允许操作栈顶; 全部都是STL模板容器,定义时都需要显式指定存储类型。
📌 整体STL阶段性小结(vector + list + queue + string + sort)
| 对象/算法 | 头文件 | 底层结构 | 迭代器类型 | 能不能直接用std::sort | 核心特点、常用接口 |
|---|---|---|---|---|---|
vector | <vector> | 动态数组(连续内存) | 随机访问迭代器 ✅ | ✅ 支持 sort(v.begin(),v.end()) | 随机访问快 [];尾部增删快,中间插入删除慢 常用:push_back / pop_back / size / clear |
list | <list> | 双向链表(非连续) | 双向迭代器 ❌ | ❌ 不能用std::sort,只能成员方法 lst.sort() | 任意位置插入删除O(1);不支持 [] 下标访问 常用:push_front/push_back / pop_front/pop_back / sort() / remove |
map | <map> | 红黑树(有序) | 双向迭代器 ❌ | ❌ 本身自动按key升序有序 | key唯一,自动排序;key不能修改 常用:insert / [] / find / erase |
stack | <stack> | 容器适配器(默认底层deque) | 无迭代器 | ❌ | 后进先出 LIFO;只能操作栈顶 接口:push / pop / top / empty |
queue | <queue> | 容器适配器(默认底层deque) | 无迭代器 | ❌ | 先进先出 FIFO;只能队首队尾 接口:push / pop / front / back / empty |
string | <string> | 动态字符数组 | 随机访问迭代器 ✅ | ✅ sort(s.begin(),s.end()) | 专门存字符串,支持 []、拼接+、substr、find、reverse |
sort(std::sort) | <algorithm> | 算法(快速排序改良,内省排序) | — | — | 全局排序函数,只接收随机访问迭代器 |
一句话重点区分(背诵版)
- ✅ 可以 std::sort:vector、string、array(随机访问迭代器)
- ❌ 不能 std::sort:list、map、stack、queue
- list:自带
.sort()成员排序 - map:天然有序,不需要sort
- stack / queue:适配器,不支持遍历迭代,不能排序
- list:自带
- stack / queue 是适配器,不是独立容器,只是包装别的容器
STL使用方式
下面这段验证代码,直接复制运行,会标注清楚哪些能用std::sort、哪些不行:
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
// 1. vector ✅ 支持 std::sort
vector<int> vec = {3,1,4,2};
sort(vec.begin(), vec.end());
cout << "vector sort ok: ";
for(auto x : vec) cout << x << " ";
cout << "\n";
// 2. string ✅ 支持 std::sort
string s = "dcba";
sort(s.begin(), s.end());
cout << "string sort ok: " << s << "\n";
// 3. list ❌ 不能std::sort,只能调用成员 .sort()
list<int> lst = {6,2,5,1};
lst.sort();
cout << "list .sort() ok: ";
for(auto x : lst) cout << x << " ";
cout << "\n";
// 4. map ❌ 本身自动有序,不需要sort
map<int, int> mp;
mp[3]=30; mp[1]=10; mp[2]=20;
cout << "map 天然有序: ";
for(auto &p : mp) cout << p.first << " ";
cout << "\n";
// 5. stack ❌ 没有迭代器,不能遍历、不能sort
stack<int> st;
st.push(5); st.push(1);
// 6. queue ❌ 没有迭代器,不能遍历、不能sort
queue<int> q;
q.push(9); q.push(4);
cout << "\n===总结===\n";
cout << "✅ std::sort:vector、string、array\n";
cout << "❌ list:lst.sort() 成员函数\n";
cout << "❌ map:自动有序\n";
cout << "❌ stack、queue:适配器,无迭代器,不可排序\n";
return 0;
}输出结果
vector sort ok: 1 2 3 4
string sort ok: abcd
list .sort() ok: 1 2 5 6
map 天然有序: 1 2 3
===总结===
✅ std::sort:vector、string、array
❌ list:lst.sort() 成员函数
❌ map:自动有序
❌ stack、queue:适配器,无迭代器,不可排序补充考点:
std::sort底层是内省排序,要求迭代器支持随机访问(+n、[]) list 双向迭代器不支持随机跳转,所以标准sort用不了,它自己实现了归并排序版本的.sort()
C++ sort 排序笔记(考研/笔试背诵版)
头文件:
#include <algorithm>✅ 前提:std::sort只支持随机访问迭代器(vector、string、普通数组) ❌ list/map/stack/queue 不能直接用 std::sort
一、sort 两个重载格式
// 方式1:默认升序,[first, last) 左闭右开区间
void sort(RandomAccessIterator first, RandomAccessIterator last);
// 方式2:自定义比较器comp
void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);重点:区间是左闭右开,
begin()包含,end()不包含。
1. 默认升序
vector<int> arr = {9, 6, 3, 8, 5, 2, 7, 4, 1, 0};
sort(arr.begin(), arr.end());2. 降序(内置仿函数 greater)
sort(arr.begin(), arr.end(), greater<int>());二、自定义比较函数 cmp(核心考点)
规则口诀
return a < b → 升序(从小到大)return a > b → 降序(从大到小)
一句话:返回 true 代表 a 应该排在 b 的前面
示例:int 降序
bool cmp(int num1, int num2)
{
return num1 > num2; // num1>num2 时,num1放前面,降序
}快速自测一下(检验你懂没懂)
bool cmp(int a,int b){
return a < b;
}这个是升序还是降序? (答案:升序,小在前)
bool cmp(int a,int b){
return a > b;
}(答案:降序,大在前) (和默认 sort 对照记忆)
sort 不加 cmp,默认就是less,等价于:
sort(v.begin(),v.end(),less<int>()); // 底层就是 return a < bgreater<int>() 等价于 return a > b
less:更少(更小)的放前面 greater:更大的放前面
三、自定义结构体/类多条件排序(高频大题)
示例类:
class Person{
public:
string name;
int age;
int height;
Person(string name, int age, int height){
this->name = name;
this->age = age;
this->height = height;
}
};示例1:优先年龄升序;年龄相等 → 身高降序
bool ComparePerson(Person &p1, Person &p2)
{
if(p1.age == p2.age)
{
return p1.height > p2.height;
}
else
{
return p1.age < p2.age;
}
}示例2:优先身高升序;身高相等 → 年龄降序(截图里的版本)
bool ComparePerson(Person &p1, Person &p2)
{
if(p1.height == p2.height)
{
return p1.age > p2.age;
}
else
{
return p1.height < p2.height;
}
}调用:
vector<Person> v;
// 插入数据...
sort(v.begin(), v.end(), ComparePerson);四、配套:重载 << 实现直接cout打印(方便调试)
class Person{
public:
string name;
int age;
int height;
Person(string name, int age, int height){
this->name = name;
this->age = age;
this->height = height;
}
// 友元声明,重载输出
friend ostream& operator << (ostream &os, Person &f);
};
ostream& operator << (ostream &os, Person &f)
{
os << "身高:" << f.height << " 年龄:" << f.age << " 姓名:" << f.name << endl;
return os;
}之后遍历可以直接写:
for(auto &x : v)
{
cout << x;
}五、整合【容器能不能sort】总回顾(和前面笔记合并)
| 容器 | 能否std::sort | 排序方式 |
|---|---|---|
| vector | ✅ | std::sort(begin,end,comp) |
| string | ✅ | std::sort(begin,end,comp) |
| list | ❌ | 只能成员函数 .sort(comp) |
| map | ❌ | 红黑树,key天然有序,不用排序 |
| stack / queue | ❌ | 适配器,无迭代器,不能遍历排序 |
六、易错坑总结(必背)
- sort 区间左闭右开,不要搞错边界;
- cmp 函数是 bool 返回值,不要写成 >=、<=(严格弱序,笔试坑);
- list 绝对不能写
sort(lst.begin(),lst.end()),编译报错; - greater<int>() 是仿函数,后面必须带括号;
- 多条件排序:先判断第一关键字,相等才进入第二关键字;
- 自定义类如果要直接cout,必须重载
operator<<,声明为friend。
七、完整可直接运行整合Demo(全部放一起)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Person{
public:
string name;
int age;
int height;
Person(string name, int age, int height){
this->name = name;
this->age = age;
this->height = height;
}
friend ostream& operator << (ostream &os, Person &f);
};
ostream& operator << (ostream &os, Person &f)
{
os << "身高:" << f.height << " 年龄:" << f.age << " 姓名:" << f.name;
return os;
}
// 排序规则:身高升序,身高相同则年龄降序
bool ComparePerson(Person &p1, Person &p2)
{
if(p1.height == p2.height)
{
return p1.age > p2.age;
}
return p1.height < p2.height;
}
int main()
{
vector<Person> v;
v.emplace_back("刘备",35,170);
v.emplace_back("关羽",45,179);
v.emplace_back("张飞",25,172);
v.emplace_back("赵云",39,172);
v.emplace_back("孙权",18,173);
v.emplace_back("关平",25,171);
sort(v.begin(), v.end(), ComparePerson);
for(auto &x : v)
{
cout << x << endl;
}
return 0;
}