C++ 巩固基础之五

发表于 阅读次数： 评论数： 本文字数： 4.4k 阅读时长 ≈ 4 分钟

大纲

顺序容器

vector

容器介绍

vector 底层所采用的数据结构是线性连续空间（单向开口的连续内存空间），可以理解为支持动态开辟内存空间的数组。vector 往尾部添加或移除元素的效率非常高，但是往头部或者中部插入元素或移除元素则比较耗时。特别注意，vector 一旦需要执行扩容操作，那么每次都会以原来空间大小的 2 倍进行扩容。

  • 声明

    • vector<int> vec;

  • 插入

    • vec.push_back(20)，往容器尾部插入元素，会导致容器扩容
    • vec.insert(iterator, 30)，往迭代器指向的位置插入元素，会导致容器扩容

  • 删除

    • vec.pop_back()，删除容器尾部的元素
    • vec.erase(iterator)，删除迭代器指向的元素

  • 查询

    • vec[5]，基于下标的随机访问
    • iterator，迭代器遍历
    • for_each，循环遍历
    • find，查找元素

  • 其他

    • vec.size()，获取容器中元素数量
    • vec.empty()，判断容器是否为空
    • vec.swap(vec2)，交换两个容器的元素
    • vec.reserve(size)，预留容器空间，只会给容器的底层开辟指定大小的内存空间，并不会添加新的元素，主要用于减少频繁扩容的次数
    • vec.resize(size)，重新指定容器的大小，不仅会给容器的底层开辟指定大小的内存空间，还会以默认值填充新的位置
    • vec.resize(size, item)，重新指定容器的大小，不仅会给容器的底层开辟指定大小的内存空间，还会以指定值填充新的位置

特别注意

对 vector 容器进行连续的插入（insert）或者删除（erase）操作时，一定要更新迭代器；否则第一次插入或删除操作完成后，迭代器就会失效。

案例代码一

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

using namespace std;

int main() {
    // 设置随机种子
    srand(time(nullptr));

    vector<int> vec;

    for (int i = 0; i < 10; i++) {
        // 往容器尾部插入元素
        vec.push_back(rand() % 100 + 1);
    }

    // 获取容器中元素数量
    cout << "size: " << vec.size() << endl;

    // 迭代器遍历容器
    for (vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // 基于下标访问元素
    cout << "vec[3] = " << vec[3] << endl;

    cout << "================================" << endl;

    // 将容器中所有的偶数元素全部删除
    for (vector<int>::iterator it = vec.begin(); it != vec.end();) {
        if (*it % 2 == 0) {
            // 连续删除元素后必须更新迭代器，否则迭代器会失效
            it = vec.erase(it);
        } else {
            ++it;
        }
    }

    // 循环遍历容器
    for (int i = 0; i < vec.size(); i++) {
        cout << vec[i] << " ";
    }
    cout << endl;

    cout << "================================" << endl;

    // 往容器中所有的奇数元素前面都添加一个偶数
    for (vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        if (*it % 2 != 0) {
            // 连续插入元素后必须更新迭代器，否则迭代器会失效
            it = vec.insert(it, *it - 1);
            ++it;
        }
    }

    // 循环遍历容器
    for (int i = 0; i < vec.size(); i++) {
        cout << vec[i] << " ";
    }
    cout << endl;

    return 0;
}

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

1
2
3
4
5
6
7
size: 10
94 80 7 45 20 57 74 73 16 19 
vec[3] = 45
================================
7 45 57 73 19 
================================
6 7 44 45 56 57 72 73 18 19

案例代码二

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

using namespace std;

int main() {
    // 设置随机种子
    srand(time(nullptr));

    // 容器的默认大小是 0，当插入元素时，容器大小会按照 0 1 2 4 8 16 ... 来扩容
    vector<int> vec;
    cout << "size: " << vec.size() << endl;
    cout << "empty: " << (vec.empty() ? "true" : "false") << endl;

    // 预留空间，只会给容器的底层开辟指定大小的内存空间，并不会添加新的元素，主要用于减少频繁扩容的次数
    vec.reserve(10);
    cout << "size: " << vec.size() << endl;
    cout << "empty: " << (vec.empty() ? "true" : "false") << endl;

    for (int i = 0; i < 10; i++) {
        vec.push_back(rand() % 100 + 1);
    }
    cout << "size: " << vec.size() << endl;
    cout << "empty: " << (vec.empty() ? "true" : "false") << endl;

    cout << "================================" << endl;

    // 容器的默认大小是 0，当插入元素时，容器大小会按照 0 1 2 4 8 16 ... 来扩容
    vector<int> vec2;
    cout << "size: " << vec2.size() << endl;
    cout << "empty: " << (vec2.empty() ? "true" : "false") << endl;

    // 重新指定容器的大小，不仅会给容器的底层开辟指定大小的内存空间，还会填充新的位置
    // 若容器变大，则以默认值（0）填充新位置。如果容器变小，则末尾超出容器大小的元素会被删除
    vec2.resize(10);
    cout << "size: " << vec2.size() << endl;
    cout << "empty: " << (vec2.empty() ? "true" : "false") << endl;

    for (int i = 0; i < 10; i++) {
        vec2.push_back(rand() % 100 + 1);
    }
    cout << "size: " << vec2.size() << endl;
    cout << "empty: " << (vec2.empty() ? "true" : "false") << endl;

    return 0;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
size: 0
empty: true
size: 0
empty: true
size: 10
empty: false
================================
size: 0
empty: true
size: 10
empty: false
size: 20
empty: false

deque

容器介绍

deque 一种双向开口的连续线性空间（双端队列容器），底层的数据结构是支持动态开辟内存空间的二维数组。所谓双向开口，意思是可以在头尾两端分别进行元素的插入和移除操作。虽然 vector 也可以在头尾两端进行操作，但是其头部操作的效率非常低，无法被接受。deque 和 vector 的最大差异，一在于 deque 允许于常数项时间内对头端进行元素的插入或移除操作，二在于 deque 没有所谓容量 capacity 的观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。换句话说，像 vector 那样因旧空间不足而重新配置一块更大的空间，然后拷贝元素，再释放旧空间这样的事情不会发生在 deque 身上，也因此 deque 没有必要提供所谓的空间保留（reserve）功能。虽然 deque 也提供了随机迭代器（Random Access Iterator），但是它的迭代器并不是普通的指针，其复杂度和 vector 不是一个量级，这会影响各个层面的运算效率。因此，除非有必要，应该尽可能的使用 vector，而不是 deque。对 deque 进行的排序操作，为了提高效率，可将 deque 先完整的复制到一个 vector 中，然后对 vector 容器进行排序，再复制回 deque。

deque 本质上是由一段一段的定量连续空间（分段连续内存空间）构造而成，一旦有必要在 deque 的头端或尾端增加新空间，便会配置一段新的定量连续空间，然后串接在整个 deque 的头端或尾端。deque 最大的工作就是维护这些分段连续的内存空间的整体性的假象，并提供随机存取的接口；这避开了重新配置空间、复制数据、释放空间的轮回，代价就是复杂的迭代器架构。既然 deque 使用的是分段连续内存空间，那么就必须有中央控制器，维持其整体连续的假象，这样也导致了数据结构的设计及迭代器的前进后退操作颇为繁琐，deque 底层实现的代码远比 vector 或 list 都多得多。

deque 内部的中控器维护的是每个缓冲区的地址，而缓冲区则存放着真实的数据，目的是让 deque 使用起来像是一片连续的内存空间。deque 采取一块所谓的 map（注意，不是 STL 的 map 容器）作为主控，这里所谓的 map 是一小块连续的内存空间，其中每一个元素（节点）都是一个指针，指向另一段连续性内存空间，称作缓冲区，缓冲区才是 deque 的存储空间的主体。

  • 声明

    • deque<int> deq;

  • 插入

    • deq.push_back(20)，往尾部插入元素
    • deq.push_front(20)，往头部插入元素
    • deq.insert(iterator, 20)，往迭代器指向的位置插入元素

  • 删除

    • deq.pop_back()，往尾部删除元素
    • deq.pop_front()，往头部删除元素
    • deq.erase(it)，删除迭代器指向的元素

  • 查询

    • iterator：迭代器遍历

deque 与 vector 的区别

  • deque 对头部的元素插入与删除，其速度比 vector 快。
  • deque 对中间的元素插入与删除，其速度比 vector 慢。
  • vector 对于头部的插入与删除效率极低，数据量越大，效率越低。
  • vector 访问元素的速度会比 deque 快，这和两者的内部实现有关。

案例代码

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

using namespace std;

void printDeque(const deque<int> &d) {
    // 遍历容器
    for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    cout << "------ deque 大小操作 ------" << endl;

    deque<int> d1;
    d1.assign(5, 10);
    printDeque(d1);

    // 判断容器是否为空
    bool empty = d1.empty();
    cout << (empty ? "yes" : "no") << endl;

    // 获取容器中元素的个数
    size_t size = d1.size();
    cout << size << endl;

    // 重新指定容器的大小为 num，若容器变大，则以默认值（0）填充新位置。如果容器变小，则末尾超出容器大小的元素会被删除
    d1.resize(7);
    printDeque(d1);

    // 重新指定容器的大小为 num，若容器变大，则以指定值填充新位置。如果容器变小，则末尾超出容器大小的元素会被删除
    d1.resize(10, 8);
    printDeque(d1);

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

    deque<int> d2;
    d2.push_back(1);
    d2.push_back(2);
    d2.push_back(3);
    d2.push_back(4);
    d2.push_back(5);

    // 返回索引所指向的数据，如果索引越界，抛出 out_of_range 异常
    int num1 = d2.at(2);
    cout << "num1 = " << num1 << endl;

    // 返回索引所指向的数据，如果索引越界，程序终止运行
    int num2 = d2[3];
    cout << "num2 = " << num2 << endl;

    // 返回容器中第一个数据元素
    int font = d2.front();
    cout << "font = " << font << endl;

    // 返回容器中最后一个数据元素
    int back = d2.back();
    cout << "back = " << back << endl;

    cout << "------ deque 插入操作 ------" << endl;

    deque<int> d3(3, 8);
    printDeque(d3);

    // 往迭代器指向的位置插入指定的元素
    d3.insert(d3.begin(), 10);
    printDeque(d3);

    // 往迭代器指向的位置插入 n 个指定的元素
    d3.insert(d3.begin(), 2, 11);
    printDeque(d3);

    // 往迭代器指向的位置插入 [begin, end) 区间的数据
    deque<int> d4(2, 12);
    d3.insert(d3.begin(), d4.begin(), d4.end());
    printDeque(d3);

    // 在容器头部插入一个数据
    d4.push_front(13);
    printDeque(d4);

    // 在容器尾部添加一个数据
    d4.push_back(11);
    printDeque(d4);

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

    deque<int> d5;
    d5.push_back(1);
    d5.push_back(2);
    d5.push_back(3);
    d5.push_back(4);
    d5.push_back(5);
    d5.push_back(6);

    // 删除指定位置的数据，会返回下一个数据的位置
    d5.erase(d5.begin());
    printDeque(d5);

    // 删除容器第一个数据
    d5.pop_front();
    printDeque(d5);

    // 删除容器最后一个数据
    d5.pop_back();
    printDeque(d5);

    // 清空容器的所有数据
    d5.clear();

    return 0;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
------ deque 大小操作 ------
10 10 10 10 10 
no
5
10 10 10 10 10 0 0 
10 10 10 10 10 0 0 8 8 8 
------ deque 读取操作 ------
num1 = 3
num2 = 4
font = 1
back = 5
------ deque 插入操作 ------
8 8 8 
10 8 8 8 
11 11 10 8 8 8 
12 12 11 11 10 8 8 8 
13 12 12 
13 12 12 11 
------ deque 删除操作 ------
2 3 4 5 6 
3 4 5 6 
3 4 5

list

容器介绍

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

  • 声明

    • list<int> mylist;

  • 插入

    • mylist.push_back(20)，往尾部插入元素
    • mylist.push_front(20)，往头部插入元素
    • mylist.insert(iterator, 20)，往迭代器指向的位置插入元素

  • 删除

    • mylist.pop_back()，往尾部删除元素
    • mylist.pop_front()，往头部删除元素
    • mylist.erase(it)，删除迭代器指向的元素

  • 查询

    • iterator：迭代器遍历

链表的特性

  • 链表采用动态内存分配，不会造成内存浪费和溢出。
  • 链表虽然灵活，但是空间和时间的额外耗费较大。
  • 链表执行插入和删除操作都十分方便，仅修改指针即可实现，不需要移动大量元素。
  • 链表的访问效率比数组要低，适合需要频繁插入、删除元素的场景（读少写多）。
  • 链表不可以随机存取元素，所以不支持 at.(pos) 函数与 [] 操作符的使用。

案例代码

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

关联容器

无序关联容器

在 C++ 中，无序关联容器的底层数据结构都是链式哈希表（也称为哈希链表），常用的无序关联容器有：

  • unordered_set: 一个无序容器，存储唯一键值（不允许重复），基于链式哈希表实现，提供快速的插入、删除和查找操作。
  • unordered_multiset: 一个无序容器，存储键值（允许重复），基于链式哈希表实现，提供快速的多键插入、删除和查找操作。
  • unordered_map: 一个无序的键值对容器（键不允许重复），基于链式哈希表实现，键唯一且与对应的值关联，提供高效的键查找。
  • unordered_multimap: 一个无序的键值对容器（键允许重复），基于链式哈希表实现，允许多个键相同的键值对，提供快速的键查找和多值存储。

在 C++ 中，无序关联容器有以下的常用操作：

  • 插入

    • insert(val)，往容器插入元素

  • 删除

    • erase(val)，删除元素
    • erase(iterator)，删除迭代器指向的元素

  • 查询

    • iterator：迭代器遍历
    • for_each，循环遍历
    • for：循环遍历
    • find：查找元素

  • 其他

    • size()：获取容器中元素数量
    • count(val)：统计容器中某个元素的数量

unordered_set

案例代码

本节将演示 unordered_set 容器的简单使用。值得一提的是，unordered_multiset 容器的使用跟 unordered_set 容器类似，这里不再累述。

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

using namespace std;

int main() {
    // 设置随机种子
    srand(time(nullptr));

    // 存储唯一键值（不允许重复）的无序容器
    unordered_set<int> set1;

    // 插入元素
    for (int i = 0; i < 50; i++) {
        set1.insert(rand() % 20 + 1);
    }

    // 遍历容器
    for (auto it = set1.begin(); it != set1.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // 获取容器中的元素数量
    cout << set1.size() << endl;

    // 统计容器中元素是 5 的个数
    cout << set1.count(5) << endl;

    // 删除元素
    set1.erase(20);

    // 查找元素
    auto iterator = set1.find(15);
    if (iterator != set1.end()) {
        cout << "find item : " << *iterator << endl;
    } else {
        cout << "not find item" << endl;
    }

    // 循环遍历
    for (int i: set1) {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

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

1
2
3
4
5
16 8 12 18 20 15 13 9 2 7 19 1 10 6 17 3 14 4 5 
19
1
find item : 15
16 8 12 18 15 13 9 2 7 19 1 10 6 17 3 14 4 5

unordered_map

案例代码

本节将演示 unordered_map 容器的简单使用。值得一提的是，unordered_multimap 容器的使用跟 unordered_map 容器类似，这里不再累述。

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
#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main() {
    // 设置随机种子
    srand(time(nullptr));

    // 无序的键值对容器（键不允许重复）
    unordered_map<int, string> map1;

    // 插入键值对
    map1.insert(make_pair(1001, "Tom"));
    map1.insert(make_pair(1002, "Peter"));
    map1.insert(make_pair(1003, "David"));

    // 获取指定键的值，如果 key 不存在，会自动插入一个键值对 [key, string()]
    cout << map1[1002] << endl;

    // 插入或者修改操作
    map1[1004] = "Jim";

    // 获取容器中键值对的数量
    cout << map1.size() << endl;

    // 删除指定的键
    map1.erase(1003);

    // 查找
    auto iterator = map1.find(1001);
    if (iterator != map1.end()) {
        // 获取 key 和 value
        cout << "finded, key: " << iterator->first << ", value: " << iterator->second << endl;
    } else {
        cout << "not finded" << endl;
    }

    // 遍历容器
    for (auto it = map1.begin(); it != map1.end(); ++it) {
        // 获取 key 和 value
        cout << "key: " << it->first << ", value: " << it->second << endl;
    }
    cout << endl;

    return 0;
}

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

1
2
3
4
5
6
Peter
4
finded, key: 1001, value: Tom
key: 1004, value: Jim
key: 1002, value: Peter
key: 1001, value: Tom

有序关联容器

在 C++ 中，有序关联容器的底层数据结构都是红黑树（一种平衡二叉搜索树），常用的有序关联容器有：

  • set: 一个有序容器，存储唯一键值（不允许重复），基于红黑树实现，提供高效的元素插入、删除和有序遍历。
  • multiset: 一个有序容器，存储键值（允许重复），基于红黑树实现，支持多键插入和有序遍历。
  • map: 一个有序的键值对容器（键不允许重复），基于红黑树实现，键唯一且与对应的值关联，支持高效查找和有序遍历。
  • multimap: 一个有序的键值对容器（键允许重复），基于红黑树实现，允许键重复，支持多键查找和有序存储。

set

本节将演示 set 容器的简单使用。值得一提的是，multiset 容器的使用跟 set 容器类似，这里不再累述。

案例代码一
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
#include <iostream>
#include <set>

using namespace std;

int main() {
    // 设置随机种子
    srand(time(nullptr));

    // 存储唯一键值（不允许重复）的有序容器
    set<int> set1;

    // 插入元素
    for (int i = 0; i < 20; i++) {
        set1.insert(rand() % 100 + 1);
    }

    // 遍历容器
    for (auto it = set1.begin(); it != set1.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // 获取容器中的元素数量
    cout << set1.size() << endl;

    // 统计容器中元素是 5 的个数
    cout << set1.count(5) << endl;

    // 删除元素
    set1.erase(20);

    // 查找元素
    auto iterator = set1.find(15);
    if (iterator != set1.end()) {
        cout << "find item : " << *iterator << endl;
    } else {
        cout << "not find item" << endl;
    }

    // 循环遍历
    for (int i: set1) {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

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

1
2
3
4
5
5 21 22 26 27 36 39 41 51 55 60 67 81 89 90 91 94 96 
18
1
not find item
5 21 22 26 27 36 39 41 51 55 60 67 81 89 90 91 94 96
案例代码二
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
#include <iostream>
#include <set>
#include <string>

using namespace std;

// 自定义数据类型
class Student {

public:
    Student(long id, string name) : _id(id), _name(name) {

    }

    // 由于 set 容器是有序的，因此自定义类型都需要重载小于运算符，否则 set 容器将不知道如何对自定义类型进行排序
    bool operator<(const Student &other) const {
        return this->_id < other._id;
    }

    friend ostream &operator<<(ostream &out, const Student &student);

private :
    long _id;
    string _name;

};

ostream &operator<<(ostream &out, const Student &student) {
    cout << "id: " << student._id << ", name: " << student._name;
    return out;
}

int main() {
    // 存储唯一键值（不允许重复）的有序容器
    set<Student> set1;

    // 插入元素
    set1.insert(Student(1001, "Tom"));
    set1.insert(Student(1002, "Jim"));
    set1.insert(Student(1003, "Peter"));

    // 遍历容器
    for (auto it = set1.begin(); it != set1.end(); ++it) {
        cout << *it << endl;
    }

    return 0;
}

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

1
2
3
id: 1001, name: Tom
id: 1002, name: Jim
id: 1003, name: Peter

map

本节将演示 map 容器的简单使用。值得一提的是，multimap 容器的使用跟 map 容器类似，这里不再累述。

案例代码一
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
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
    // 设置随机种子
    srand(time(nullptr));

    // 有序的键值对容器（键不允许重复）
    map<int, string> map1;

    // 插入键值对
    map1.insert(make_pair(1001, "Tom"));
    map1.insert(make_pair(1002, "Peter"));
    map1.insert(make_pair(1003, "David"));

    // 获取指定键的值，如果 key 不存在，会自动插入一个键值对 [key, string()]
    cout << map1[1002] << endl;

    // 插入或者修改操作
    map1[1004] = "Jim";

    // 获取容器中键值对的数量
    cout << map1.size() << endl;

    // 删除指定的键
    map1.erase(1003);

    // 查找
    auto iterator = map1.find(1001);
    if (iterator != map1.end()) {
        // 获取 key 和 value
        cout << "finded, key: " << iterator->first << ", value: " << iterator->second << endl;
    } else {
        cout << "not finded" << endl;
    }

    // 遍历容器
    for (auto it = map1.begin(); it != map1.end(); ++it) {
        // 获取 key 和 value
        cout << "key: " << it->first << ", value: " << it->second << endl;
    }
    cout << endl;

    return 0;
}

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

1
2
3
4
5
6
Peter
4
finded, key: 1001, value: Tom
key: 1001, value: Tom
key: 1002, value: Peter
key: 1004, value: Jim
案例代码二
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
#include <iostream>
#include <string>
#include <map>

using namespace std;

// 自定义数据类型
class Student {

public:

    // 默认构造函数
    Student() {
        this->_id = 0;
        this->_name = "";
    }

    Student(long id, string name) : _id(id), _name(name) {

    }

    friend ostream &operator<<(ostream &out, const Student &student);

private :
    long _id;
    string _name;

};

ostream &operator<<(ostream &out, const Student &student) {
    cout << "id: " << student._id << ", name: " << student._name;
    return out;
}

int main() {
    // 有序的键值对容器（键不允许重复）
    map<int, Student> map1;

    // 插入键值对
    map1.insert({1001, Student(1001, "Jim")});
    map1.insert({1002, Student(1002, "Peter")});
    map1.insert({1003, Student(1003, "David")});

    // 获取指定键的值，如果 key 不存在，会自动插入一个键值对 [key, Student()]，这需要自定义的数据类型提供默认构造函数
    cout << map1[1002] << endl;

    // 遍历容器
    for (auto it = map1.begin(); it != map1.end(); ++it) {
        // 获取 key 和 value
        cout << "key: " << it->first << ", value: " << it->second << endl;
    }
    cout << endl;

    return 0;
}

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

1
2
3
4
id: 1002, name: Peter
key: 1001, value: id: 1001, name: Jim
key: 1002, value: id: 1002, name: Peter
key: 1003, value: id: 1003, name: David

容器适配器

在 C++ 中，常用的容器适配器有：

  • stack: 一个遵循后进先出（LIFO）原则的容器适配器，底层默认是基于 deque 实现，也可以使用 vector 或 list 替代底层容器，支持在栈顶插入、删除和访问元素的操作。
  • queue: 一个遵循先进先出（FIFO）原则的容器适配器，底层默认是基于 deque 实现，支持在队尾插入元素和在队头移除、访问元素的操作。
  • priority_queue: 一个基于堆实现的容器适配器（即优先级队列），底层默认使用 vector 作为容器存储，借助堆算法按优先级（默认大顶堆）访问最高优先级的元素。

容器迭代器的特点

  • 容器适配器没有自己的迭代器。
  • 容器适配器的底层没有自己的数据机构，它本质是另外一个容器的封装，它的函数全部由底层依赖的容器来实现。

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

using namespace std;

int main() {
    // 设置随机种子
    srand(time(nullptr));

    // 栈（后进先出 - LIFO）
    stack<int> s1;

    for (int i = 0; i < 20; i++) {
        int item = rand() % 100 + 1;
        // 入栈
        s1.push(item);
        cout << item << " ";
    }
    cout << endl;

    // 返回栈的元素个数
    cout << "size: " << s1.size() << endl;

    // 判断栈是否为空
    while (!s1.empty()) {
        // 获取栈顶元素
        cout << s1.top() << " ";
        // 弹栈
        s1.pop();
    }

    return 0;
}

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

1
2
3
10 80 23 89 30 85 6 58 5 67 32 98 13 65 42 60 75 85 77 57 
size: 20
57 77 85 75 60 42 65 13 98 32 67 5 58 6 85 30 89 23 80 10

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

using namespace std;

int main() {
    // 设置随机种子
    srand(time(nullptr));

    // 队列（先进先出 - FIFO）
    queue<int> q1;

    for (int i = 0; i < 20; i++) {
        int item = rand() % 100 + 1;
        // 入队
        q1.push(item);
        cout << item << " ";
    }
    cout << endl;

    // 返回队列的元素个数
    cout << "size: " << q1.size() << endl;

    // 判断队列是否为空
    while (!q1.empty()) {
        // 获取队头元素
        cout << q1.front() << " ";
        // 出队
        q1.pop();
    }

    return 0;
}

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

1
2
3
14 45 87 90 95 32 66 27 9 92 96 88 93 68 72 55 42 37 35 64 
size: 20
14 45 87 90 95 32 66 27 9 92 96 88 93 68 72 55 42 37 35 64

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

using namespace std;

int main() {
    // 设置随机种子
    srand(time(nullptr));

    // 优先级队列
    priority_queue<int> pque;

    for (int i = 0; i < 20; i++) {
        int item = rand() % 100 + 1;
        // 入队
        pque.push(item);
        cout << item << " ";
    }
    cout << endl;

    // 返回队列的元素个数
    cout << "size: " << pque.size() << endl;

    // 判断队列是否为空
    while (!pque.empty()) {
        // 获取队头元素
        cout << pque.top() << " ";
        // 出队
        pque.pop();
    }

    return 0;
}

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

1
2
3
85 32 2 2 38 96 10 2 83 34 1 64 19 90 64 20 6 81 100 47 
size: 20
100 96 90 85 83 81 64 64 47 38 34 32 20 19 10 6 2 2 2 1