# 十三. 标准模板库（STL）
标准模板库，其主要思想是结合C++的模板机制，设计出一系列的针对数据结构中具体问题的类模板和函数模板，所以也被称为是一个泛型化的数据结构和算法库
STL倡导泛型编程，形成了具有优秀、高效编码的模板库，成为了标准C++体系的一部分，使程序员将主要精力集中在高层逻辑而不是底层操作，极大地提高了编程效率
迭代器
可以理解为一种高级指针
定义迭代器变量的格式：
容器类名称 <数据类型参数>:: iterator 迭代器变量;迭代器提供的基本操作和函数有：
- 获取当前被指向的元素，用“ * ”或“ -> ”表示；
- 指向下一个元素，迭代器的增量使用运算符 ++；
- 使用运算符“ == ”判断相等；
- begin() 返回指向容器首元素的迭代器
- end() 返回容器末元素后一个位置的迭代器，注意不是末元素位置
# 1. 容器
# （1）顺序容器
有vector,deque,list
存放元素都是线性的，具有很多共同操作
它们的差别在于访问元素的方式，以及添加或删除元素相关操作的效率
以下为共同操作：
| 函数名 | 功能说明 |
|---|---|
| begin | 返回容器中前端的迭代器 |
| end | 返回容器中末端的迭代器 |
| rbegin | 返回容器中前端的倒转迭代器 |
| rend | 返回容器中末端的倒转迭代器 |
| insert（pos,e） | 在容器中pos位置处插入元素e |
| erase（pos） | 删除pos位置的元素 |
| erase（begin，end） | 删除[begin，end]区间中的元素 |
| clear | 删除容器内的所有元素 |
| max_size | 返回容器中的容量 |
| size | 返回容器当前包含元素的数量 |
| empty | 若容器为空（无元素），返回true；否则，返回false |
根据不同要求，选择合适的容器，以提高效率
# vecter
向量vector用于容纳不定长的线性序列，允许对各元素进行随机访问，可以理解为一个动态数组
特点：
- 对序列元素可以快速、随机地访问，可以使用下标直接访问“[]”
- 在末端插入和删除元素速度快，而在其他位置插入、删除需要移动大量元素，所以效率低
- 自己的函数：
函数名 功能说明 front 返回容器中首元素的引用 back 返回容器中末端元素的引用 push_back 向容器末端插入元素 pop_back 删除末端元素 例:
#include<iostream> #include<vector> //包含头文件 using namespace std; int main() { vector<int> v; //定义v向量对象，vector为类模板，将其实例化为模板类，里面存放整型数据，定义对象名为v v.insert(v.begin(),1);//把1插入向量v首端 //v中为1 v.insert(v.begin(),2);//把2插入向量v首端 //v中为2，1 v.insert(v.end(),3);//把3插入向量v末端 //v中为2，1，3 //前面为通用方法，后面为自带方法 v.push_back(4);//向容器末端插入4 //v中为2,1,3,4 v.insert(v.begin()+3,5);//在第1+3位置插入5 //v中为2,1,3,5,4 v.erase(v.begin()+2);//删除第1+2个元素 //v中为2,1,5,4 //输出所有元素 for(int i = 0;i < v.size();i++)//size()表示当前所有元素的个数 cout<<v[i]<<"\t"; cout<<"v.max_size:"<<v.max_size()<<endl;//容器可以存储元素的最大个数,与机器的环境有关 //v中设计元素的个数 cout<<"v.capacity:"<<v.capacity()<<endl;//目前v中可以存储元素的最大个数，可以动态增加，可能不是一个一个增加的 return 0; }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21# deque
与vector相似，双端队列deque也是一种动态数组的形式，可以高效地在队尾插入、删除元素
不同的是：还可以高效地在队头插入、删除元素
特点:
- 可以通过[]下标形式来访问队列中的元素
- 两端插入、删除速度快、效率高，而在中间插入数据时开销大
- 自己的函数：
函数名 功能说明 push_front 插入数据到前端 pop_front 删除前端数据 push_back 向容器末端插入元素 pop_back 删除末端元素 例:
#include<iostream> #include<deque> using namespace std; int main() { deque<char> d;//定义d向量对象 d.push_back('a');//向容器末端插入a //d中为：a d.push_back('b');//向容器末端插入b //d中为：a,b d.push_front('c');//向容器前端插入c //d中为：c,a,b d.push_back('d');//向容器末端插入d //d中为：c,a,b,d d.pop_back();//删除容器末端 //d中为：c,a,b d.pop_front();//删除容器末端 //d中为：a,b //输出v的所有元素 for(int i = 0;i < d.size();i++) cout<<d[i]<<"\t"; }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16# list
链表容器list其内部数据结构实质上是一个双向链表
特点:
- 不支持随机访问，即不支持“[]”运算符，只能用对应的迭代器来操作元素
- 在任何位置插入、删除都不需要移动，所以速度快、效率高
- 自己的函数：
函数名 功能说明 push_back 插入数据到末端 push_front 插入数据到前端 splice(pos,a) 将链表a插入到当前链表pos之前 splice(pos,a,posa) 将链表a在posa后的元素移到当前链表pos前 splice(pos,a,abeg,aend) 将链表a在[abeg,aend]内的元素移到当前链表pos之前 unique 删除链表中相邻的重复元素 remove(x) 删除与x相等的元素 sort 对链表排序 reverse 逆转链表中元素的次序 例:
#include<iostream> #include<list> using namespace std; int main() { list<double> l; //定义l向量对象 l.push_front(1.1); //向容器前端插入1.1 l中为1.1 l.push_front(5.5); //向容器前端插入5.5 l中为5.5，1.1 l.push_front(2.2); //向容器前端插入2.2 l中为2.2，5.5，1.1 l.push_back(3.3); //向容器末端插入3.3 l中为2.2, 5.5, 1.1, 3.3 list<double>::iterator it; //定义list迭代器 for(it = l.begin();it != l.end();it++)//输出l的所有元素 { cout<<*it<<"\t"; } l.sort();//排序 l中为1.1, 2.2, 3.3, 5.5 for(it = l.begin();it != l.end();it++)//输出l的所有元素 { cout<<*it<<"\t"; } cout<<l.size(); //l中元素的个数 l.remove(3.3); //删除l中3.3 //输出l中的所有元素 }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# （2）关联容器
关联容器的每个元素都有一个键值，容器中的元素是按照键的取值升序排列
关联容器的内部实现是采用二叉平衡树，所以可以高效地查找、插入和删除，但不能实现任意位置的操作
左节点比根节点小，右节点比根节点大
# set
- set是一个元素集合，集合中的元素是按有序的方式储存，所以查找、插入和删除速度快
- set中没有重复的元素，但multiset中允许有重复的元素
例:
#include<iostream> #include<set> #include<string> using namespace std; int main() { string name[] = {"Simon","Tony","Harry","John"}; //定义字符串数组 //1 set<string> s; //定义s向量对象 //2 s.insert(name[0]); //3 s.insert(name[1]); //以上1,2,3可写成： set<string> s(name,name+4); //将数组内所有元素都给它 set<string>::iterator it; //定义set迭代器 for(it = s.begin();it != s.end();it++)//输出s的所有元素 { cout<<*it<<"\t"; } string search_name; //输入查找的字符串 cout<<"input search_name:"<<endl; cin>>search_name//按照输入的值进行查找 it = s.find(search_name); //查找 if(it == s.end())//如果查找不到进行插入 { cout<<"not find!"<<endl; s.insert(search_name); for(it == s.begin();it != s.end();it++) cout<<*it<<"\t"; } else //查找到则进行删除 { cout<<"Find!"<<endl; s.erase(search_name); } for(it == s.begin();it != s.end();it++)//输出s的所有元素查看插入结果 cout<<*it<<"\t"; return 0; }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43# map
有点像映射
map映射与set的主要区别：set的元素本身是键本身，而一个map是一个键值对序列，即（key,value）一对值。它提供基于key的快速检索能力，在一个map中key值是唯一的
map提供双向迭代器，既有从前往后的迭代器iterator,也有从后往前的迭代器reverse_iterator
例:
#include<iostream> #include<map> #include<string> using namespace std; int main() { string name[4] = {"Simon","Tony","Harry","John"};//定义字符串数组放姓名 int id[4] = {1101,1102,1103,1104};//定义整型数组放学号 map<string,int> n;//定义n向量对象 for(int i = 0;i < 4;i++)//n[键值] = 元素值 { n[name[i]] = id[i]; } for(i = 0;i < 4;i++)//通过下标输出姓名和学号 { cout<<name[i]<<"\t"<<n[name[i]]<<endl; } map<string,int>::iterator it;//定义map迭代器 for(it = n.begin();it != n.end();it++)//采用迭代器输出 { cout<<it->first<<"\t"<<it->second<<endl; } //采用下标输出和迭代器输出的顺序是不同的，因为键值对是按字符串的ASC11码的值的顺序进行存储的 }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26