内容有亿点多:smile:，如果看不完，可以收藏了慢慢看哦(doge)
@TOC
一、什么是容器？
二、STL 中各大容器的结构与分类
2.1 顺序性容器
2.1.1 什么是顺序性容器？
顺序性容器就是将一组具有相同类型的元素以严格的线性形式组织起来
2.1.2 有哪些顺序性容器？
这里给大家整理成了一个表格的形式，如下表所示:dog:
2.1.3 顺序性容器在什么场合使用？
一般大多数的题目都可以使用 vector 容器，除非有特定需求使用其他容器更加合理方便；
如果需要在一串数字的头尾进行操作，偏向 deque，对于较中间的元素操作，不推荐:elephant:；
对于中间的元素插入或删除，可采用 forward_list（单向链表）或 list（双向链表），不需要移动元素，只需改变相关结点的指针域即可；
2.2 关联式容器
2.2.1 什么是关联式容器？
关联式容器每一个元素都有一个键值（key），对于二元关联容器，还拥有实值（value）容器中的元素顺序不能由程序员来决定，有 set（集合）和 map（映射）这两大类，它们均是以 RB-Tree（red-black tree，红黑树）为底层架构。
2.2.2 有哪些关联式容器？
同样，以表格的形式呈现，如下表所示:cat:
2.2.3 关联式容器在什么场合使用？
如果只负责查找内容，具体到某个单位，使用场景比如对手机游戏的个人的计分的存储，可以使用 set 或 mutliset
如果需要同时放入容器的数据不止一个，并且是不同类型，比如一个为整型 int,一个为 string 字符串型，就可以考虑使用 map 或 mutlimap
2.3 容器适配器
2.3.1 什么是容器适配器？
容器适配器是一个封装了序列容器的一个==类模板===，它在一般的序列容器的基础上提供了一些不同的功能。之所以称为容器适配器，是因为它是适配容器来提供其它不一样的功能。通过对应的容器和成员函数来实现我们需要的功能
2.3.2 有哪些容器适配器？
不必多说，看表:wolf:
2.3.3 容器适配器在什么场合使用？
对于 stack 堆栈，在我们日常生活中类似于坐地铁、电梯；
对于 deque 队列，在我们日常生活中类似于排队打饭；
对于 pirority_queue，因为其本质是堆，可以考虑解决一些贪心问题；
三、具体容器的深入剖析与详解
3.1.顺序性容器
3.1.1 vector（向量）
1）基本概念和介绍
2）头文件
3）内部结构
4）常用 API 操作
先说一下什么是 API，API 就是==应用程序编程接口==（Application Programming Interface），说得更加通俗易懂一些，别人编译好的程序，提供给你使用，就叫做 API。你使用了别人代码（或者程序）中的某个函数、类、对象，就叫做使用了某个 API。
void PrintVector(vector<int>& v){ for (auto x : v) { cout << x << " "; } cout << endl;}
复制代码
接下来回归正题 :
① 构造函数常见的构造方式有四种，一般我们会前两种就可以
vector<int> v1; //1.默认构造，无参构造
for (int i = 0; i < 10; ++i) { v1.push_back(i); } PrintVector(v1);
//2.利用区间方式构造 vector<int> v2(v1.begin(), v1.end()); PrintVector(v2);
//3.n个element方式构造 vector<int> v3(10, 100); //10个100 PrintVector(v3);
//4.拷贝构造 vector<int> v4(v3); PrintVector(v4);
复制代码
② 赋值操作赋值的话可以使用 assign()函数，也可以使用其他方式
//直接赋值 vector<int> v2; v2 = v1;
//assign赋值 vector<int> v3; v3.assign(v1.begin(), v1.end());
//n个element赋值 vector<int> v4; v4.assign(10, 100);
复制代码
③ 插入和删除插入主要是使用==push_back()==，也可使用 insert()；删除操作主要是==pop_back()==，也可使用 erase()
vector<int> v; //尾插 v.push_back(10); v.push_back(20); v.push_back(30); v.push_back(40); v.push_back(50);
PrintVector(v);
//尾删 v.pop_back(); PrintVector(v);
//插入 - 提供迭代器 v.insert(v.begin(), 100); PrintVector(v);
//重载 v.insert(v.begin(), 2, 100); PrintVector(v);
//删除 - 提供迭代器 v.erase(v.begin()); PrintVector(v);
//重载 v.erase(v.begin(), v.end()); //相当于清空操作 PrintVector(v);
v.clear(); //清空容器中所有元素 PrintVector(v);
复制代码
④ 容量和大小对于容量用的是 capacity()，对于大小是 size()，当然你也可以用 resize()来改变其大小，不够在此之前都需用 empty()这个函数来判断一下容器是否为空；
vector<int> v;
for (int i = 0; i < 10; ++i) { v.push_back(i); } PrintVector(v);
if (v.empty()) { cout << "vector容器为空" << endl; } else { cout << "vector容器不为空" << endl; cout << "vector容器的容量为：" << v.capacity() << endl; cout << "vector容器的大小为：" << v.size()<< endl; }
//重新指定大小 - 变大// v.resize(15); v.resize(15,10); //重载 PrintVector(v);
//重新指定大小 - 变小 v.resize(5); PrintVector(v); //超过部分将会删除
复制代码
3.1.2 deque（双端队列）
1）基本概念和介绍
deque 容器为双端队列，可以对其两段的数据进行操作，因为它没有 capacity 属性，因此不会像 vector 那样”旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”，因此，deque 没有必须要提供所谓的空间保留(reserve)功能。
2）头文件
3）内部结构
4）常用 API 操作① 构造函数 deque 的构造函数与 vector 类似，也是四种常见的方式
deque<int> d1;
for (int i = 0; i < 10; ++i) { d1.push_back(i); } deque<int> d2(d1); deque<int> d3(10, 100); deque<int> d4; d4 = d3;
复制代码
② 赋值操作
deque<int> d1;
for (int i = 0; i < 10; ++i) { d1.push_back(i); }
deque<int> d2; d2 = d1;
deque<int> d3; d3.assign(d1.begin(), d1.end());//将[beg, end)区间中的数据拷贝赋值给本身
deque<int> d4; d4.assign(10, 100);
复制代码
③ 大小和容量上文提到，deque 容器无 capacity()函数
if (d1.empty()) { cout << "deque容器为空" << endl; } else { cout << "deque容器不为空" << endl; cout << "deque容器的大小为：" << d1.size() << endl; //deque容器无capacity - 容量 }
//改变大小 //d1.resize(15); d1.resize(15,1); print(d1);
d1.resize(5); print(d1);
复制代码
③ ==插入和删除==对于双端队列来说，插入和删除时一个亮眼的地方，因为首尾均可操作，有头插 push_front()，头删 pop_front()，尾插 push_back()，尾删 pop_back()，以及 inset()插入和 erase()删除
//首尾操作 deque<int> d;
d.push_back(10); d.push_back(20); //尾插
d.push_front(100); d.push_front(200); //头插
print(d); //200 100 10 20
d.pop_back(); //尾删 d.pop_front(); //头删 print(d); //100 10
复制代码
运行结果：
//插入操作deque<int> d;
d.push_back(10); d.push_back(20); //尾插
d.push_front(100); d.push_front(200); //头插
print(d); //200 100 10 20
d.insert(d.begin(), 100); //100 200 100 10 20 print(d);
d.insert(d.begin(), 2, 900); //900 900 100 200 100 10 20 print(d);
复制代码
运行结果：
//删除操作 deque<int> d;
d.push_back(10); d.push_back(20); //尾插
d.push_front(100); d.push_front(200); //头插
print(d); //200 100 10 20
deque<int>::iterator it = d.begin(); it++; //迭代器往后偏移一个位置 d.erase(it); print(d); //200 10 20
d.erase(d.begin(), d.end()); print(d);
d.clear(); print(d);
复制代码
运行结果：
④ 数据存取
这里主要是区别[]方式和 at()函数的访问情况
deque<int> d;
d.push_back(10); d.push_back(20); d.push_back(30); d.push_front(100); d.push_front(200); d.push_front(300);
//通过[]方式访问 for (int i = 0; i < d.size(); ++i) { cout << d[i] << " "; } cout << endl;
//通过at访问 for (int i = 0; i < d.size(); ++i) { cout << d.at(i)<< " "; } cout << endl; cout << "第一个元素为：" << d.front() << endl; cout << "最后一个元素为：" << d.back() << endl;
复制代码
3.1.3 list（列表[双向循环链表]）
1）头文件
2）内部结构
3）常用 API 操作
这里的一些常规操作与前文类似，因此不做过多展示，只普通地做一些用法讲解 ① 构造函数
list(beg,end);//构造函数将[beg, end)区间中的元素拷贝给本身。list(n,elem);//构造函数将n个elem拷贝给本身。
复制代码
② 赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。assign(n, elem);//将n个elem拷贝赋值给本身。swap(lst);//使用之后实现将lst与本身的元素互换。
复制代码
③ 插入和删除操作
push_back(elem);//在容器尾部加入一个元素pop_back();//删除容器中最后一个元素push_front(elem);//在容器开头插入一个元素pop_front();//从容器开头移除第一个元素insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置。insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。clear();//移除容器的所有数据erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。erase(pos);//删除pos位置的数据，返回下一个数据的位置。remove(elem);//删除容器中所有与elem值匹配的元素。
复制代码
3.1.4 forword_list（单向链表）
1）基本概念和介绍
对于 forword_list 单向链表，虽然它具有和 list 容器相同的特性，擅长在序列的任何位置进行插入元素或删除元素的操作，但对于访问存储的元素，没有其它容器（如 array、vector）的效率高，以及由于单链表没有双向链表那样灵活，因此相比 list 容器，单链表只能==从前向后遍历==，而不支持反向遍历
2）头文件
3）常用 API 操作
begin() //返回一个前向迭代器，其指向容器中第一个元素的位置。 end() //返回一个前向迭代器，其指向容器中最后一个元素之后的位置。assign() //用新元素替换容器中原有内容。push_front() //在容器头部插入一个元素。pop_front() //删除容器头部的一个元素。swap() //交换两个容器中的元素，必须保证这两个容器中存储的元素类型是相同的。remove(val) //删除容器中所有等于 val 的元素sort() //通过更改容器中元素的位置，将它们进行排序。
复制代码
3.1.5 array（数组）
1）基本概念和介绍
array 是 C++11 中新增的容器，它与其他容器不同的是，它的大小是固定的，无法动态扩展或收缩，只允许访问或者替换存储的元素。
2）头文件
3）案例讲解下面讲解一个简单的案例从这里可以看出，array 的形参列表是需要两个参数，第一个是所要创建的元素的数据类型，第二个就是数组的元素个数，这和直接创建一个 a 数组其实很类似，比方 a[5]={1,2,3,4,5}，也是同样的原理，这里的auto i 是一个变量，循环时每次获得一次容器 a 中的变量，相当于省去 int i 直接循环全部内容,也就相当于 for (array<int, 5>::iterator it = a.begin(); it != a.end(); ++it)
#include <array>#include <iostream>using namespace std;
int main(){ array<int,5> a = {1,2,3,4,5}; for(auto i:a) { std::cout << "value is " << i << std::endl; } return 0;}
复制代码
这里是 array 的其他 API 操作和迭代器，感兴趣的小伙伴可以了解一下
3.2 关联式容器
3.2.1 set/multiset（集合/多重集合）
1）基本概念和介绍
有关 set 容器，它在用 insert()函数插入之后会自行被排序，默认是升序，但不可重复插入，即不能有重复的 key(键值)，对于 multiset，就可以实施多个键值的插入操作，这两个容器和 map 不一样，它们是简单关联容器，其参数类型只有一个，所以它的元素既是键值(value)又是实值(value)。
2）头文件
注：set/multiset 一样，都是使用此头文件
3）常用 API 操作
① 查找和统计操作我们可以看到，在 set 容器中，你可以通过相关的迭代器去访问容器中相应的元素，利用 find()函数，也可以用 count()函数去统计相关元素在容器中出现了几次；这是它们的==相关语法==:
set<int> s1;
s1.insert(10); s1.insert(60); s1.insert(30); s1.insert(20); s1.insert(90); s1.insert(70);
print(s1);
//查找 set<int>::iterator pos = s1.find(300); if (pos != s1.end()) { cout << "找到了，为：" << *pos << endl; } else { cout << "没找到" << endl; }
//统计 set<int> s2;
s2.insert(10); s2.insert(60); s2.insert(30); s2.insert(60); s2.insert(90); s2.insert(10);
print(s2);
int num1 = s1.count(30); cout << "num1=" << num1 << endl;
int num2 = s2.count(10); //即使插入了两个元素10，因为集合元素的互异性，count统计之后依旧只有一个 cout << "num2=" << num2 << endl;
复制代码
运行结果：
接下来讲讲==pair 对组==的概念
1.定义一般我们这里使用第一个就可以了
pair<int, double> p1; //使用默认构造函数 pair<int, double> p2(1, 2.4); //用给定值初始化 pair<int, double> p3(p2); //拷贝构造函数
复制代码
2.访问访问两个元素（通过 first 和 second）：
pair<int, double> p1; //使用默认构造函数 p1.first = 1; p1.second = 2.5; cout << p1.first << ' ' << p1.second << endl;
复制代码
3.赋值 1）利用 make_pair
pair<int, double> p1; p1 = make_pair(1, 1.2);
复制代码
2）变量间赋值：
pair<int, double> p1(1, 1.2); pair<int, double> p2 = p1;
复制代码
4.应用像这里就可以利用 first 和 second 来访问对组中的两个元素
pair<string, int> p("Tom", 20);cout << "姓名：" << p.first << "\t年龄：" << p.second << endl;
pair<string, int> p2 = make_pair("Jerry", 25);cout << "姓名：" << p2.first << "\t年龄：" << p2.second << endl;
复制代码
不仅如此，对组还可以放入 queue（队列）然后配合BFS（广度优先搜索）来解题，感兴趣的小伙伴可以去了解一下；例：
queue<pair<int,int> >q;q.push(make_pair(x,y));
复制代码
然后这里再说一下==仿函数==的用法和实例
仿函数，又叫做函数对象或者智能函数，他相当于一个类一样，你需要==重载 operator()运算符==，因为调用仿函数，实际上就是通过类对象调用重载后的 operator() 运算符.
仿函数一般有两种使用方法：（1）一个办法就是先将该“操作”设计为一个函数，再将函数指针当做算法的一个参数。上面的实例就是该做法；（2）将该“操作”设计为一个仿函数（就语言层面而言是个 class），再以该仿函数产生一个对象，并以此对象作为算法的一个参数。
可以看出第二种方法会更高效可靠一些，第一种方法的扩展性较差，这里给出一个简洁的例子：
#include <iostream>#include <set>#include "print.h"using namespace std;
class MyCompare{
public: //仿函数 bool operator()(int v1, int v2) const { return v1 > v2; //降序排列 }};int main(){ set<int> s1;
s1.insert(10); s1.insert(60); s1.insert(30); s1.insert(20); s1.insert(90); s1.insert(70);
print(s1); //默认升序
//降序显示
set<int, MyCompare> s2; s2.insert(10); s2.insert(20); s2.insert(90); s2.insert(70); for (set<int, MyCompare>::iterator it = s2.begin(); it != s2.end(); ++it) { cout << *it << " "; } cout << endl;}
复制代码
运行结果：
上述例子是一个内置数据类型，其实仿函数也可以写成自定义数据类型，比如定义一个 Person 类，有年龄和身高两个属性，通过仿函数传入对应的类对象，也可以进行升序或降序的排列,大概类似于这样，这里的 const 一定要加，否则会报错的，因为设置成常成员函数，数据成员就不会被修改：
class MyCompare {
public: bool operator()(const Person &p1,const Person &p2) const { return p1.m_age > p2.m_age; }};
复制代码
对于仿函数，其实它和回调函数挺像的，回调函数是通过函数指针来进行传参，然后实现的一系列操作，有兴趣的小伙伴可以深入了解一下：回调函数与仿函数
3.2.2 map/multimap（映射/多重映射）
1）基本概念和介绍
map 的所有元素是 pair 对组，同时拥有键值（key）和实值（value），所有元素都会根据键值来自动排序，当对它的容器元素进行新增操作或者删除操作时，操作之前的所有迭代器，在操作完成之后依然有效，map 的使用率还是挺高的，仅此于 vector 和 list
2）头文件
注：同理，map/multimap 一样，都是使用此头文件
3）常用 API 操作**① **构造和赋值可以看出，对于 map 容器，使用其 insert()进行插入就需要使用 pair 对组来实现，不然是插入不进去了，要分别传入它的键值和实值，这里我不是按照键值的顺序插入，但是看运行结果，最后显示出来的还是会按照顺序排列
map<int, int> m; //键值对
//第一个：key（键值） 第二个：value（实值） m.insert(pair<int, int>(1, 10)); m.insert(pair<int, int>(3, 30)); m.insert(pair<int, int>(2, 20)); //依旧会按照顺序排列 m.insert(pair<int, int>(4, 40)); m.insert(pair<int, int>(5, 30));
print(m);
//拷贝构造 map<int, int> m2(m); print(m2);
//赋值 map<int, int> m3; m3 = m2; print(m3);
复制代码
运行结果：
②大小和交换从运行结果可以看出，即使我插入了相同键值对应的实值，但是由于键值的重复，因此 80 这个数字是放不进容器的
//大小 map<int, int> m;
//第一个：key（键值） 第二个：value（实值） m.insert(pair<int, int>(1, 10)); m.insert(pair<int, int>(3, 30)); m.insert(pair<int, int>(2, 20)); //依旧会按照顺序排列 m.insert(pair<int, int>(4, 40)); m.insert(pair<int, int>(4, 80)); //无效
print(m);
if (m.empty()) { cout << "map容器为空" << endl; } else { cout << "map容器不为空" << endl; cout << "map容器的大小为：" << m.size() << endl; }
复制代码
运行结果：
这里是使用到了 swap()函数，对两个 map 容器中的值进行交换
//交换 map<int, int> m1;
//第一个：key（键值） 第二个：value（实值） m1.insert(pair<int, int>(1, 10)); m1.insert(pair<int, int>(2, 20)); m1.insert(pair<int, int>(3, 30));
map<int, int> m2;
//第一个：key（键值） 第二个：value（实值） m2.insert(pair<int, int>(4, 100)); m2.insert(pair<int, int>(5, 200)); m2.insert(pair<int, int>(6, 300));
cout << "交换前" << endl; print(m1); print(m2);
m1.swap(m2); cout << "交换后" << endl; cout << "---------------------------" << endl; print(m1); print(m2);
复制代码
运行结果：
③查找和统计对于 find()查找函数，在 map 中可以利用键值来查找相应的实值，比如这里 find(3),显示的便是对应的实值 30；而对于 count 统计也是同理，count(3)的意思是统计键值为 3 的数有多少个，但是对于 map 容器，一定是 0 或者 1。因为对于重复的键值是插不进去的，可对于 mutilmap，利用 count()函数去统计的话就可能是>1 的数量
map<int, int> m;
m.insert(make_pair(1, 10)); m.insert(make_pair(2, 20)); m.insert(make_pair(3, 30)); m.insert(make_pair(3, 40));
print(m);
map<int, int>::iterator pos = m.find(3); if (pos!=m.end()) { cout << "找到到元素了，key=" << pos->first << " value=" << pos->second << endl; } else { cout << "没有找到改元素" << endl; }
int num = m.count(3); cout << "num=" << num << endl; //map不允许插入重复元素，对于count统计而言，要么为0，要么为1 //mutilmap的count统计可能>1
复制代码
运行结果：
④插入和删除
对于插入 insert()，有着四种方式可以选择，一般我们记住前两种就可以了，第三种需要用迭代器来访问，第四种的话不太建议，因为如果按照这样方式插入，编译器会按照你之前没有的那个数创建一个新的对组出来，就像运行结果一样，我没有插入键值 key 为 5 的实值，但是默认显示的是 0，这里要注意，一般这种方法可以通过 key 来访问 value，这是可以的，也比较方便。
对于删除 erase()，也是可以通过它的 key 值来删除对应的 value 值，这在实际的开发中还是会起到一定的作用，不需要一个个去查找
map<int, int> m;
//插入
//① m.insert(pair<int, int>(1, 10));
//② m.insert(make_pair(2, 20));
//③ m.insert(map<int,int>::value_type(3,30));
//④ m[4] = 40; //[]不建议插入，可以用key来访问value cout << m[5] << endl; print(m);
//删除 m.erase(m.begin()); print(m);
m.erase(3); //根据键值key来删除 print(m);
m.erase(m.begin(), m.end()); print(m);
m.clear(); print(m);
复制代码
运行结果：
3.3 容器适配器
3.3.1 stack（堆栈）
1）基本概念和介绍
stack 为堆栈，上文提到过，其内部元素都是需要==先进后出==（FILO）的，也就是说只有栈顶的元素 top 才可以被访问到
2）头文件
3）内部结构
3）常用 API 操作
stack<int> s;
s.push(10); s.push(20); s.push(30); s.push(40); //入栈
cout<<"栈的大小\t栈顶元素" << endl; while (!s.empty()) { cout << s.size() <<"\t\t" << s.top() << endl;
s.pop(); //出栈 }
cout << "出栈后的大小为：" << s.size() << endl;}
复制代码
运行结果：
3.3.2 queue（队列）
1）基本概念和介绍
queue 为队列，它和 stack 堆栈的正好相反，栈是先进后出，而队列则是==先进先出==(FIFO)。看到这里是不是想起了我们前面学过的一个顺序性容器 deque（双端队列），下面来区分一下他们之间的不同之处：
1、==queue==可以访问两端但是只能修改队头，而==deque==可以访问两端并且可以在队首和队尾删除和插入元素 2、==deque==可以从两端入队，但是==queue==只能从队尾入队，3、对于弹出队内元素，==deque==拥有 pop_front(删除队头元素)以及 pop_back(删除队尾元素)
2）头文件
3）内部结构
3）常用 API 操作
对于队列的 API 操作，也是和堆栈一样，并不是很多，这里我们举一个例子来说明一下几个常用函数
#include <iostream>#include <queue>#include <string>using namespace std;
class Person {
public: Person(string name, int age) { this->m_name = name; this->m_age = age; }
string m_name; int m_age;};void test(){ queue<Person> q;
//构建数据 Person p1("唐僧", 100); Person p2("孙悟空", 200); Person p3("猪八戒", 300); Person p4("沙僧", 400);
//入队 q.push(p1); q.push(p2); q.push(p3); q.push(p4);
//访问队列元素 cout << "队列大小\t队头元素\t\t队尾元素" << endl; while (!q.empty()) { cout << q.size()<<"\t\t"; cout << q.front().m_name<<"\t"; cout<< q.front().m_age << "\t\t"; cout << q.back().m_name << "\t"; cout << q.back().m_age << endl;
//出队 q.pop(); } cout << "均出队后的队列元素个数为：" << q.size();}int main(void) { test(); return 0;}
复制代码
运行结果：
讲解：
3.3.3 pirority_queue（优先队列）
1）基本概念和介绍
所谓优先队列，就是我们可以自定义中数据的优先级, 让优先级高的排在队列前面,优先出队
2）头文件
注：对于优先队列，它的头文件和队列是一样的 3）参数定义及简单介绍
priority_queue<Type, Container, Functional>
复制代码
==Type== 就是数据类型;==Container== 就是容器类型;==Functional== 就是比较的方式;这里是两种优先队列的方式：对于最后的 functional,这也是一个模板头文件，这里的 greater 是大的，也就是呈上升，less 是少的，也就是呈下降，自然对应的就是升序队列和降序队列
//升序队列（小顶堆）- 优先输出最小的priority_queue <int,vector<int>,greater<int> > q;//降序队列（大顶堆）- 优先输出最大的[默认]priority_queue <int,vector<int>,less<int> >q;
复制代码
我们来看一下具体实例：
#include <iostream>#include <queue>using namespace std;
int main(void){ priority_queue<int> q;
q.push(9); q.push(2); q.push(7); q.push(3); q.push(-8); q.push(1);
while (!q.empty()) { cout << q.top() << " "; q.pop(); } cout<<endl; return 0;}
复制代码
运行结果：
可以看出，默认就是大顶堆，优先输出最大的元素
priority_queue<int,vector<int>,greater<int>> q;
q.push(9); q.push(2); q.push(7); q.push(3); q.push(-8); q.push(1);
复制代码
运行结果：
从这里可以看出修改内部参数之后呈现出的就是一个小顶堆，也就是优先输出最小的元素
小结可以看出优先队列，它的功能还是很强大的，在实现算法的时候，你可以替代快排[快速排序 sort() ],因为快排虽然很快，但是稳定性不是很好，时间复杂度也是会到达 O(nlogn),但这里的复杂度只有 O(n),当然具体案例具体分析；
四、利用容器实现的具体案例
看到这里，相信您对 STL 中的容器已经有了一个完整的概念，但光是了解并不够，我们还要将其放到具体的问题中，从中看看容器起到哪些关键性的作用
4.1 评委打分
1、案例描述
2、案例分析与思路罗列==本题主要是运用了 vector 容器和 deque 容器==①首先可以创建一个 Person 类，将五名选手存放到一个 vector 容器中；②接着就是评委的打分，因为我们要取出最高分和最低分，所以可以将评委的分数存放到 deque 容器中，利用 pop_front()和 pop_back()来去掉最高分和最低分；③在取出最高最低分前需要对每位选手的十个分数进行排序④累加和求平均分并输出
2、具体代码实现与讲解下面来分开讲解三个重要的主体函数①选手的创建
class Person{public: Person(string name, int score) { this->m_name = name; this->m_score = score; } string m_name; int m_score;};
复制代码
void CreaePlayer(vector<Person> &v){ string nameSeed = "ABCDE"; int score = 0; for (int i = 0; i < 5; ++i) { string name = "选手"; name+=nameSeed[i]; //字符串拼接
Person p(name, score);
v.push_back(p); }}
复制代码
//创建五个选手 vector<Person> player; //存放选手容器 CreaePlayer(player);
复制代码
详细讲解：
void SetScore(vector<Person>& v){ int avg = 0; srand((unsigned int)time(NULL)); //随机化种子 for (vector<Person>::iterator it = v.begin(); it != v.end(); ++it) //每位选手的外层遍历（5） { //将评委的打分放入deque容器 deque<int> d; for (int i = 0; i < 10; ++i) { int score = rand() % 41 + 60; //评委随机打分40~60 d.push_back(score); }
//观察评委打分情况 cout<< it->m_name << "的十位评委打分为：" << endl; for (deque<int>::iterator dit = d.begin(); dit != d.end(); ++dit) //每位评委的内层遍历（10） { cout << *dit << " "; } cout << endl; //排序 sort(d.begin(), d.end());
//去除最高分和最低分 d.pop_back(); d.pop_front();
//取平均数 int sum = 0; //放入循环内部，累加完一个玩家的十位评委的总分置零重新记数 for (deque<int>::iterator dit = d.begin(); dit != d.end(); ++dit) //每位评委的内层遍历（10） { sum += *dit; //累加每位玩家十位评委的打分 } cout << "总分为：" << sum << " "; cout << endl<<endl; avg = sum / d.size(); //计算每一位玩家的平均分
it->m_score = avg; }}
复制代码
详细讲解：
对于十位评委的打分，是将其放入 deque 容器中，这里为了方便，直接通过rand()随机数来生成，不过这个函数大家记得包含"ctime"的头文件，在 C 语言中直接写"time"即可，以及 srand()这个函数是一个随机化种子，可以保证每次产生的随机数都不同，然后中途我是通过迭代器的访问来观察每位选手的十位评委打分情况；
接着就是通过 sort()快速排序来实现十位评委的打分排序，以此来去除最高分和最低分，这里大家记得要包含算法头文件"algorithm",因为它是里面的一种算法，之后也会出关于 STL 算法的讲解，记得随时关注哦，然后就是计算每一位选手的总分以及平均分，大家看代码即可；这里是运行结果：
③平均分的显示
void ShowScore(vector<Person>& v){ for (vector<Person>::iterator it = v.begin(); it != v.end(); ++it) { cout << "姓名：" << it->m_name << " 得分成绩： " << it->m_score; cout << endl; } cout << endl;}
复制代码
详细讲解：
整体代码展示
#include <iostream>#include <string>#include <vector>#include <deque>#include <algorithm>#include <ctime>using namespace std;
class Person{public: Person(string name, int score) { this->m_name = name; this->m_score = score; } string m_name; int m_score;};
void CreaePlayer(vector<Person> &v){ string nameSeed = "ABCDE"; int score = 0; for (int i = 0; i < 5; ++i) { string name = "选手"; name+=nameSeed[i]; //字符串拼接
Person p(name, score);
v.push_back(p); }}
void SetScore(vector<Person>& v){ int avg = 0; srand((unsigned int)time(NULL)); //随机化种子 for (vector<Person>::iterator it = v.begin(); it != v.end(); ++it) //每位选手的外层遍历（5） { //将评委的打分放入deque容器 deque<int> d; for (int i = 0; i < 10; ++i) { int score = rand() % 41 + 60; //评委随机打分40~60 d.push_back(score); }
//观察评委打分情况 cout<< it->m_name << "的十位评委打分为：" << endl; for (deque<int>::iterator dit = d.begin(); dit != d.end(); ++dit) //每位评委的内层遍历（10） { cout << *dit << " "; } cout << endl; //排序 sort(d.begin(), d.end());
//去除最高分和最低分 d.pop_back(); d.pop_front();
//取平均数 int sum = 0; //放入循环内部，累加完一个玩家的十位评委的总分置零重新记数 for (deque<int>::iterator dit = d.begin(); dit != d.end(); ++dit) //每位评委的内层遍历（10） { sum += *dit; //累加每位玩家十位评委的打分 } cout << "总分为：" << sum << " "; cout << endl << endl; avg = sum / d.size(); //计算每一位玩家的平均分
it->m_score = avg; }}
void ShowScore(vector<Person>& v){ for (vector<Person>::iterator it = v.begin(); it != v.end(); ++it) { cout << "姓名：" << it->m_name << " 得分成绩： " << it->m_score; cout << endl; } cout << endl;}void test1(){ //创建五个选手 vector<Person> player; //存放选手容器 CreaePlayer(player);
//初始化测试 /*for (vector<Person>::iterator it = player.begin(); it != player.end(); ++it) { cout << "姓名：" << it->m_name << " 成绩为： " << it->m_score; cout << endl; }*/ cout << endl; //给五个选手打分 SetScore(player);
//显示五位选手的平均分 ShowScore(player);}int main(void){ test1(); return 0;}
复制代码
运行结果就是上述的拼接，就不展示，主要是太大了:flushed:
4.2 员工分组
1、案例描述
2、案例分析与思路罗列==本题主要是运用了 vector 容器和 multimap 容器==①首先依旧创建一个 Person 类，将十个员工存放到一个 vector 容器中；②遍历 vector 容器，取出每个员工，对他们进行随机分组；③分组之后，将部门编号作为 key(键值)，将员工的部门工作作为 value(实值)，放到 multimap 容器中；④分部门显示员工信息；
2、具体代码实现与讲解依旧是分开讲解三个重要的主体函数①员工的创建
class Person {public: string m_name; int m_salary;};
复制代码
void CreateWorker(vector<Person>& v){ string NameSeed = "ABCDEFGHIJ"; for (int i = 0; i < 10; ++i) { //编号 Person p; p.m_name = "员工"; p.m_name += NameSeed[i]; //薪水 p.m_salary = rand() % 10000 + 10000; //10000~19999
v.push_back(p); }}
复制代码
vector<Person> vWorker;
//创建10个员工CreateWorker(vWorker);
复制代码
详细讲解：
②员工的分组
void SetGroup(vector<Person>& v, multimap<int, Person>& m){ for (vector<Person>::iterator it = v.begin(); it != v.end(); ++it) { //随机化三个部门 int dep = rand() % 3; //0~2
//key：部门 value：员工 m.insert(pair<int, Person>(dep, *it)); //将十个员工放入三个部门 }}
复制代码
//员工分组 multimap<int,Person> mWorker; SetGroup(vWorker, mWorker);
复制代码
详细讲解：
②员工信息的显示由于类似，这里先只给出策划部的代码，另两个部门见下方整体代码展示
#define CH 0 //策划部#define MS 1 //美术部#define YF 2 //研发部
复制代码
void ShowGroup(multimap<int, Person>& m){ //策划部（0） A B C int count1 = m.count(CH); // 统计策划部的人数 multimap<int,Person>::iterator pos=m.find(CH); //查找
cout << "策划部" << endl; for (int index = 0; pos != m.end() && index < count1; ++pos,index++) { cout << "编号：" << pos->second.m_name<< "\t薪水：" << pos->second.m_salary << endl; } cout << "---------------------------------" << endl;}
复制代码
详细讲解：
讲一下这里为什么要用 multimap 而不用 map 呢，因为每个员工的部门是随机产生的，所以 A~J 有可能就在一个部门里，这就需要用到 multimap 中运行多键值插入的操作。来看函数体，这里是用到了 count()操作去统计这个部门有多少人数，然后用 find()去查找属于这个部门的有哪些人，find()它的返回结果是一个迭代器，所以用一个专属的迭代器去接受它的值，最后是通过一层 for 循环来，遍历统计并且输出每个员工的信息。
这里的 pos->second.m_name 便是这个位置上的员工通过 multimap 容器中的第二个属性参数信息也就是 second，这样就完全找到了这个员工.m_name 可以访问其姓名，.m_salary 便可以访问其工资运行结果:
整体代码展示
#include <iostream>#include <vector>#include <map>#include <ctime>#include <iterator>#include <string>using namespace std;
#define CH 0 //策划部#define MS 1 //美术部#define YF 2 //研发部
class Person {
public: string m_name; int m_salary;};
void CreateWorker(vector<Person>& v){ string NameSeed = "ABCDEFGHIJ"; for (int i = 0; i < 10; ++i) { //编号 Person p; p.m_name = "员工"; p.m_name += NameSeed[i]; //薪水 p.m_salary = rand() % 10000 + 10000; //10000~19999
v.push_back(p); }}
void SetGroup(vector<Person>& v, multimap<int, Person>& m){ for (vector<Person>::iterator it = v.begin(); it != v.end(); ++it) { //随机化三个部门 int dep = rand() % 3; //0~2
//key：部门 value：员工 m.insert(pair<int, Person>(dep, *it)); //将十个员工放入三个部门 }}
void ShowGroup(multimap<int, Person>& m){
//策划部（0） A B C int count1 = m.count(CH); // 统计策划部的人数 multimap<int,Person>::iterator pos=m.find(CH); //查找
cout << "策划部" << endl; for (int index = 0; pos != m.end() && index < count1; ++pos,index++) { cout << "编号：" << pos->second.m_name<< "\t薪水：" << pos->second.m_salary << endl; } cout << "---------------------------------" << endl;
//美术部（1） D E F int count2 = m.count(MS); // 统计美术部的人数 pos = m.find(MS); //查找
cout << "美术部" << endl; for (int index = 0; pos != m.end() && index < count2; ++pos,index++) { cout << "编号：" << pos->second.m_name << "\t薪水：" << pos->second.m_salary << endl; } cout << "---------------------------------" << endl;
//研发部（2） G H I J int count3 = m.count(YF); // 统计美术部的人数 pos = m.find(YF); //查找
cout << "研发部" << endl; for (int index = 0; pos != m.end() && index < count3; ++pos,index++) { cout << "编号：" << pos->second.m_name << "\t薪水：" << pos->second.m_salary << endl; } cout << "---------------------------------" << endl;
}void test(){ srand((unsigned int)time(NULL)); vector<Person> vWorker;
//创建10个员工 CreateWorker(vWorker);
//初始化测试 /*for (vector<Person>::iterator it = vWorker.begin(); it != vWorker.end(); ++it) { cout << "编号：" << it->m_name << "\t薪水：" << it->m_salary << endl; } cout << "---------------------------------" << endl;*/
//员工分组 multimap<int,Person> mWorker; SetGroup(vWorker, mWorker);
//显示员工分组 ShowGroup(mWorker);}int main(void){ test(); return 0;}
复制代码
五、总结
最后，感谢您对于本文的阅读，如有问题请于评论区留言:grin:
评论