背景
下周数据结构实验就要开始考试了，所以总结一点C++的标准模板库来学习，希望下周考试能轻松度过
(〃’▽’〃)(〃’▽’〃)(〃’▽’〃)
1 什么是标准模板库（STL）？
1.1 C++标准模板库与C++标准库的关系
C++标准模板库其实属于C++标准库的一部分，C++标准模板库主要是定义了标准模板的定义与声明，而这些模板主要都是类模板，我们可以调用这些模板来定义一个具体的类；与之前的自己手动创建一个函数模版或者是类模板不一样，我们使用STL就不用自己来创建模板了，这些模板都定义在标准模板库中，我们只需要学会怎么使用这些类模板来定义一个具体的类，然后能够使用类提供的各种方法来处理数据。
1.2 STL六大组件
容器（containers）、算法（algorithms）、迭代器（iterators）、函数对象（functors）、适配器（adapters）、分配器（allocators）
2 容器分类
STL对定义的通用容器分三类：顺序性容器、关联式容器和容器适配器。
- 顺序性容器：vector、deque、list
- 关联性容器：set、multiset、map、multimap
- 容器适配器：stack、queue
2.1 vector 容器
vector向量是一种顺序性容器。相当于数组，但其大小可以不预先指定，并且自动扩展。它可以像数组一样被操作，由于它的特性我们完全可以将vector 看作动态数组。
在创建一个vector后，它会自动在内存中分配一块连续的内存空间进行数据存储，初始的空间大小可以预先指定也可以由vector 默认指定。当存储的数据超过分配的空间时，vector会重新分配一块内存块，但这样的分配是很耗时的，在重新分配空间时它会做这样的动作：
- 首先，vector 会申请一块更大的内存块；
- 然后，将原来的数据拷贝到新的内存块中；
- 其次，销毁掉原内存块中的对象（调用对象的析构函数）；
- 最后，将原来的内存空间释放掉。
当vector保存的数据量很大时，如果此时进行插入数据导致需要更大的空间来存放这些数据量，那么将会大大的影响程序运行的效率，所以我们应该合理的使用vector。
2.1.1 初始化vector对象的方式：
1
2
3
4
| vector<T> v1; // 默认的初始化方式，内容为空
vector<T> v2(v1); // v2是v1的一个副本
vector<T> v3(n, i) // v3中包含了n个数值为i的元素
vector<T> v4(n); // v4中包含了n个元素，每个元素的值都是0
|
2.1.2 vector常用函数
empty()：判断向量是否为空，为空返回真，否则为假
begin()：返回向量（数组）的首元素地址
end()： 返回向量（数组）的末元素的下一个元素的地址
clear()：清空向量
front()：返回得到向量的第一个元素的数据
back()：返回得到向量的最后一个元素的数据
size()：返回得到向量中元素的个数
push_back(数据)：将数据插入到向量的尾部
pop_back()：删除向量尾部的数据
2.1.3 遍历方式
vector向量支持两种方式遍历，因为可以认为vector是一种动态数组，所以可以使用数组下标的方式，也可以使用迭代器
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
| #include <iostream>
#include <vector>
using namespace std;
int main(void)
{
vector<int> vec;
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
vec.push_back(4);
vec.push_back(5);
cout << "向量的大小：" << vec.size() << endl;
// 数组下标方式遍历vector
for (int i = 0; i < vec.size(); i++)
cout << vec[i] << " ";
cout << endl;
// 迭代器方式遍历vector
vector<int>::iterator itor = vec.begin();
for (; itor != vec.end(); itor++)
cout << *itor << " ";
cout << endl;
return 0;
}
|
输出结果为：
2.2 双向链表list
学过数据结构的同学都知道，对于一个双向链表来说主要包括3个元素：
- 指向前一个链表节点的前向指针
- 有效数据
- 指向后一个链表节点的后向指针
链表相对于vector向量来说的优点在于：
(1)动态的分配内存，当需要添加数据的时候不会像vector那样，先将现有的内存空间释放，再次分配更大的空间，这样的话效率就比较低了。
(2)支持内部插入、头部插入和尾部插入
缺点：不能随机访问，不支持[]方式和vector.at()、占用的内存会多于vector（非有效数据占用的内存空间）
2.2.1 初始化list对象的方式：
1
2
3
4
5
| list<int> L0; //空链表
list<int> L1(3); //建一个含三个默认值是0的元素的链表
list<int> L2(5, 2); //建一个含五个元素的链表，值都是2
list<int> L3(L2); //L3是L2的副本
list<int> L4(L1.begin(), L1.end()); //L4含L1一个区域的元素[begin, end]。
|
2.2.2 list常用函数
begin()：返回list容器的第一个元素的地址
end()：返回list容器的最后一个元素之后的地址
rbegin()：返回逆向链表的第一个元素的地址（也就是最后一个元素的地址）
rend()：返回逆向链表的最后一个元素之后的地址（也就是第一个元素再往前的位置）
front()：返回链表中第一个数据值
back()：返回链表中最后一个数据值
empty()：判断链表是否为空
size()：返回链表容器的元素个数
clear()：清除容器中所有元素
insert(pos, num)：将数据num插入到pos位置处（pos是一个地址）
insert(pos, n, num)：在pos位置处插入n个元素num
erase(pos)：删除pos位置处的元素
push_back(num)：在链表尾部插入数据num
pop_back()：删除链表尾部的元素
push_front(num)：在链表头部插入数据num
pop_front()：删除链表头部的元素
sort()：将链表排序，默认升序
……
2.2.3 遍历方式
双向链表list支持使用迭代器正向的遍历，也支持迭代器逆向的遍历，但是不能使用 [] 索引的方式进行遍历。
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
44
45
| #include <iostream>
#include <list>
using namespace std;
int main(void)
{
list<int> l1;
// 插入元素方式演示
l1.push_front(1); // 头部插入
l1.push_back(2); // 尾部插入
l1.insert(l1.begin(), 3); // 开始位置插入
l1.insert(l1.end(), 4); // 结束位置插入
cout << "list链表是否为空：" << l1.empty() << endl;
cout << "list链表中元素个数：" << l1.size() << endl;
cout << "list链表第一个元素：" << l1.front() << endl;
cout << "list链表最后一个元素：" << l1.back() << endl;
// 遍历链表正向
list<int>::iterator itor = l1.begin();
for (; itor != l1.end(); itor++)
cout << *itor << " ";
cout << endl;
// 遍历链表逆向
list<int>::reverse_iterator reitor = l1.rbegin();
for (; reitor != l1.rend(); reitor++)
cout << *reitor << " ";
cout << endl;
// 将链表排序
l1.sort();
itor = l1.begin();
cout << "重新排序之后正向遍历：";
for (; itor != l1.end(); itor++)
cout << *itor << " ";
cout << endl;
// 清除容器中的所有元素
l1.clear();
cout << "清除容器所有元素之后大小：" << l1.size() << endl;
return 0;
}
|
输出结果为：
2.3 stack
std::stack 类是容器适配器，它给予程序员栈的功能——特别是 FILO （先进后出）数据结构。
2.3.1 stack常用函数
empty()：检查底层的容器是否为空
top()：访问栈顶元素
size()：返回容纳的元素数
push()：向栈顶插入元素
pop()：删除栈顶元素
swap()：交换内容
2.3.2 常用函数的使用
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
| #include <iostream>
#include <stack>
using namespace std;
int main()
{
int i;
//创建栈 s
stack<int> s;
//将元素压入栈
for(i = 0; i < 10; i++)
{
s.push(i);
}
cout << "栈s中元素的个数为：" << s.size() << endl;
while(!s.empty())
{
cout << s.top() << " "; //获取栈顶元素
s.pop(); //弹出栈顶元素
}
cout << endl;
if(s.empty())
{
cout << "栈s现在为空" << endl;
}
return 0;
}
|
输出结果为：
2.4 queue容器
C++队列queue模板类的定义在头文件中,queue模板类需要两个模板参数，一个是元素类型，一个容器类型，元素类型是必要的，容器类型是可选的，默认为deque类型。
C++队列Queue是一种容器适配器，它给予程序员一种先进先出(FIFO)的数据结构。
2.4.1 初始化list对象的方式：
1
2
| queue<int> q1;
queue<double> q2;
|
2.4.2 queue常用函数
top：访问队头元素
empty()：如果queue中没有元素的话，返回true。
size()：返回queue中元素的个数。
front()：返回queue中第一个元素的引用，若queue是常量，返回一个常引用，若queue为空，返回值是未定义的。
back()：返回queue中最后一个元素的引用，若queue是常量，返回一个常引用，若queue为空，返回值是未定义的。
push()：在queue的尾部添加一个元素的副本。这是通过调用底层容器的成员函数push_back()来完成的。
pop()：删除queue中的第一个元素。
swap(queue &other_q)：将当前queue中的元素和参数queue中
的元素交换。它们需要包含相同类型的元素。也可以调用全局函数模板 swap(q1, q2) 来将当前q1中的元素和q1中的元素中的元素交换
2.4.3 队列使用
对queue进行遍历，可以将其赋予一个副本，然后将副本边输出，边弹出元素。
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| #include <iostream>
#include <queue>
using namespace std;
int main()
{
int e, n, m, i;
queue<int> q1, q2;
queue<int> q3, q4;
for(i = 0; i < 10; i++)
{
q1.push(i);
q3.push(i);
q2.push(i + 10);
q4.push(i + 10);
}
cout << "队列q1\n";
if(!q1.empty())
cout << "dui lie bu kong\n";
n = q1.size();
cout << n << endl;
m = q1.back();
cout << m << endl;
for(i = 0; i < n; i++)
{
e = q1.front();
cout << e << " ";
q1.pop();
}
cout << endl;
if(q1.empty())
cout << "dui lie bu kong\n";
cout << "队列q2\n";
if(!q2.empty())
cout << "dui lie bu kong\n";
n = q2.size();
cout << n << endl;
m = q2.back();
cout << m << endl;
for(i = 0; i < n; i++)
{
e = q2.front();
cout << e << " ";
q2.pop();
}
cout << endl;
if(q2.empty())
cout << "dui lie bu kong\n";
swap(q3, q4);
cout << "队列q1与队列q2交换后\n";
cout << "队列q1\n";
for(i = 0; i < n; i++)
{
e = q3.front();
cout << e << " ";
q3.pop();
}
cout << endl;
cout << "队列q2\n";
for(i = 0; i < n; i++)
{
e = q4.front();
cout << e << " ";
q4.pop();
}
cout << endl;
return 0;
}
|
输出结果为：
2.4.4 优先队列使用
priority_queue<Type, Container, Functional>
Type为数据类型， Container为保存数据的容器，Functional为元素比较方式。
如果不写后两个参数，那么容器默认用的是vector，比较方式默认用operator<，也就是优先队列是大顶堆，队头元素最大。
2.4.4.1 优先输出大数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include <iostream>
#include <queue>
using namespace std;
int main()
{
priority_queue<int> p;
p.push(1);
p.push(2);
p.push(8);
p.push(5);
p.push(43);
for(int i = 0; i < 5; i++)
{
cout << p.top() << endl;
p.pop();
}
return 0;
}
|
输出结果为：
43
8
5
2
1
2.4.4.2 优先输出小数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include <iostream>
#include <queue>
using namespace std;
int main()
{
priority_queue<int, vector<int>, greater<int> >p;
p.push(1);
p.push(2);
p.push(8);
p.push(5);
p.push(43);
for(int i = 0; i < 5; i++)
{
cout << p.top() << endl;
p.pop();
}
return 0;
}
|
输出结果为：
1
2
5
8
43
2.4.4.3 自定义优先级，重载默认的 < 符号
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
| #include <iostream>
#include <queue>
using namespace std;
struct Node
{
int x, y;
Node(int a = 0, int b = 0) : x(a), y(b) {}
};
struct cmp
{
bool operator() (Node a, Node b)
{
if(a.x == b.x)
return a.y > b.y;
return a.x > b.x;
}
};
int main()
{
priority_queue<Node, vector<Node>, cmp> p;
for(int i = 0; i < 10; ++i)
p.push(Node(rand(), rand()));
while(!p.empty())
{
cout << p.top().x << ' ' << p.top().y << endl;
p.pop();
}
return 0;
}
|
输出结果为：
491 9961
5436 4827
11942 2995
15724 19169
16827 23281
18467 41
24464 26962
26500 6334
28145 5705
29358 11478
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以邮件至 xingshuaikun@163.com。
