C++ 进阶基础之八

大纲

stack 容器

stack 容器的概念

stack 是堆栈容器,属于一种先进后出(First In Last Out,FILO)的数据结构,它只有一个出口。stack 容器允许新增元素、移除元素、取得栈顶元素,但是除了最顶端的元素外,没有任何其他方法可以存取 stack 中的其他元素。stack 没有迭代器,容器中所有元素的进出都必须符合 “先进后出” 的规则,只有 stack 最顶端的元素,才有机会被外界取用。换言之,stack 不提供遍历功能,也不提供迭代器。deque 是双向开口的数据结构,若以 deque 为底部结构并封闭其头端开口,便轻而易举地形成一个 stack。因此,SGI STL 便以 deque 作为缺省情况下的 stack 底部结构。由于 stack 以 deque 做为底部容器完成其所有工作,而具有这种 “修改某物接口,形成另一种风貌” 的性质者,称为 adapter(配接器),因此,stack 往往不被归类为 container(容器),而被归类为 container adapter(容器配接器)。简而言之,stack 是简单地装饰 deque 容器而成为另外的一种容器。

stack 容器的使用

statck 的构造与赋值

默认构造函数

stack 采用模板类实现,stack 对象的默认构造形式: stack <T> stkT;,其中 <> 尖括号内还可以设置指针类型或自定义类型

1
2
3
stack <int> stkInt;          // 一个存放 int 数据的 stack 容器。
stack <float> stkFloat; // 一个存放 float 数据的 stack 容器
stack <string> stkString; // 一个存放 string 数据的 stack 容器
赋值操作说明
1
2
stack(const stack &stk);               // 拷贝构造函数
stack& operator=(const stack &stk); // 重载等号操作符

stack 的常用操作

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
#include<iostream>
#include<stack>

using namespace std;

void printStack(stack<int> &s) {
// 判断容器是否为空
while (!s.empty()) {
// 获取栈顶元素
cout << s.top() << " ";
// 弹出栈顶元素(弹栈)
s.pop();
}
cout << endl;
}

int main() {
// 默认构造函数
stack<int> s1;

// 向栈顶添加元素(压栈)
s1.push(5);
s1.push(12);
s1.push(24);
s1.push(35);
s1.push(46);

printStack(s1);

// 拷贝构造函数
stack<int> s2 = s1;

return 0;
}

程序运行输出的结果如下:

1
46 35 24 12 5 

queue 容器

queue 容器的概念

queue 是队列容器,属于一种先进先出(First In First Out,FIFO)的数据结构,它有两个出口。queue 容器允许从一端新增元素,从另一端移除元素。queue 所有元素的进出都必须符合 ” 先进先出” 的规则,只有 queue 的顶端元素,才有机会被外界取用。queue 不提供遍历功能,也不提供迭代器。由于 queue 以 deque 作为底部容器完成其所有工作,因此,queue 往往也不被归类为 container(容器),而被归类为 container adapter(容器配接器)。简而言之,queue 是简单地装饰 deque 容器而成为另外的一种容器。

queue 容器的使用

queue 的构造与赋值

默认构造函数

queue 采用模板类实现,queue 对象的默认构造形式:queue<T> queT;,其中 <> 尖括号内还可以设置指针类型或自定义类型。

1
2
3
queue<int> queInt;         // 一个存放 int 数据的 queue 容器
queue<float> queFloat; // 一个存放 float 数据的 queue 容器
queue<string> queString; // 一个存放 string 数据的 queue 容器
赋值操作说明
1
2
queue(const queue &que);               // 拷贝构造函数
queue& operator=(const queue &que); // 重载等号操作符

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
#include<iostream>
#include<queue>

using namespace std;

void printQueue(queue<int> &q) {
// 判断队列是否为空
while (!q.empty()) {
cout << "大小: " << q.size() << endl;
cout << "队头: " << q.front() << endl;
cout << "队尾: " << q.back() << endl;
// 弹出(删除)队头元素
q.pop();
}

}

int main() {
// 默认构造函数
queue<int> q1;

// 往队尾添加元素
q1.push(1);
q1.push(3);
q1.push(5);
q1.push(7);
q1.push(9);

// 返回队列的大小
cout << "size = " << q1.size() << endl;

// 返回第一个元素
cout << "first = " << q1.front() << endl;

// 返回最后一个元素
cout << "last = " << q1.back() << endl;

printQueue(q1);

// 拷贝构造函数
queue<int> q2 = q1;

return 0;
}

程序运行输出的结果如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
size = 5
first = 1
last = 9
大小: 5
队头: 1
队尾: 9
大小: 4
队头: 3
队尾: 9
大小: 3
队头: 5
队尾: 9
大小: 2
队头: 7
队尾: 9
大小: 1
队头: 9
队尾: 9

list 容器

list 容器的概念

list 是一个双向链表容器,而且还是一个双向循环链表,可以高效地进行插入和删除元素。链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的(如下图所示)。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。相较于 vector 的连续线性空间,list 就显得负责许多,它的好处是每次插入或者删除一个元素,就是配置或者释放一个元素的空间。因此,list 对于空间的运用有绝对的精准,一点也不浪费。而且,对于任何位置的元素插入或元素的移除,list 永远是常数时间的耗时。

总结

  • 链表采用动态内存分配,不会造成内存浪费和溢出。
  • 链表虽然灵活,但是空间和时间的额外耗费较大。
  • 链表执行插入和删除操作都十分方便,仅修改指针即可实现,不需要移动大量元素。
  • 链表不可以随机存取元素,所以不支持 at.(pos) 函数与 [] 操作符的使用。

list 容器的迭代器

list 容器不能像 vector 一样以普通指针作为迭代器,因为其节点不能保证都在同一块连续的内存空间上。list 迭代器必须有能力指向 list 的节点,并有能力进行正确的递增、递减、取值、成员存取操作。所谓 “list 正确的递增、递减、取值、成员取用” 是指,递增时指向下一个节点,递减时指向上一个节点,取值时取的是节点的数据值,成员取用时取的是节点的成员。由于 list 是一个双向链表,迭代器必须能够具备前移、后移的能力,所以 list 容器提供的迭代器是 BidirectionalIterators。list 有一个重要的性质,插入操作和删除操作都不会造成原有 list 送代器的失效。这在 vector 是不成立的,因为 vector 的插入操作可能造成记忆体重新配置,导致原有的送代器全部失效;甚至 list 元素的删除,也只有被删除的那个元素的迭代器失效,其他迭代器不受任何影响。

list 容器的使用

list 的构造与赋值

默认构造函数

list 采用模板类实现,对象的默认构造形式:list<T> lstT;,其中 <> 尖括号内还可以设置指针类型或自定义类型

1
2
3
list<int> lstInt;         // 定义一个存放 int 数据的 list 容器
list<float> lstFloat; // 定义一个存放 float 数据的 list 容器
list<string> lstString; // 定义一个存放 string 数据的 list 容器
有参构造函数
1
2
3
list(beg, end);           // 构造函数将 [beg, end) 区间中的元素拷贝给本身,注意该区间是左闭右开的区间
list(n, elem); // 构造函数将 n 个 elem 拷贝给本身
list(const list &lst); // 拷贝构造函数
赋值操作说明
1
2
3
4
list.assign(beg, end);               // 构造函数将 [beg, end) 区间中的元素拷贝给本身,注意该区间是左闭右开的区间
list.assign(n, elem); // 将 n 个 elem 拷贝赋值给本身
list& operator=(const list &lst); // 重载等号操作符
list.swap(lst); // 将 lst 与本身的元素互换
构造与赋值的使用
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
#include <iostream>
#include <list>

using namespace std;

void printList(list<int> &L) {
// 遍历容器
for (list<int>::iterator it = L.begin(); it != L.end(); it++) {
cout << *it << " ";
}
cout << endl;
}

int main() {

cout << "------ list 构造函数 ------" << endl;

// 默认构造函数
list<int> myList1;

// 有参构造函数,将 n 个 elem 元素拷贝给本身
list<int> myList2(5, 10);
printList(myList2);

// 有参构造函数,将 [begin, end) 区间中的元素拷贝给本身
list<int> myList3(myList2.begin(), myList2.end());
printList(myList3);

// 拷贝构造函数
list<int> myList4 = myList2;
printList(myList4);

cout << "------ list 赋值操作 ------" << endl;

// 赋值操作,将 [begin, end) 区间中的元素拷贝给本身
list<int> myList5;
myList5.assign(myList2.begin(), myList2.end());
printList(myList5);

// 赋值操作,将 n 个 elem 元素拷贝给本身
list<int> myList6;
myList6.assign(5, 8);
printList(myList6);

// 赋值操作,重载等号操作符
list<int> myList7;
myList7 = myList2;
printList(myList7);

// 赋值操作,将其他容器与本身的元素互换
myList6.swap(myList7);
printList(myList6);
printList(myList7);

return 0;
}

程序运行输出的结果如下:

1
2
3
4
5
6
7
8
9
10
------ list 构造函数 ------
10 10 10 10 10
10 10 10 10 10
10 10 10 10 10
------ list 赋值操作 ------
10 10 10 10 10
8 8 8 8 8
10 10 10 10 10
10 10 10 10 10
8 8 8 8 8

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
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <list>

using namespace std;

void printList(list<int> &L) {
// 遍历容器
for (list<int>::iterator it = L.begin(); it != L.end(); it++) {
cout << *it << " ";
}
cout << endl;
}

void reversePrintList(list<int> &L) {
// 逆向遍历
for (list<int>::reverse_iterator it = L.rbegin(); it != L.rend(); it++) {
cout << *it << " ";
}
cout << endl;
}

int main() {
cout << "------ list 插入操作 ------" << endl;

list<int> myList1;

// 往容器的尾部插入元素
myList1.push_back(10);
myList1.push_back(20);
myList1.push_back(30);
printList(myList1);

// 往容器的头部插入元素
myList1.push_front(300);
myList1.push_front(200);
myList1.push_front(100);
printList(myList1);

// 往 pos 位置插入 elem 数据的拷贝,返回新数据的位置
myList1.insert(myList1.begin(), 400);
printList(myList1);

// 往 pos 位置插入 n 个 elem 数据,无返回值
myList1.insert(myList1.begin(), 2, 500);
printList(myList1);

// 往 pos 位置插入 [begin, end) 区间的数据,无返回值
list<int> myList2;
myList2.push_back(1);
myList2.push_back(2);
myList2.push_back(3);
myList1.insert(myList1.begin(), myList2.begin(), myList2.end());
printList(myList1);

cout << "------ list 删除操作 ------" << endl;

// 删除容器头部的数据
myList1.pop_front();
printList(myList1);

// 删除容器尾部的数据
myList1.pop_back();
printList(myList1);

// 删除 pos 位置的数据,返回下一个数据的位置
myList1.erase(myList1.begin());
printList(myList1);

// 删除容器中所有与 elem 值匹配的元素
myList1.remove(100);
printList(myList1);

cout << "------ list 读取操作 ------" << endl;

// 获取第一个元素
cout << myList1.front() << endl;

// 获取最后一个元素
cout << myList1.back() << endl;

cout << "------ list 清空操作 ------" << endl;

list<int> myList3;
myList3.push_back(10);
myList3.push_back(10);
myList3.clear();
printList(myList3);

cout << "------ list 大小操作 ------" << endl;

// 返回容器中元素的个数
cout << "size = " << myList1.size() << endl;

// 判断容器是否为空
bool isEmpty = myList1.empty();
cout << "isEmpty = " << (isEmpty ? "true" : "false") << endl;

// 重新指定容器的长度 num,若容器变长,则以默认值填充新位置,若容器变短,则末尾超出容器长度的元素会被删除
myList1.resize(6);
cout << "size = " << myList1.size() << endl;

// 重新指定容器的长度 num,若容器变长,则以 elem 值填充新位置,若容器变短,则末尾超出容器长度的元素会被删除
myList1.resize(9, 11);
printList(myList1);
cout << "size = " << myList1.size() << endl;

cout << "------ list 逆向遍历操作 ------" << endl;

list<int> myList11;
myList11.push_back(1);
myList11.push_back(2);
myList11.push_back(3);
reversePrintList(myList11);

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
------ list 插入操作 ------
10 20 30
100 200 300 10 20 30
400 100 200 300 10 20 30
500 500 400 100 200 300 10 20 30
1 2 3 500 500 400 100 200 300 10 20 30
------ list 删除操作 ------
2 3 500 500 400 100 200 300 10 20 30
2 3 500 500 400 100 200 300 10 20
3 500 500 400 100 200 300 10 20
3 500 500 400 200 300 10 20
------ list 读取操作 ------
3
20
------ list 清空操作 ------

------ list 大小操作 ------
size = 8
isEmpty = false
size = 6
3 500 500 400 200 300 11 11 11
size = 9
------ list 逆向遍历操作 ------
3 2 1

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
#include <iostream>
#include <list>

using namespace std;

void printList(list<int> &L) {
// 遍历容器
for (list<int>::iterator it = L.begin(); it != L.end(); it++) {
cout << *it << " ";
}
cout << endl;
}

bool myCompare(int v1, int v2) {
// 从大到小排序
return v1 > v2;
}

int main() {
list<int> myList;
myList.push_back(1);
myList.push_back(3);
myList.push_back(2);

cout << "------ list 反转操作 ------" << endl;

myList.reverse();
printList(myList);

cout << "------ list 排序操作 ------" << endl;

// 排序(从小到大)
myList.sort();
printList(myList);

// 排序(从大到小)
myList.sort(myCompare);
printList(myList);

return 0;
}

程序运行输出的结果如下:

1
2
3
4
5
------ list 反转操作 ------
2 3 1
------ list 排序操作 ------
1 2 3
3 2 1

list 的自定义数据类型操作

提示

  • 对 list 的自定义类型数据类型进行排序时,必须指定排序规则。
  • 调用 remove() 函数移除 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
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
75
76
77
#include <iostream>
#include <string>
#include <list>

using namespace std;

class Person {

public:
Person(string name, int age) {
this->name = name;
this->age = age;
}

// 获取名称
string getName() const {
return this->name;
}

// 获取年龄
int getAge() const {
return this->age;
}

// 重载 == 双等号操作符
bool operator==(const Person &p) {
return this->name == p.name && this->age == p.age;
}

private:
string name;
int age;

};

void printList(list<Person> &L) {
// 遍历容器
for (list<Person>::iterator it = L.begin(); it != L.end(); it++) {
cout << "name: " << it->getName() << ", age: " << it->getAge() << endl;
}
}

bool myCompare(Person &p1, Person &p2) {
// 按年龄从大到小排序
return p1.getAge() > p2.getAge();
}

int main() {
list<Person> myList;

Person p1("Tom", 17);
Person p2("Jim", 18);
Person p3("Peter", 19);
Person p4("David", 20);

cout << "------ list 插入操作(自定义数据类型) ------" << endl;

myList.push_back(p1);
myList.push_back(p2);
myList.push_back(p3);
myList.push_back(p4);
printList(myList);

cout << "------ list 删除操作(自定义数据类型) ------" << endl;

// 调用 remove() 函数移除 list 容器中的元素时,自定义数据类型必须重载 `==` 双等号操作符,否则移除操作会执行失败
myList.remove(p3);
printList(myList);

cout << "------ list 排序操作(自定义数据类型) ------" << endl;

// 对 list 的自定义类型数据类型进行排序时,必须指定排序规则
myList.sort(myCompare);
printList(myList);

return 0;
}

程序运行输出的结果如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
------ list 插入操作(自定义数据类型) ------
name: Tom, age: 17
name: Jim, age: 18
name: Peter, age: 19
name: David, age: 20
------ list 删除操作(自定义数据类型) ------
name: Tom, age: 17
name: Jim, age: 18
name: David, age: 20
------ list 排序操作(自定义数据类型) ------
name: David, age: 20
name: Jim, age: 18
name: Tom, age: 17