目录
一，准备工作
二，push_back
1， 关于引用
2. 参数const 的修饰
补充
三，迭代器实现
四，Pop_back
五，insert
1. 补充——迭代器失效
六， erase
七，构造函数
1. 迭代器构造
2. 其他构造
3. 拷贝构造
1） 传统写法
2）现代写法（提高函数复用性）
八，赋值符号重载
九，resize
![[STL] vector 模拟实现详解,C++——从入门到入土，安排！,c++,开发语言,学习,windows,算法](https://imgs.yssmx.com/Uploads/2023/07/595014-1.jpeg)
一，准备工作
准备工作中，需要前面所学的，命名空间 , 类模板知识，以及我们实现之前需要借鉴一下STL源代码如何实现。
开始实现前，我们先熟悉一下vector 的框架：
![[STL] vector 模拟实现详解,C++——从入门到入土，安排！,c++,开发语言,学习,windows,算法](https://imgs.yssmx.com/Uploads/2023/07/595014-2.png)
// 头文件
#include <iostream>
#include <vector>
using namespace std;
namespace my_vector // 里面我们使用的类也叫vector，命名空间隔离，避免与STL中的vector命名重复
{
template <class T> // 这里缺了内存池的模板，后面再学习
class vector
{
typedef T* iterator; // vector在物理空间上是一段连续的空间，所有这里的迭代器就是指针
public:
private:
iterator _start; // 迭代器开始位置
iterator _finish; // 当前迭代器指向位置，相当于size
iterator end_of_storage; // 该段迭代器的最终位置
};
}
// 测试文件///
#include "my_vector.h"
int main()
{
my_vector::vector<int> p1; // 使用自己的vector需要进行标识命名空间，否则用的就是STL中vector
return 0;
}二，push_back
void push_back(const T& data) // 这里有关 两个问题的探讨，1. const 修饰； 2. 引用
{
}这里有我们需要探讨的两个点： 1. 参数 const 修饰 ； 2. 关于引用
先讲关于引用
1， 关于引用
我们的数据是int, char还好，我们不使用引用，值拷贝也不太差， 但我们的参数是 string类，vector<T>等等，这时string就是深拷贝，性能浪费太大。因此，这里选择引用。
2. 参数const 的修饰
我们看下面场景
int main()
{
my_vector::vector<int> p1; // 使用自己的vector需要进行标识命名空间，否则用的就是STL中的vector
// 场景一：参数是 变量对象
int a = 10;
p1.push_back(a); // ok的
// 场景二：参数是临时变量，或者匿名对象
p1.push_back(10); // 挪,没有const 修饰，无法接收临时数据
my_vector::vector<string> p2;
p2.push_back(string("xxxxx"));
return 0;
} ![[STL] vector 模拟实现详解,C++——从入门到入土，安排！,c++,开发语言,学习,windows,算法](https://imgs.yssmx.com/Uploads/2023/07/595014-3.png)
结论： 1. 为了保证面对各种数据类型，vector都能有比较高的性能，引用是需要的； 2. 对数据进行const 修饰 能提高对数据的兼容。
这里是push_back + operator[] 的实现代码：
size_t size() const // 针对被const修饰的对象，使其兼容
{
return _finish - _start;
}
size_t capacity() const
{
return end_of_storage - _start;
}
void reserve(size_t n)
{
if (n > capacity())
{
T* new_start = new T[n];
if (_start) // 如果旧空间不是空，则需要拷贝备份
{
// memcpy(new_start, _start, sizeof(T) * size()); 为啥不直接选择memcopy
// 这里需要重点讲解
for (size_t i = 0; i < n; i++)
{
new_start[i] = _start[i]; // 如果是自定义类型，则会调用其operator
}
delete[] _start;
}
_finish = new_start + size();
_start = new_start;
end_of_storage = new_start + n;
}
}
T& operator[](size_t pos)
{
assert(pos < size()); //进行越界判断
return _start[pos];
}
void push_back(const T& data) // 这里有关 两个问题的探讨，1. const 修饰； 2. 引用
{
if (_finish == end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = data;
_finish++;
}补充
为啥不用memcpy那段代码？
如果你一直使用 int 这样的内置类型作为 T ,那你会很难发现。当数据是自定义类型时，外层是深拷贝，而内部还是浅拷贝。
![[STL] vector 模拟实现详解,C++——从入门到入土，安排！,c++,开发语言,学习,windows,算法](https://imgs.yssmx.com/Uploads/2023/07/595014-4.png)
同理，传统写法的拷贝构造我们也可以完善（拷贝构造在下面）
三，迭代器实现
![[STL] vector 模拟实现详解,C++——从入门到入土，安排！,c++,开发语言,学习,windows,算法](https://imgs.yssmx.com/Uploads/2023/07/595014-5.png)
STL中, 我们可以瞧见，有两种版本的迭代器，不同的是对象是否是const的对象。
分析： const成员函数中，this 显示表现是：const T& const this , 是不允许修改内容的缩小权限，因此需要我们实现一些函数时，需要2个版本。
诺：
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
void func(const vector<T>& v)
{
const_iterator it = v.begin();
while (it != v.end())
{
cout << *it << endl;
it++;
}
}没有const版本的迭代器，在接收const对象时就可能出现这种类型错误：
![[STL] vector 模拟实现详解,C++——从入门到入土，安排！,c++,开发语言,学习,windows,算法](https://imgs.yssmx.com/Uploads/2023/07/595014-6.png)
更改很简单，完整的实现如下：
iterator begin()
{
return _start;
}
iterator begin() const
{
return _start;
}
iterator end()
{
return _finish;
}
iterator end() const
{
return _finish;
}不止是begine（）函数，其他成员函数，在特定情况下也是需要const修饰版本。
既然完成了迭代器begine, end实现，那范围for面对const对象时，就能解解决了。（范围for底层仅仅只是替换为迭代器访问）
诺：
my_vector::vector<int> p1;
const my_vector::vector<int> p2;
for (cosnt auto& i : p1) // 调用普通迭代器 （这里的const与&，兼顾效率与兼容性）
{
cout << p1[i] << " ";
}
for (cosnt auto& i : p2) // 调用const迭代器
{
cout << p1[i] << " ";
}四，Pop_back
void Pop_back()
{
assert(_finish > _start);
_finish--;
}五，insert
关于插入，在C语言插入思想大差不差。
void insert(iterator pos, const T& val)
{
assert(pos >= _start);
if (size() + 1 >= capacity())
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
if (pos < _finish)
{
iterator end = _finish;
while ( end != pos)
{
*end = *(end - 1);
end--;
}
*pos = val;
_finish++;
}
else
{
push_back(val);
}
}这里埋个雷，看大家能排出来吗？迭代器失效再完善上面代码。
1. 补充——迭代器失效
基于前面所写的代码，我们来实验一下面代码。
void func1()
{
my_vector::vector<int> p2;
p2.push_back(1);
p2.push_back(2);
p2.push_back(3);
p2.push_back(4);
p2.push_back(5);
auto pos = find(p2.begin(), p2.end(), 3);
p2.insert(pos, 100); // insert一般搭配find算法，一般情况下是不知道数据的迭代器
for (const auto& n : p2)
{
cout << n << " ";
}
}现在运行没有问题，但我们将p2.push_back（5）注释掉后我们再运行。结果是：
![[STL] vector 模拟实现详解,C++——从入门到入土，安排！,c++,开发语言,学习,windows,算法](https://imgs.yssmx.com/Uploads/2023/07/595014-7.png)
???!!! 有bug??!!!
这里就不卖关子，错误原因：
在该场景下，是既要插入，又要扩容。而迭代器pos本质是指针，由于扩容后，pos保留旧空间的位置，pos数据未更新，野指针错误。
![[STL] vector 模拟实现详解,C++——从入门到入土，安排！,c++,开发语言,学习,windows,算法](https://imgs.yssmx.com/Uploads/2023/07/595014-8.png)
修改方法也很简单，完善一下pos更新机制 ：![[STL] vector 模拟实现详解,C++——从入门到入土，安排！,c++,开发语言,学习,windows,算法](https://imgs.yssmx.com/Uploads/2023/07/595014-9.png)
好了，那迭代器失效到底想告诉我们啥？
迭代器失效————在我们插入数据之后的pos，是有可能失效了的，尽量不要用pos访问数据。
这里我们可能会有疑问？我们不是已经更新了pos了吗？
解答： 那是在insert函数中修改，值传递，行参不影响实参。(请原谅我会问出这样的问题【苦笑不得】)
另外，有的人会说，那我行参我传pos的引用，在此环境下，确实可以解决此问题，但我的回答是尽量跟STL保持一致，设计框架上的修改往往牵一发而动全身，我们现在还把握不住。
六， erase
比较简单，就是向前替换数据。如：vector<int> p1(10, 2); 初始10个数据，初始值为2.
// STL中要求erase返回被删除位置的下一个位置的迭代器
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
while (pos + 1 != _finish)
{
*pos = *(pos + 1);
pos++;
}
_finish--;
return pos;
}那么这里存在迭代器失效的问题吗？ 结果：我们所实现的erase不会导致迭代器失效，那STL库里面的呢？ 答案是看编译器。 （我们知道STL是一个标准库，旨在告诉大家要实现C++库函数的功能标准，具体实现得看编译器如何实现，比如：一些编译器，在实现erase时，可能会进行缩容，这样迭代器就可能失效）
总结一下迭代器失效：insert / erase的 pos位置，一定要更新； 不要直接访问，可能会出现出乎意料的结果。
七，构造函数
开头我们已经写了一个简单的构造函数，这里将补充：迭代器构造， 拷贝构造。
1. 迭代器构造
template <class inputIterator> // 提供一个接收参数迭代器的新模板
25 vector (inputIterator first, inputIterator last)
26 :_start(nullptr)
27 ,_finish(nullptr)
28 ,end_of_storage(nullptr)
29 {
30 while (first != last)
31 {
32 push_back(*first);
33 first++;
34 }
35 }
这里需要注意的是，这是构造函数，需要将数据初始化，不要忘了。
2. 其他构造
实现一下，一次性初始化多个数据。
vector(size_t n , const T& val = T())
{
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
但这样写会有一个bug ，就是当两参数都是int时，会与迭代器构造产生歧义，由于计算机会寻找最匹配的函数，因此会调用迭代器构造函数，而后面访问把int当做迭代器将会导致报错。
那如何调整？？
其实很简单解决：
法一： 改size_t 为 int
vector(int n , const T& val = T())
法二： 保留size_t, 我们再重载一个int 的构造函数
vector(size_t n , const T& val = T())
{
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
vector(int n , const T& val = T())
{
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
} 3. 拷贝构造
1） 传统写法
// 传统写法
E> 56 vector (const my_vector::vector<T>& v)
57 :_start(nullptr)
58 ,_finish(nullptr)
59 ,end_of_storage(nullptr)
60 {
61 reserve(v.size());
62 // memcpy(_start, v._start, sizeof(T) * v.size() );
63 for (size_t i = 0; i < v.size(); i++ )
64 {
65 _start[i] = v[i];
66 }
67 _finish += v.size();
68 } 2）现代写法（提高函数复用性）
void swap(my_vector::vector<T>& order)
38 {
39 std::swap(_start, order._start);
40 std::swap(_finish, order._finish);
41 std::swap(end_of_storage, order.end_of_storage);
42 }
43
44 // 拷贝构造
45 vector (const my_vector::vector<T>& v )
46 : _start(nullptr)
47 , _finish(nullptr)
48 , end_of_storage(nullptr)
49 {
50 my_vector::vector<T> tmp(v.begin(), v.end());
51 // 借用迭代器构造，然后交换数据。
52 swap(tmp);
53 }
八，赋值符号重载
这里对一个易错点进行分析: 有些同学会分不清 p2 = p1 & p2(Data)
void t() 81 { 82 vector<int> p1 = 10; // 这是一个p1的初始化，等价于p1(10) 83 vector<int> p2; 84 p2 = p1; // p2已经存在，这才是调用赋值重载函数 86 }
关于这个赋值重载比较简便的写法：
vector<T>& operator= (vector<T> v) // 不添加&是故意的
195 {
196 swap(v);
197 return *this;
198 } 这里提一下里面的思路：![[STL] vector 模拟实现详解,C++——从入门到入土，安排！,c++,开发语言,学习,windows,算法](https://imgs.yssmx.com/Uploads/2023/07/595014-10.png)
九，resize
调整数据大小的函数， 解决已经存在的对象进行修改大小。文章来源：https://www.toymoban.com/news/detail-595014.html
// 调整数据大小
132 void resize(size_t n , const T& val = T())
133 {
134 if (n > capacity())
135 {
136 reserve(n);
137 }
138
139 if (n > size())
140 {
141 // 开始填充数据
142 while ( _finish < _start + n )
143 {
144 *_finish = val;
145 _finish++;
146 }
147 }else
148 {
149 _finish = _start + n;
150 }
151 }
结语
本小节就到这里了，感谢小伙伴的浏览，如果有什么建议，欢迎在评论区评论，如果给小伙伴带来一些收获请留下你的小赞，你的点赞和关注将会成为博主创作的动力。文章来源地址https://www.toymoban.com/news/detail-595014.html
到了这里，关于[STL] vector 模拟实现详解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![C++ [STL之vector模拟实现]](https://imgs.yssmx.com/Uploads/2024/02/500268-1.png)
