机试小课堂丨 C++ STL容器进阶，“标准模板库”新人上手必学！
【声明：本文为原创文章,未经同意,严禁转载和抄袭,违者将追究其法律责任】
/ 写在前面的话 /
苏世机试小课堂，考研机试不再慌！
公主号：苏世学社考研 苏世计算机考研
STL是什么？
STL(Standard Template Library)，中文翻译成“标准模板库”或者“泛型库”，包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法，并且做到了数据结构和算法的分离，是 C++ 提供的一个基础模板的集合，用于完成输入/输出、数学计算等功能，高度体现了软件的复用性。
STL是C++ 程序库的重要组成部分，已完全被内置到支持 C++ 的编译器中，无需额外安装。从广义上讲STL代码分为三类：container（容器）、iterator（迭代器）和algorithm（算法）， 位于各个 C++ 的头文件中，以源代码的形式提供。
学STL能干什么？
STL起到了简化作用，可以直接调用别人的代码，提高代码的开发效率！
STL常用内容介绍
1
容器(Container)
容器(Container)，是用来管理某一类对象的集合，是一种数据结构，如vector、list、deque、set/multiset、map/multimap等。
1.1 vector
vector（向量）是一个封装了动态大小数组的顺序容器，可以随机存取元素，也能够存放任意类型。元素按照严格的线性顺序排序，可以通过元素在序列中的位置访问对应的元素。也支持对序列中的元素快速直接访问，使用一个内存分配器对象来动态处理它的存储需求。
常用方法：
size() 返回向量大小
max_size() 返回向量最大容量
resize() 更改向量大小
capacity() 真实大小
empty() 判空，如果是空，返回true
push_back() 末尾添加元素
pop_back() 末尾删除元素
insert() 任意位置插入元素
erase() 任意位置删除元素
swap() 交换两个向量的元素
clear() 清空向量元素
begin() 指向向量第一个元素
end() 指向向量最后一个元素的下一个位置
front() 访问第一个元素
back() 访问最后一个元素
参考代码和运行结果：
1.2 list
list和vector容器都是序列式容器，list是一个由它的数据元素通过链表指针串连成逻辑意义的环状双向链表，所以只用一个指针就可以完整实现。
常用方法：
push_front(x) 把元素x插入链表头部
push_back(x) 把元素x插入链表尾部
pop_front() 弹出双向队列的第一个元素
pop_back() 删除双向队列的最后一个元素
begin() 返回list中第一个元素的迭代器
end() 返回list中最后一个元素的下一个位置
clear() 清空list中的所有元素
empty() 利用empty() 判断list是否为空
front() 获得list容器中的头部元素
back() 获得list容器的最后一个元素
resize(n) 调整list的长度为只容纳n个元素
assign(n,val) 将所有元素替换为n个val
swap() 交换两个链表
reverse() 实现list逆置
merge() 合并一个list
remove(x) 删除所有值为x的元素
参考代码和运行结果：
1.3 deque
deque动态将多个连续空间通过指针数组合在一起，随时可以增加一段新的空间，用来做队列，在常数时间内对头尾两端进行插入和删除操作，虽然和vector一样都是采用动态数组来管理元素，但不需要保留空间，可以随机存取。
常用方法：
push_front(x) 将x插入队首
push_back(x) 将x插入队尾
pop_front() 弹出队首
pop_back() 弹出队尾
front() 获取队首
back() 获取队尾
empty() 判断deque是否为空
size() 返回deque当前元素的个数
clear() 清空一个deque
max_size() 返回deque所能容纳的最大容量
assign(n,val) 将所有元素替换为n个val
insert(pos,elem) 在pos上插入一个元素
erase(pos) 删除pos位置上的元素
resize(n) 重定义deque的大小
参考代码和运行结果：
1.4 set/multiset
set(集合)是一个用来存储同一数据类型的关联式容器，每个元素的值都唯一，而且系统能根据元素的值自动排序。set内部采用的是一种非常高效的平衡检索二叉树：红黑树(Red-Black Tree)，性能好于一般的平衡二叉树。multiset和set的区别在于multiset可以包含多个数值相同的元素，set不可以。
常用方法为：
begin() 返回set容器的第一个元素
end() 返回set容器的最后一个元素的下一个位置
clear() 删除set容器中的所有的元素 empty() 判断set容器是否为空,如果为空，返回true
max_size() 返回set容器能容纳的元素最大个数
size() 返回当前set容器中的元素个数
insert() 在集合中插入元素
erase() 在集合中删除元素
count() 返回某个值元素的个数
find() 返回一个指向被查找到元素的迭代器
lower_bound() 返回指向大于（或等于）某个值元素的第一个迭代器
upper_bound() 返回大于某个值元素的迭代器
参考代码和运行结果：
1.5 map/multimap
map是一个关联容器，提供一对一(key-value)的数据处理功能，key和value可以是任意类型，可以根据key值快速查找value，查找的时间复杂度是log(n),也可以快速插入key-value值，快速删除，根据key值修改value，遍历所有数据。map内部是一棵红黑树，具有根据key值自动排序的功能。multimap和map的区别是multimap的一个key值可以对应多个value。
常用方法：
map<int,string> mp;构造一个map
insert() 插入数据
mp[1]=”111” 用数组方式插入数据
size() 返回map里有多少数据
count() 判定关键字是否出现
find() 定位关键字在哪个位置出现
lower_bound() 返回查找关键字的下界
upper_bound() 返回查找关键字的上界
erase(iterator it) 指定某个位置进行删除
erase(iterator fi,iterator la) 删除一个范围
erase(key) 删除一个关键字
clear() 清空所有元素
begin() 返回指向map头部的迭代器
end() 返回指向map最后一个键值对的下一个位置
参考代码和运行结果：
2
迭代器(iterator)
迭代器用于遍历对象集合的元素，这些元素可能是容器，也可能是容器的子集。迭代器相当于容器和操作容器的算法之间的中介。
迭代器分为以下四种：
①正向迭代器
容器类名::iterator 迭代器名;
②常量正向迭代器
容器类名::const_iterator 迭代器名;
③反向迭代器
容器类名::reverse_iterator 迭代器名;
④常量反向迭代器
容器类名::const_reverse_iterator 迭代器名;
不同容器的迭代器功能
3
算法(iterator)
算法作用于容器，提供了执行各种操作的方式，包括对容器内容执行初始化、排序、搜索和转换等操作。
使用C++标准库的算法，需要包含头文件<algorithm>
用于处理一个或多个iterator区间，第一个区间通常以起点和终点表示，其他区间多数只需要提供起点足够。
当需要用STL中某一个方法时，建议同学们自行查阅API文档。
这里列举一些算法：
（1）只读算法：
查找算法
搜索统计算法
（2）可变序列算法：
可变序列算法包括元素复制，变换，替换，填充，移除和随机生成等。
（3）排序算法：
（4）关系算法：
（5）堆算法：
（6）list容器特有算法：
苏世学社旗下品牌，专注于计算机考研
计算机考研一手资讯，原创高质量干货
深度的学习分享丨咨询前辈丨个性化指导
