STL标准模板库
6/17/25About 15 min
STL标准模板库
一、概述
- STL的全称为Standard Template Library，即标准模板库。STL由三大部分构成，分别是容器（Containers）、算法（Algorithms）以及迭代器（Iterators），它们通过泛型设计实现了数据结构与操作的分离，极大提升了代码复用性和灵活性。
- STL模板库提供的容器类，结合了数组和链表的优缺点，将开发者从内存管理的细节中解脱出来。同时STL内部使用了模板，将常用的链表、队列、栈等数据结构的相关操作更加泛化。模板是C++的一部分，但是STL标准模板库并不是C++的一部分。
1. 十大容器简介
基本容器：
- 向量（vector）：类似数组（内部是线性存储）支持下标访问，在尾部添加和删除元素效率高，也可以在中间执行添加删除操作，但效率很低。
- 双端队列( deque ) : 支持下标访问（头尾两端都可添加/删除操作）。
- 列表（list）：在任何位置添加和删除操作都很方便，不支持下标访问。
裁剪容器：
- 堆栈（stack）：支持在一端存储和提取元素。
- 队列（queue）：支持从前端提取，后端压入元素。
- 优先队列（priority_queue）：类似队列，但所提取的是具有最高优先级的元素（默认大者优先）。
关联容器：
- 映射（map）：以 key-value对的形式存储数据，以key的升序排列，key唯一（内部结构是红黑树）。
- 多重映射（multimap）：允许key重复出现的映射。
- 集合（set）：没有value的映射。
- 多重集合（multiset）：没有value的多重映射。
容器分类:
- 线性容器：（向量，双端队列，列表）这类容器元素按照线性（线性：通过一个能找下一个）顺序排列，必须支持某种形式的next操作，以便从一个元素移动到下一个元素（迭代）。
- 适配器容器：（堆栈，队列，优先队列）这类容器是对线性容器的一些接口加以屏蔽的产物。
- 关联容器：（映射，多重映射，集合，多重集合）这类容器根据一个元素相关联的key来存储或提取数据元素，存储是以key-value对的形式，按照key的升序（二叉树存储）。
十大容器的共同特点：
- 所有容器都支持 拷贝构造 和 拷贝赋值。
- 相同类型的两个容器之间可以通过==进行相等性判断。
- 容器存储的为数据的副本，这也就意味着存入容器中的对象应支持拷贝构造和拷贝赋值。
- 通常情况下，被存放到容器中的对象应支持无参构造。
2. 迭代器简介
顺序迭代器：一次只能向后或者向前迭代一步，只支持++和--运算。
随机迭代器：即能一次向后或者向前迭代一步，也可以迭代多步，除了支持++和--，也支持对整数的加减运算。
正向迭代器：起始迭代器指向向量第一个元素位置，终止迭代器指向向量最后一个元素的下一个位置，增操作向容器的尾部移动，减操作向容器的首部移动。
反向迭代器：起始迭代器指向向量的最后一个元素的位置，终止迭代器指向向量第一个元素的前一个位置，增操作向容器的首部移动，减操作向容器的尾部移动。
注意：除了向量和双端队列以及优先队列支持随机迭代器以外，其余容器只支持顺序迭代器。四个迭代器类：
iterator、const_iterator、reverse_iterator、const_reverse_iterator八个迭代器对象：
begin()、end()、begin() const、end() const
rbegin()、rend()、rbegin() const、rend() const
二、向量容器
1. 向量容器的成员函数
front()：获取头结点数据
back()：获取尾结点数据
insert()：在迭代器指向的位置添加结点
erase()：删除迭代器指向的结点
push_back()：给向量容器添加尾结点
pop_back()：删除向量容器的尾结点
empty()：向量容器判空
clear()：清空向量
size()：向量维护元素个数
resize()：设置向量元素个数
capacity()：获取向量容量
reserve()：设置向量的容量
注意：大小指当前存储了多少数据，容量指最多能存储多少数据。
2. 向量容器的初始化
- 向量中的元素被存储在一段连续的内存空间中。
- 向量维护的内存空间会随着新元素的增加而自动增长。
- 内存空间的连续性不会妨碍向量元素的增加，如果内存空间无法满足新元素的增加，向量会开辟新的足够的连续内存空间，并把原内存空间的数据复制到新的内存空间，释放原内存空间。
- 向量的增加会伴随着内存空间的分配和释放，元素复制和销毁等额外开销。
- 如果能够在创建向量时合理预分配一些空间，将很大程度上缓解这些额外开销。
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
class Student {
public:
Student(string const& name = ""):m_name(name) {
cout << "缺省构造了：" << m_name << "{" << this << "}" << endl;
}
Student(Student const& that) :m_name(that.m_name) {
cout << "用：" << that.m_name << "{" << &that << "}" << "拷贝构造了" << m_name << "{" << this << "}" << endl;
}
~Student(){
cout << "析构了" << m_name << "{" << this << "}" << endl;
}
private:
string m_name;
};
int main() {
vector<Student> vs;
// vs.resize(10);
vs.push_back(Student("张三")); // 缺省构造出来的张三是一个匿名对象， 其生命周期只有语句级别
vs.push_back(Student("李四"));
getchar();
return 0;
}/*
未使用resize()设置向量初始大小：
缺省构造了：张三{0x7fff66115eb0}
用：张三{0x7fff66115eb0}拷贝构造了张三{0x5c2bd45c46c0}
析构了张三{0x7fff66115eb0}
缺省构造了：李四{0x7fff66115eb0}
用：李四{0x7fff66115eb0}拷贝构造了李四{0x5c2bd45c4710}
用：张三{0x5c2bd45c46c0}拷贝构造了张三{0x5c2bd45c46f0}
析构了张三{0x5c2bd45c46c0}
析构了李四{0x7fff66115eb0}
*/
最初分配的内存不够时，会有大量的复制和销毁开销（用副本再造副本）。因此在创建向量时，合理地预分配空间可解决此问题。
3. 向量迭代器的使用
- 增加操作：insert
- 删除操作：erase
- 修改操作：
- 查询查操作：find
- 排序操作：sort
#include <iostream>
#include <vector>
#include <algorithm> //find sort 所需要的头文件
using namespace std;
class Student {
public:
Student(string const& name = "", int age = 0) :m_name(name), m_age(age) {}
bool operator==(Student const& that)const {
return m_name == that.m_name && m_age == that.m_age;
}
bool operator<(Student const& that)const {
return m_age < that.m_age; //改成 > 就是降序排列了
}
private:
string m_name;
int m_age;
friend ostream& operator<<(ostream& os, Student const& that);
};
ostream& operator<<(ostream& os, Student const& that) {
return os << that.m_name << ":" << that.m_age;
}
void show(string const& str, vector<Student>& v) {
cout << str << endl;
typedef vector<Student>::iterator IT;
for (IT it = v.begin();it != v.end();++it)
cout << *it << " ";
cout << endl << "------------" << endl;
}
class CMP {
public:
bool operator()(Student const& a, Student const& b) {
return a < b; //这里复用了之前的 < 操作符，不复用再次实现其中的逻辑也可以
}
};
int main() {
vector<Student> vs;
vs.reserve(10);
vs.push_back(Student("张飞", 22));
vs.push_back(Student("赵云", 20));
vs.push_back(Student("黄忠", 25));
vs.push_back(Student("关羽", 24));
vs.push_back(Student("马超", 29));
show("添加结点后：", vs);
vs.insert(vs.begin(), Student("刘备", 20));
show("向迭代器指向的位置添加结点后：", vs);
vs.erase(vs.begin());
show("删除迭代器指向的结点后：", vs);
typedef vector<Student>::iterator IT;
IT it = vs.begin();
*it = Student("诸葛亮", 18);
show("更改迭代器指向的结点后：", vs);
//find是一个通用的操作，对于多种容器都适用，因此放在全局域中
IT fit = find(vs.begin(), vs.end(), Student("赵云", 20)); // 需要==实现，Student需要对其进行重载
if (fit != vs.end())
vs.erase(fit);
show("找到赵云并删除后：", vs);
sort(vs.begin(), vs.end()); //"<" Student需要重载<
CMP cmp;//比较器
sort(vs.begin(), vs.end(), cmp); //比较器--> 自己实现比较类的时候要重载()操作符
show("排序后", vs);
return 0;
}三、双端队列/列表
1. 双端队列
- 双端队列和向量差别
- 首尾两端同样都是开放的，因此他同时提供了首尾两端增删元素的接口。
- 没有提供设置/获取容量的函数，设置和获取容器大小的函数存在。
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
class Student {
public:
Student(string const& name = "", int age = 0) :m_name(name), m_age(age) {}
bool operator==(Student const& that)const {
return m_name == that.m_name && m_age == that.m_age;
}
bool operator<(Student const& that)const {
return m_age < that.m_age;
}
private:
string m_name;
int m_age;
friend ostream& operator<<(ostream& os, Student const& that);
};
ostream& operator<<(ostream& os, Student const& that) {
return os << that.m_name << ":" << that.m_age;
}
void show(string const& str, deque<Student>& d) {
cout << str << endl;
typedef deque<Student>::iterator IT;
for (IT it = d.begin();it != d.end();++it)
cout << *it << " ";
cout << endl << "------------" << endl;
}
int main() {
deque<Student> di;
di.push_front(Student("张飞", 22));
di.push_front(Student("赵云", 20));
di.push_front(Student("马超", 21));
di.push_back(Student("关羽", 28));
di.push_back(Student("黄忠", 44));
show("添加结点后：", di);
typedef deque<Student>::iterator IT;
di.insert(di.begin(), Student("刘备", 50));
show("在迭代器指向的位置添加结点后：", di);
di.erase(di.begin());
show("删除迭代器指向的结点后：", di);
IT it = di.begin();
*it = Student("吕布", 36);
show("更改迭代器指向的结点后：", di);
IT fit = find(di.begin(), di.end(), Student("黄忠", 44));
if (fit != di.end())
di.erase(fit); //重载==操作符
show("找到黄忠并删除后:", di);
sort(di.begin(), di.end()); //"<"
show("排序后：", di);
return 0;
}//总结:
// 把数据扔到容器后，容器要什么操作，这个类就得支持什么操作。如 == <
// 对于类类型排序，可以通过重载< 在return语句中实现升降序。对于基本类型如int，使用比较器来实现。
2. 列表
唯一化
void unique(void); 将连续重复出现的元素唯一化。排序
都是全局排序，即所有的结点都要参与排序。
注意这里的sort是成员函数（列表相多提供了两个成员函数用于排序）
原因：连续存储的数据进行排序必须交换位置，而列表无需交换数据，只要更改指针指向就可以实现排序了。全局的sort会交换数据位置，两个成员函数sort不会交换数据位置。
void sort(void); 通过 < 比大小
template<class LESS>void sort(LESS less); 通过比较器比大小- 拆分：将参数列表中的部分或全部元素剪切到调用列表中
template<class IT>void splice( IT pos, list& lst );
template<class IT>void splice( IT pos, list& lst, IT del); //del是参数列表的迭代器
template<class IT>void splice( IT pos, list& lst, IT begin, IT end);注：IT是调用列表的迭代器，用来指示元素剪切后存到调用列表中的位置。
即将参数列表中的部分或者全部元素，剪切到调用列表迭代器pos所指向的位置的前面。
#include <iostream>
#include <list>
using namespace std;
class CMP {
public:
bool operator()(int const& a, int const& b) {
return a > b;
}
};
void show(string const& str, list<int>& l) {
cout << str << endl;
typedef list<int>::iterator IT;
for (IT it = l.begin();it != l.end();++it)
cout << *it << endl;
cout << endl << "----------" << endl;
}
int main() {
list<int> ls;
for (int i = 0;i < 5;i++)
ls.push_front(10 + i);
for (int i = 0;i < 5;i++)
ls.push_back(10 - i);
show("添加结点后", ls);
ls.unique();
show("唯一化后", ls);
//ls.sort();
//对于基本类型降序排列只能用比较器去实现，因为不可能去int里面重载它的操作符。
CMP cmp; //比较器 -->重载()操作符
ls.sort(cmp);
show("排序后", ls);
list<int> lst;
ls.push_back(1000); ls.push_back(2000); ls, push_back(3000);
ls.splice(ls.begin(), lst);
show("ls:", ls);
show("lst:", lst);
return 0;
}四、适配器容器
1. 栈
定义形式
stack<元素类型，[底层容器类型]> 堆栈对象（构造实参表）底层容器：vector / deque(默认) / list / 自己实现的容器也可以作为栈的底层容器
成员函数：（左边是栈的，右边是底层容器的）
push ->push_back （无形中屏蔽了底层容器的部分功能）
pop ->pop_back
top -> back
size -> size
empty -> empty
clear -> clear栈的底层实现
tempalate<class T,class D=deque<T>> class stack{
public:
void push(T data) { m_d.push_back(data); }
void pop() { m_d.pop_back(); }
……
private:
D m_d; //
};
stack<int> s; 或 stack<int,vector<int>> s; 或 stack<int,list<int>> s;#include <iostream>
#include <stack>
#include <deque> //把deque、vector和list都包含进来，测试看它们是否都能作为底层容器
#include <vector>
#include <list>
using namespace std;
int main() {
stack <int> s; //stack <int,deque<int>> s; stack <int,list<int>> s; stack <int,vector<int>> s;
s.push(1); s.push(2); s.push(3); s.push(4);
while (!s.empty()) {
cout << s.top() << endl;
s.pop();
}
return 0;
}2. 队列
定义形式
queue<元素类型，[底层容器类型]> 队列对象（构造实参表）底层容器：deque(默认) / list / vector不可以
成员函数
push ->push_back
pop ->pop_front
back - > back
front -> front
size -> size / empty -> empty / clear -> clear队列的底层实现
tempalate<class T,class D=deque<T>> class queue{
public:
void push(T data) { m_d.push_back(data); }
void pop() { m_d.pop_front(); }
……
private:
D m_d; //
};
queue<int> s; 或 queue<int,vector<int>> s; 或 queue<int,list<int>> s;#include <iostream>
#include <queue>
#include <deque>
#include <vector> //向量不可以作为队列的底层容器
#include <list>
using namespace std;
int main() {
queue <int> s; //queue <int,deque<int>> s; queue <int,list<int>> s; //向量不可以queue <int,vector<int>> s;向量不可以
s.push(1); s.push(2); s.push(3); s.push(4);
while (!s.empty()) {
cout << s.front() << endl;
s.pop();
}
return 0;
}3. 优先队列
- 定义形式：
priority_queue<元素类型,【底层容器类型】,【比较器类型】>优先队列对象（构造实参表） - 底层容器：deque(默认) /vector
(支持随机迭代，因此list不能不能作为底层容器) - 注意事项：
优者先出，默认以大者为优，也可以通过比较器定制（比较器必须是类），
如果没有“比较器”默认内部使用<运算符。
并不是出队时挑，而且进队列时就保证有序 - 成员函数
push /pop / top / empty / size / clear
#include <iostream>
#include <queue>
#include <vector>
#include <deque>
#include <list> //不能作为底层容器
using namespace std;
class CMP {
public:
bool operator()(int const& a, int const& b) {
return a > b; //小者为优
}
};
int main() {
priority_queue<int,deque<int>,CMP> pq;
//为什么优先容器在定义比较类的时候就要比较器类型？因为push的时候就要进行比较。
pq.push(4); pq.push(11); pq.push(1); pq.push(8); pq.push(6);
while (!pq.empty()) {
cout << pq.top() << endl;
pq.pop();
}
}五、关联容器
1. 映射
定义形式： map<键类型，值类型> 映射对象；
逻辑模型：一一对应模型 键（信息索引）值（信息内容）对。
//键值对并不陌生，数组中（数组下标,值）就是一种键值对。
主要用于信息检索，性能可以达到对数级（O(logN)），类似二分法。 //速度快！物理模型：平衡有序二叉树又名红黑树。
//有序二叉树有缺陷。5 4 3 2 1 5作为头结点，会变成只有左子树的树，退化成链表了。
//红黑树：相差不能超过一层。 //树形结构检索东西快！键必须唯一。
迭代过程实际上是关于键的中序遍历（L D R）,键的升序。
存储单位是由键和值组成的pair。
template<class FIRST,class SECOND>class pair{
public:
pair(FIRST const& f, SECOND const& s) : first(f),second(s){}
FIRST first; //键
SECOND second;//值
}映射的迭代器相当于指向pair对象的指针。
//pair是一个类模板
//映射容器的每个结点保存的数据为pair对象，pair对象就是键值对。
- 映射中的键是只读的。 //改键会影响红黑树的平衡有序，需要重新组织映射，因此不让改。
- 检索性能好（一砍砍一半），构建和修改性能较差。适用于结构稳定，但是需要频繁检索的操作。
- 支持“下标”[ ]运算，用键作为下标，得到对应的值的引用。如果所给出的键不存在，增加一个节点，返回其值的引用。
- 成员函数
insert( pair<FIRST,SECOND>(键，值) )
insert( make_pair(键，值))
迭代器 = find(键)；
失败返回终止迭代（并非全局函数而是 成员函数）
//insert需要一个pair对象，可以通过构造造出来，也可以通过make_pair函数造出来。
#include <iostream>
#include <map>
using namespace std;
//模拟投票，5个人选举
class Candidate {
public:
Candidate(string name = "") :m_name(name), m_vote(0) {}
string m_name;
int m_vote;
};
void show(map<char, Candidate>& m) {
typedef map<char, Candidate>::iterator IT;
for (IT it = m.begin();it != m.end();++it) {
cout << "(" << (*it).first << ")" << (*it).second.m_name << " ";
}
cout << endl;
}
int main() {
map<char, Candidate> m;
m.insert(pair<char, Candidate>('A', Candidate("张飞")));
m.insert(make_pair('B', Candidate("关羽")));
m['C'] = Candidate("赵云"); //不存在则创建 推荐使用这种，比较简短方便
m['D'] = Candidate("马超"); m['E'] = Candidate("黄忠");
typedef map<char, Candidate>::iterator IT;
for (int i = 0;i < 10;i++) {
show(m);
char ch;
cin >> ch;
IT fit = m.find(ch);
if (fit == m.end()) {
cout << "废票" << endl;
continue;
}
++(*fit).second.m_vote;
}
for (IT it = m.begin();it != m.end();++it) {
cout << (*it).second.m_name << ":" << (*it).second.m_vote << endl;
}
return 0;
}2. 多重映射
允许键重复的映射，表示一对多的逻辑关系，不支持下标运算符。
#include <iostream>
#include <map>
using namespace std;
int main() {
multimap<string, int> m;
m.insert(make_pair("张飞", 80));
m.insert(make_pair("赵云", 50));
m.insert(make_pair("赵云", 90));
m.insert(make_pair("张飞", 80));
typedef multimap<string, int>::iterator IT;
for (IT it = m.begin();it != m.end();++it) {
cout << (*it).first << ":" << (*it).second << " ";
}
cout << endl;
}3. 集合
- 没有值只有键的映射，即只存单一数据类型，不再是pair
- 与向量等基本容器相比最大优势就是 排重。
//另一优势，用红黑树存的，检索速度快。
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s;
s.insert(1); s.insert(2); s.insert(3); s.insert(2); s.insert(3);
cout << "结点个数:" << s.size() << endl;
typedef set<int>::iterator IT;
for(IT it=s.begin();it!=s.end();++it)
cout << (*it) << " " ;
cout << endl;
return 0;
}4. 多重集合
- 没有值只有键的多重映射。
//仍然是红黑树保存的，检索速度快。
#include <iostream>
#include <set>
using namespace std;
int main() {
multiset<int> s;
s.insert(1); s.insert(2); s.insert(3); s.insert(2); s.insert(3);
cout << "结点个数:" << s.size() << endl;
typedef multiset<int>::iterator IT;
for(IT it=s.begin();it!=s.end();++it)
cout << (*it) << " " ;
cout << endl;
return 0;
}★四个比较重要的容器：向量、双端队列、列表、映射。