C++ 进阶基础之七

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

大纲

vector 容器

vector 容器的概念

vector 的数据存储以及操作方式，与 Array 非常相似，两者的唯一差别在于空间运用的灵活性。Array 是静态空间，一旦配置了就不能改变，要换大一点或者小一点的空间，可以，一切琐碎的细节得由自己来实现；首先配置一块新的空间，然后将旧空间的数据搬往新空间，再释放原来的空间。Vector 是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新元素。因此 vector 的运用对于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必害怕空间不足而一开始就初始化一个大的 Array 了。Vector 的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率，一旦 vector 旧空间满了，如果客户每新增一个元素 vector 内部只是扩充一个元素的空间，实为不智，因为所谓的扩充空间（不论多大），一如刚所说，是 “配置新空间 - 数据移动 - 释放旧空间” 的大工程，时间成本很高，应该加入某种未雨绸缪的考虑。

vector 容器的数据结构

vector 所采用的数据结构是线性连续空间（单向开口的连续内存空间），它以两个迭代器（_Myfirst 和 _Mylast）分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器 _Myend 指向整块连续内存空间的尾端。vector 往尾部添加或移除元素的效率非常高，但是往头部或者中部插入元素或移除元素则比较费时。为了降低空间配置时的速度成本，vector 实际配置的大小可能比客户端需求大一些，以应付将来可能的扩充，这里是容量的概念。换句话说，一个 vector 的容量永远大于或等于其大小，一旦容量等于大小，便是满载，下次再需要新增元素时，整个 vector 容器就得另觅居所。值得一提的是，所谓动态增加大小，并不是在原空间之后续接新空间（因为无法保证原空间之后尚有可配置的空间），而是申请一块更大的内存空间，然后将原数据拷贝到新空间，并释放原空间。因此，对 vector 的任何操作，一旦引起空间的重新配置，指向原 vector 的所有迭代器就都失效了，这是程序容易出错的地方，务必小心。

vector 容器的迭代器

vector 维护了一个线性空间，所以不论元素的类型是什么，普通指针都可以作为 vector 的迭代器，因为 vector 迭代器所需要的操作行为，如 operaroe*, operator->, operator++, operator--, operator+, operator-, operator+=, operator-= 都是普通指针天生具备的。vector 支持随机存取，而普通指针正有着这样的能力，所以 vector 提供的是随机访问迭代器（Random Access Iterators），支持随机存取元素。根据前面的描述，可以写如下的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<vector>

using namespace std;

int main() {
    // 声明容器
    vector<int> v1;

    // 插入容器数据
    for (int i = 0; i < 10; i++) {
        v1.push_back(i);
        cout << i << " ";
    }

    cout << endl;

    // vector 的迭代器是随机访问迭代器，支持跳跃式访问（随机存取元素）
    vector<int>::iterator itBegin = v1.begin();
    itBegin = itBegin + 2;
    cout << *itBegin << endl;

    return 0;
}

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

1
2
0 1 2 3 4 5 6 7 8 9 
2

vector 容器的使用

vector 的构造与赋值

1
2
3
4
vector<T> v;                        // 默认构造函数，采用模板实现类实现
vector(v.begin(), v.end());         // 有参构造函数，将 v[begin(), end()] 区间中的元素拷贝给本身
vector(n, elem);                    // 有参构造函数，将 n 个 elem 元素拷贝给本身
vector(const vector &vec);          // 拷贝构造函数
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
#include <iostream>
#include<vector>

using namespace std;

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

int main() {
    int arr[] = {1, 2, 3, 4, 5};

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

    // 默认构造函数
    vector<int> v1;

    // 有参构造函数，将 v[begin(), end()] 区间中的元素拷贝给本身
    vector<int> v2(arr, arr + sizeof(arr) / sizeof(int));
    printVector(v2);

    // 有参构造函数，将 v[begin(), end()] 区间中的元素拷贝给本身
    vector<int> v3(v2.begin(), v2.end());
    printVector(v3);

    // 有参构造函数，将 n 个 elem 元素拷贝给本身
    vector<int> v4(5, 10);
    printVector(v4);

    // 拷贝构造函数
    vector<int> v5 = v4;
    printVector(v5);

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

    // 赋值操作，将 v[begin(), end()] 区间中的元素拷贝给本身
    vector<int> v6;
    v6.assign(v5.begin(), v5.end());
    printVector(v6);

    // 赋值操作，将 n 个 elem 元素拷贝给本身
    vector<int> v7;
    v7.assign(5, 8);
    printVector(v7);

    // 赋值操作，重载等号操作符
    vector<int> v8;
    v8 = v6;
    printVector(v8);

    // 赋值操作，将其他容器与本身的元素互换，利用 swap() 可以收缩空间
    v8.swap(v7);
    printVector(v8);

    return 0;
}

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

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

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

using namespace std;

void printVector(vector<int> &v) {
    // 遍历vector
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    vector<int> v1;
    v1.assign(5, 10);

    cout << "------ vector 大小、容量操作 ------" << endl;

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

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

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

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

    // 获取容器的容量
    size_t capacity = v1.capacity();
    cout << "capacity = " << capacity << endl;

    cout << "------ vector 数据读取操作 ------" << endl;

    vector<int> v2;
    v2.push_back(3);
    v2.push_back(6);
    v2.push_back(9);
    v2.push_back(12);
    v2.push_back(15);

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

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

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

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

    cout << "------ vector 插入和删除操作 ------" << endl;

    // 往迭代器指向的位置插入 n 个指定的元素，其中元素个数可以省略
    vector<int> v3(5, 8);
    v3.insert(v3.begin(), 2, 10);
    printVector(v3);

    // 往容器的尾部插入元素
    v3.push_back(11);
    printVector(v3);

    // 删除最后一个元素
    v3.pop_back();
    printVector(v3);

    // 删除迭代器指向的元素，迭代器就是指针
    v3.erase(v3.begin());
    printVector(v3);

    // 删除迭代器从 start 到 end 之间的元素
    v3.erase(v3.begin(), v3.end());
    if (v3.empty()) {
        cout << "vector is empty" << endl;
    }

    // 删除容器中的所有元素
    v3.clear();

    return 0;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
------ vector 大小、容量操作 ------
size = 5
true
10 10 10 10 10 0 0 
10 10 10 10 10 0 0 8 8 8 
capacity = 10
------ vector 数据存取操作 ------
num1 = 6
num2 = 12
font = 3
back = 15
------ vector 插入和删除操作 ------
10 10 8 8 8 8 8 
10 10 8 8 8 8 8 11 
10 10 8 8 8 8 8 
10 8 8 8 8 8 
vector is empty

vector 逆序遍历

容器迭代器的类型：

  • iterator：普通迭代器
  • const_iterator：只读迭代器
  • reverse_iterator：逆序迭代器
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
#include<iostream>
#include<vector>

using namespace std;

int main() {
    vector<int> v1;
    for (int i = 0; i < 10; i++) {
        v1.push_back(i);
    }

    // 顺序遍历容器
    for (vector<int>::iterator it = v1.begin(); it != v1.end(); it++) {
        cout << *it << " ";
    }

    cout << endl;

    // 逆序遍历容器（使用逆序迭代器）
    for (vector<int>::reverse_iterator it = v1.rbegin(); it != v1.rend(); it++) {
        cout << *it << " ";
    }

    cout << endl;

    // vector 的迭代器是随机访问迭代器，支持跳跃式访问
    vector<int>::iterator itBegin = v1.begin();
    itBegin = itBegin + 2;
    cout << *itBegin << endl;

    return 0;
}

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

1
2
3
0 1 2 3 4 5 6 7 8 9 
9 8 7 6 5 4 3 2 1 0 
2

vector 收缩空间

结合 C++ 的匿名对象和 vector 容器的 swap() 函数，可以实现收缩 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() {
    vector<int> v1;

    // 插入容器数据
    for (int i = 0; i < 100000; i++) {
        v1.push_back(i);
    }

    cout << "size = " << v1.size() << endl;
    cout << "capacity = " << v1.capacity() << endl;

    // 重新指定容器的大小，此时容器的容量不会改变
    v1.resize(5);
    cout << "size = " << v1.size() << endl;
    cout << "capacity = " << v1.capacity() << endl;

    // 巧用匿名对象和 swap() 函数收缩 vector 容器的空间
    vector<int>(v1).swap(v1);
    cout << "size = " << v1.size() << endl;
    cout << "capacity = " << v1.capacity() << endl;

    return 0;
}

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

1
2
3
4
5
6
size = 100000
capacity = 131072
size = 5
capacity = 131072
size = 5
capacity = 5

vector 预留空间

reserve() 函数可以让 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
29
30
31
32
33
34
35
36
#include<iostream>
#include<vector>

using namespace std;

void initData(vector<int> &v, size_t size, bool reserve) {
    // 预留空间
    if (reserve) {
        v.reserve(size);
    }

    int count = 0;
    int *pStart = NULL;
    for (int i = 0; i < size; i++) {
        // 插入容器数据
        v.push_back(i);
        // 统计容器改变容量的次数
        if (pStart != &v[0]) {
            pStart = &v[0];
            count++;
        }
    }
    cout << "count : " << count << endl;
}

int main() {
    // 不申请预览空间
    vector<int> v1;
    initData(v1, 100000, false);

    // 申请预览空间
    vector<int> v2;
    initData(v2, 100000, true);

    return 0;
}

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

1
2
count : 18
count : 1

deque 容器

deque 容器的概念

vector 是单向开口的连续线性空间，而 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 使用的是分段连续内存空间，那么就必须有中央控制器，维持其整体连续的假象，这样也导致了数据结构的设计及迭代器的前进后退操作颇为繁琐，deque 底层实现的代码远比 vector 或 list 都多得多。

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

deque 与 vector 的区别

  • vector 对于头部的插入效率极低，数据量越大，效率越低
  • deque 相对而言，对头部的元素插入、删除速度会比 vector 快
  • vector 访问元素时的速度会比 deque 快，这和两者的内部实现有关

deque 容器的使用

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
#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;

    // 有参构造函数，将 n 个 elem 元素拷贝给本身
    deque<int> d2(5, 10);
    printDeque(d2);

    // 有参构造函数，将 d[begin(), end()] 区间中的元素拷贝给本身
    deque<int> d3(d2.begin(), d2.end());
    printDeque(d3);

    // 拷贝构造函
    deque<int> d4 = d3;
    printDeque(d4);

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

    // 赋值操作，重载等号操作符
    deque<int> d5;
    d5 = d4;
    printDeque(d5);

    // 赋值操作，将 d[begin(), end()] 区间中的元素拷贝给本身
    deque<int> d6;
    d6.assign(d5.begin(), d5.end());
    printDeque(d6);

    // 赋值操作，将 n 个 elem 元素拷贝给本身
    deque<int> d7;
    d7.assign(5, 8);
    printDeque(d7);

    // 赋值操作，将其他容器与本身的元素互换
    d7.swap(d6);
    printDeque(d7);

    return 0;
}

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

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

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

deque 的排序操作

利用算法可以对 deque 容器进行排序，但需要引入头文件 algorithm。对于支持随机访问的迭代器的容器，都可以利用 sort() 排序，vector 容器也可以用 sort() 排序。

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

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;
}

bool descCompare(const int a, const int b) {
    return a > b;
}

void asc() {
    deque<int> d1;
    d1.push_back(3);
    d1.push_back(11);
    d1.push_back(8);
    d1.push_back(6);
    d1.push_back(21);

    cout << "升序排序前：" << endl;
    printDeque(d1);

    // 升序排序，默认从小到大排序
    sort(d1.begin(), d1.end());

    cout << "升序排序后：" << endl;
    printDeque(d1);
}

void desc() {
    deque<int> d1;
    d1.push_back(3);
    d1.push_back(11);
    d1.push_back(8);
    d1.push_back(6);
    d1.push_back(21);

    cout << "降序排序前：" << endl;
    printDeque(d1);

    // 降序排序，默认从大到小排序
    sort(d1.begin(), d1.end(), descCompare);

    cout << "降序排序后：" << endl;
    printDeque(d1);
}


int main() {
    asc();  // 升序排序
    cout << endl;
    desc(); // 降序排序后
    return 0;
}

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

1
2
3
4
5
6
7
8
9
升序排序前：
3 11 8 6 21 
升序排序后：
3 6 8 11 21 

降序排序前：
3 11 8 6 21 
降序排序后：
21 11 8 6 3