C++ 进阶基础之八

发表于 更新于 阅读次数： 评论数： 本文字数： 2.4k 阅读时长 ≈ 2 分钟

大纲

list 容器

list 容器的概念

list 是一个双向链表容器，而且还是一个双向循环链表，可以高效地进行插入和删除元素。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的（如下图所示）。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相较于 vector 的连续线性空间，list 就显得负责许多，它的好处是每次插入或者删除一个元素，就是配置或者释放一个元素的空间。因此，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

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