-
Vector 模拟实现
前言
本文将会向您介绍如何模拟实现vector
引入
Vector是一种动态数组，也是C++标准库中的容器之一。它提供了一种存储和操作一系列元素的方式，类似于数组，但具有更多的功能和灵活性。
Vector可以存储不同类型的元素，并且可以根据需要动态调整大小。它使用连续的内存块来存储元素，使得元素的访问和遍历效率较高。与普通数组相比，Vector的大小可以动态增长或缩小，而不需要手动编写代码来重新分配内存。
Vector提供了一系列的成员函数和操作符，可以方便地进行元素的插入、删除、访问和修改等操作。它还支持迭代器，可以通过迭代器遍历Vector中的元素。
功能分解
构造
提供了一个默认的构造，和一个n个value的构造
//构造 vector() { } //构造 vector(int n, const T& value = T()) { reserve(n); for (int i = 0; i < n; i++) { push_back(value); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
拷贝构造
解析：假设用v1拷贝v2，v是v1的别名，将v的内容尾插到v2中
//v2(v1) vector(const vector<T>& v) { reserve(v.capacity()); for (auto& e : v) { push_back(e); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
赋值重载
void swap(vector<T>& v) { std::swap(start, v.start); std::swap(finish, v.finish); std::swap(end_of_storage, v.end_of_storage); } vector<T>& operator= (vector<T> v) { swap(v); return *this; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
析构
~vector() { delete[] start; start = finish = end_of_storage = nullptr; }- 1
- 2
- 3
- 4
- 5
迭代器
Vector源代码中使用了start、finish、endofstorage三个指针
start指针指向vector中的第一个元素的位置。
finish指针指向vector中最后一个元素的下一个位置。也就是说，finish指针指向vector中当前元素的末尾位置。tips：[start , finish)
endofstorage指针指向vector内部分配的内存空间的末尾位置。这个指针通常用于判断vector是否需要重新分配内存空间。iterator begin() { return start; } iterator end() { return finish; } const_iterator begin() const { return start; } const_iterator end() const { return finish; } //获取大小 size_t size() const { return finish - start; } //获取容量 size_t capacity() const { return end_of_storage - start; }- 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
尾插：当size与capacity相等时，就需要进行扩容。
以下一个步骤相当于扩容，当尾插需要扩容时，对capacity进行修改
而reserve只是完成扩容的剩下步骤（拷贝空间到新空间，释放旧空间，更新指针指向的位置）reserve(capacity() == 0 ? 4 : capacity() * 2);- 1
当capacity为0时，赋值4，当capcaity不为0时capacity*2作为参数给reserve
void push_back(const T& x) { if (size() == capacity()) { //扩容 reserve(capacity() == 0 ? 4 : capacity() * 2); } //插入数据 *finish = x; finish ++; //复用 //insert(end(), x); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
Reserve
开空间：
场景一：当尾插size与capacity相等时，n接收应需要扩容的大小
开辟一个新空间T* tmp = new T[n];- 1
如果start不为空，就需要把原来空间里的内容拷贝到新空间里，然后在再释放旧空间
if (start) { }- 1
- 2
- 3
void reserve(size_t n) { size_t sz = size(); //开空间 if (n > capacity()) { T* tmp = new T[n]; //如果start不为空就要拷贝就空间 //memcpy(tmp, start, sizeof(T) * sz); if (start) { for (int i = 0; i < sz; i++) { tmp[i] = start[i]; } delete[] start; } //更新 start = tmp; finish = start + sz; end_of_storage = start + n; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
注意：
在更新指针指向的空间时，这里需要提前保存size的大小
不能按如下写法finish = start + size();- 1
当还没有插入数据时，start应与finish指向的位置相同位于起始位置0处，size( )应为0.但是size（）不为0，size = finish - start 旧空间的finish - 新空间的start(tmp)
Resize
改变大小： n的可能有两种情况，第一是n <= size，直接改变finish指向的位置即可
第二时n > size，需要进行扩容，并且插入Value值const T& value = T()- 1
//改变大小 void resize(size_t n, const T& value = T()) { if (n <= size()) { finish = start + n; } else { reserve(n); while(size_t(finish - start) < n) { *finish = value; ++finish; } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
Insert
在任意位置pos处插入：
判断有效位置、判断扩容、挪动数据、插入数据
以上步骤的逻辑较为简单不再讲解
注意：
必须要记录pos的相对位置，再对pos进行更新
否则：pos指向要插入的位置，如果扩容后，会将旧空间释放掉，其中包括pos指向的位置，这样一来pos就变成野指针，解引用插入数据的时候就会有问题size_t len = pos - start; reserve(capacity() == 0 ? 4 : capacity() * 2); pos = start + len;- 1
- 2
- 3
iterator insert(iterator pos, const T& x) { //判断有效位置 assert(pos >= start); assert(pos <= finish); //判断扩容 if (size() == capacity()) { //pos失效 size_t len = pos - start; reserve(capacity() == 0 ? 4 : capacity() * 2); pos = start + len; } //挪动数据 T* end = finish - 1; while (end >= pos) { *(end + 1) = *end; end--; } *pos = x; finish++; return start; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
另外当我们进行以下测试的时候会出现以下错误
原因是：
当我们向一个vector中插入元素时，pos是it的拷贝，虽然我们在insert中对pos进行修正，但是pos的修改并不会影响到it迭代器，这种情况下，原有的迭代器指向的内存地址已经不再有效，因此不能再使用。void test3() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vector<int>::iterator it = v.begin() + 2; v.insert(it, 30); for (auto e : v) { cout << e << " "; } cout << endl; v.insert(it, 20); for (auto e : v) { cout << e << " "; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
Erase
删除：判断有效位置、覆盖数据，最后 - -finish
以上步骤较为简单，就不在这里进行讲解iterator erase(iterator pos) { //判断有效位置 assert(pos >= start); assert(pos < finish); iterator end = pos + 1; while (end < finish) { *(end - 1) = *end; end++; } finish--; return start; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
注意：
当我们测试以下数据并且想erase掉偶数
我们像以下写法使用迭代器还会导致像insert时迭代器失效一样的问题吗
答案是：会的while (it != v3.end()) { if (*it % 2 == 0) { v3.erase(it); } it++; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
测试数据：1 2 2 3 4 5
我们可以观察到，此时并没有erase掉偶数
原因是 it 指向第一个2的位置，当我们erase移动覆盖第一个2时，此时 第二个2就跑到了it指向的位置，然后再++it，本来应对第二个2进行判断的时候，却直接跳过了
测试数据：1，2，3，4，5，6
VS有个特点：erase后不让再使用迭代器，进行了强制检查
当我们erase最后一个偶数时，finish–，然后it++，这会导致it != v3.end()直接失效
C++库也给出了解决方案
返回被删除数据的下一个位置，我们只需要接收这个位置即可
void test_vector3() { vector<int> v3; v3.push_back(1); v3.push_back(2); v3.push_back(2); v3.push_back(3); v3.push_back(4); v3.push_back(5); v3.push_back(6); for (auto e : v3) { cout << e << " "; } cout << endl; Fan::vector<int>::iterator it = v3.begin(); while (it != v3.end()) { if (*it % 2 == 0) { it = v3.erase(it); } else { it++; } } for (auto e : v3) { cout << e << " "; } }- 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
测试用例
//void test_vector1() //{ // vectorv1; // v1.push_back(1); // v1.push_back(2); // v1.push_back(3); // v1.push_back(4); // v1.push_back(5); // v1.insert(v1.begin() + 3, 1); // v1.insert(v1.begin(), 0); // v1.insert(v1.end(), 1); // Fan::vector::iterator it = v1.begin(); // while (it != v1.end()) // { // cout <<" "<< * it; // ++it; // } //} //void test_vector2() //{ // vectorv2; // v2.push_back(1); // v2.push_back(2); // v2.push_back(3); // v2.push_back(4); // v2.push_back(5); // v2.push_back(6); // v2.push_back(7); // for (auto e : v2) // { // cout << e << " "; // } // cout << endl; // v2.erase(v2.begin() + 1); // v2.erase(v2.begin() + 1); // for (auto e : v2) // { // cout << e << " "; // } //} //void test_vector3() //{ // vectorv3; // v3.push_back(1); // v3.push_back(2); // v3.push_back(2); // v3.push_back(3); // v3.push_back(4); // v3.push_back(5); // v3.push_back(6); // for (auto e : v3) // { // cout << e << " "; // } // cout << endl; // Fan::vector::iterator it = v3.begin(); // while (it != v3.end()) // { // if (*it % 2 == 0) // { // it = v3.erase(it); // } // else // { // it++; // } // } // for (auto e : v3) // { // cout << e << " "; // } //} //void test_vector4() //{ // vectorv4; // v4.push_back(1); // v4.push_back(2); // v4.push_back(2); // v4.push_back(3); // v4.push_back(4); // v4.push_back(5); // v4.push_back(6); // for (auto e : v4) // { // cout << e << " "; // } // v4.pop_back(); // cout << endl; // for (auto e : v4) // { // cout << e << " "; // } // cout << endl; // cout << v4[1]; //} //void test_vector5() //{ // vectorv5; // v5.push_back(1); // v5.push_back(2); // v5.push_back(2); // v5.push_back(3); // v5.push_back(4); // vectorv6; // v6 = v5; // for (auto e : v6) // { // cout << e << " "; // } //} //void test_vector6() //{ // vectorv6; // v6.push_back("1111111111111111111"); // v6.push_back("1111111111111111111"); // v6.push_back("1111111111111111111"); // v6.push_back("1111111111111111111"); // v6.push_back("1111111111111111111"); // v6.push_back("1111111111111111111"); // v6.push_back("1111111111111111111"); // v6.push_back("1111111111111111111"); // v6.push_back("1111111111111111111"); // v6.push_back("1111111111111111111"); // for (auto e : v6) // { // cout << e << " "; // } //} //void test_vector7() //{ // vectorv2; // v2.resize(10, "xxx"); // for (auto e : v1) // { // cout << e << " "; // } // cout << endl; // for (auto e : v2) // { // cout << e << " "; // } //} //void test_vector8() //{ // vectorv1; // v1.resize(10, "xxx"); // vectorv2(v1); // for (auto e : v2) // { // cout << e << " "; // } // cout << endl; // vectorv3(v2.begin(), v2.end()); // for (auto e : v3) // { // cout << e << " "; // } //} int main() { //test_vector1(); //test_vector2(); //test_vector3(); //test_vector4(); //test_vector5(); //test_vector6(); //test_vector7(); //test_vector8(); 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
- 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
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
小结
关于本文Vector代码已经上传到gitee了，如果本文存在遗漏或错误的的地方，还请您能够指出。
-
相关阅读:
【牛客-剑指offer-数据结构篇】JZ32 从上往下打印二叉树 Java实现
使用vite+react搭建项目踩坑记录
泓博医药开启申购：预计上市时市值约31亿元，高瓴资本为其股东
查看电脑jdk/jre版本以及安装路径并测试是否可以正常使用（检查运行环境）
基于MOOC的FPGA硬件类课程远程实验教学平台设计
Stretched mesh
解释器模式
Mybatis简介
会员营销中,沉寂会员的三种运营策略
LeetCode每日一题(1441. Build an Array With Stack Operations)
- 原文地址：https://blog.csdn.net/Moonnight_bit/article/details/132915601
