文章目录
前言一、 成员变量二、迭代器相关1. 普通类型2. const类型 三、构造相关1. 无参默认构造2. 构造n个val3. 迭代器区间初始化4. 支持{ }初始化的形式initializer_list 四、拷贝构造1. memcpy是浅拷贝2. 传统写法3. 现代写法 五、赋值重载六、析构函数七、其他使用1. 重载operator[]2. 获取size3. 获取capacity4. 判空 八、对空间的使用1. 预开空间reserve2. 改变size resize 九、插入删除相关1. 任意位置插入 insert1）代码实现2）迭代器失效1（1）内部迭代器失效的原因（2）内部失效的解决方法（3）外部迭代器失效的原因 2. 删除pos位置 erase1）代码实现2）迭代器失效2 3. 迭代器失效深入剖析4. 尾插push_back5. 尾删pop_back 总结
前言
今天我们一起来看看vector的模拟实现~
一、 成员变量
在 vector 的模拟实现中，private 部分的三个变量用于管理动态数组的内存和元素范围：_start 指向表头，_finish 指向当前元素的末尾，_endofstorage 指向分配容量的末尾。
这里给了缺省值，是给初始化列表用的，避免构造和拷贝构造为随机值。
private:iterator _start = nullptr; //表头位置iterator _finish = nullptr; //size大小结束位置下一个iterator _endofstorage = nullptr; //capacity下一个位置二、迭代器相关
对于const和非const我们要提供两种类型。
1. 普通类型
typedef T* iterator;iterator begin(){return _start;}iterator end(){return _finish;}2. const类型
typedef const T* const_iterator;const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}三、构造相关
1. 无参默认构造
因为给了缺省值，所以不需要写初始化列表，和再给一次缺省了
//无参默认构造vector(){}2. 构造n个val
这里提供2个版本，是因为这里的构造和下面用迭代器的有冲突，迭代器是两个类型一致的，而我们这里传的两个变量默认为int，他不会走size_t这个调用，而是回去走迭代器，一旦走迭代器传参不符合下面的代码就会报错，因此这里提供一个int版本避免这个问题。
使用的时候像这样才都可以支持：
这里要使用x86，x64这里行为不太一样
//构造为n个valvector(size_t n, const T& val = T()){resize(n, val);}vector(int n, const T& val = T()){resize(n, val);}3. 迭代器区间初始化
这里要写成模板的形式更加的通用，对于任意的类型都可以用迭代器，比如下方这种情况：
namespace jyf { std::list<int> myList = {1, 2, 3, 4, 5}; // 创建一个 list jyf::vector<int> vec(myList.begin(), myList.end()); // 用 list 的迭代器初始化 MyVector}//用一段迭代器区间初始化template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}4. 支持{ }初始化的形式initializer_list
用这种形式，构造的时候可以写成 vector<int> v = {1, 2, 3, 4, 5};
//C++11支持{ }初始化的形式initializer_listvector(initializer_list<T> il){//提前开空间，提高插入效率，减小频繁开空间reserve(il.size());for (auto& e : il){push_back(e);}}四、拷贝构造
1. memcpy是浅拷贝
本来我们自己开空间，然后使用memcpy对vector进行拷贝，但是memcpy是浅拷贝，对于自定义有资源申请的类型会有大坑（如：两次析构）。
因此，我们拷贝不能用memcpy，而是可以用一个for循环逐个拷贝值。
这也是一种深拷贝！
for (int i = 0; i < v.size(); i++){_start[i] = v._start[i];}2. 传统写法
//拷贝构造vector(const vector<T>& v){//传统写法_start = new T[v.capacity()];//memcpy是浅拷贝，对与有资源的内置类型不可以//memcpy(_start, v._start, sizeof(T) * v.size());//深拷贝for (int i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_endofstorage = _start + v.capacity();}传统写法也可以（用reserve）这样去复用：
//传统写法也可以像这样去复用vector(const vector<T>& v){reserve(v.capacity());for (auto e : v){push_back(e);}}3. 现代写法
void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}//拷贝构造vector(const vector<T>& v){// 现代写法vector<T> tmp(v);swap(tmp);}五、赋值重载
直接用现代写法简单又便捷，就是复用构造。
//赋值重载vector<T>& operator= (vector<T> v){//现代写法swap(v);return *this;}六、析构函数
释放资源就好，这里可以判空也可以不判空，对空析构也不是什么大错，不用断言，判断一下即可。
~vector(){if (_start){delete[] _start;_start = _finish = _endofstorage = 0;}}七、其他使用
1. 重载operator[]
同样提供constyu非const两个版本
//operator[]T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}2. 获取size
//获取sizesize_t size() const{return _finish - _start;}3. 获取capacity
size_t capacity() const{return _endofstorage - _start;}4. 判空
//判空bool empty() const{return _start == _finish;}八、对空间的使用
1. 预开空间reserve
要注意的点是：
n > capacity 才去开空间，reserve没有缩容，对于 n < capacity 不做处理。同样不能用memcpy，memcpy只是浅拷贝，我们这里vector是要支持所有类型的，对于自定义带资源的浅拷贝不够。//预开空间void reserve(size_t n){if (n > capacity()){size_t oldsize = size();T* tmp = new T[n];if (_start){//memcpy只是浅拷贝//memcpy(tmp, _start, sizeof(T) * oldsize);for (size_t i = 0; i < oldsize; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + oldsize;_endofstorage = _start + n;}}2. 改变size resize
要注意的点是：
n < size 仅仅移动_finish删除， n >= size 要进行对多出来的数据初始化，这里为了适配所有类型，传了T类型的匿名对象做缺省参数。//改变size大小void resize(size_t n, const T& val = T()){if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}}九、插入删除相关
1. 任意位置插入 insert
1）代码实现
要注意的点：
要先判断空间够不够，不够先扩容。注意循环的时候对应好位置，这里用的指针不想string存在size_t类型的end小于0的情况。注意迭代器的失效，记录相对位置更新pos//任意位置插入iterator insert(iterator pos, T x){assert(pos >= _start && pos <= _finish);if (size() == capacity()){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}iterator i = _finish - 1;while (i >= pos){*(i + 1) = *i;--i;}*pos= x;_finish++;return pos;}2）迭代器失效1
（1）内部迭代器失效的原因
内部迭代器失效是指在容器的内部结构发生变化时，指向该容器元素的迭代器不再有效。以下是一些常见的原因：
动态内存分配：当容器的容量满时，如果需要插入新元素，通常会分配一块更大的内存。这种情况下，原有的元素可能会被复制到新的内存位置，导致原来的迭代器失效，因为它们仍然指向旧的内存位置。
元素移动：在插入或删除操作时，元素可能需要移动。例如，在插入新元素时，为了在指定位置保留元素顺序，容器需要将该位置及其后面的元素向后移动。这时，如果有迭代器指向这些元素，它们会失去指向正确位置的能力。
例子：
假设我们有一个 vector，初始容量为 3，存储元素 {1, 2, 3}。当我们试图插入新元素 4 到位置 1 时，容器会重新分配内存并将元素 {1, 2, 3} 复制到新的位置。此时，指向原位置的迭代器失效，因为它们仍然指向旧的内存地址。
（2）内部失效的解决方法
为了避免内部迭代器失效，可以采取以下方法：
记录相对位置更新pos：在插入新元素之前，我们可以记录 pos 相对于 _start 的位置，并在扩容后根据这个位置更新 pos。具体来说，可以在容器扩容后，通过计算新位置来确保 pos 依然指向正确的元素。 例子：
如果 pos 原本是指向第 2 个元素（即 {1, 2, 3} 中的 2），在扩容后，我们可以通过计算相对位置来重新获得 pos：
size_t len = pos - _start; // 记录 pos 的相对位置reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len; // 根据新的 _start 更新 pos这样，即使内存发生变化，pos 依然能够正确指向新的元素。
（3）外部迭代器失效的原因
外部迭代器失效主要是因为形参的改变不影响实际参数，以及容器空间变化后迭代器位置的不一致：
形参不影响实参：在函数内部对形参 pos 的修改不会反映到实参上，因此在修改 pos 之前，需要确保在其他操作后，pos 仍然是有效的。
空间变化导致不一致：当容器空间发生变化（如扩容、缩容等），如果直接使用 pos，它可能依然指向旧的内存地址，因此需要相应地更新 pos 以避免失效。
如：
iterator pos = v.begin() + 3;v.insert(pos, 10);//pos因为扩容已经不匹配当前空间了pos++;v.insert(pos, 10);因此我们要避免iterator pos这种写法，用的话只能用一次，只要牵扯可能会扩容，我们就认为迭代器失效了。
当然，我们也可以把返回值改成iterator,使用insert后重新用pos来接收更新这个迭代器。
2. 删除pos位置 erase
1）代码实现
要注意的点：
这里的返回值是iterator是因为减少迭代器失效所带来的麻烦，如同下面的例子，删除vecetor中的偶数会使用。//删除任意位置的值iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator i = pos + 1;while (i != _finish){*(i - 1) = *i;++i;}--_finish;return pos;}2）迭代器失效2
这里的迭代器也有失效的风险，比如删除最后一个元素，pos就会越界访问，因此vs会对这里进行强制性的检查，一旦执行erase后还要访问pos，就会报错。
这里我们模拟实现的迭代器和库里的迭代器都会失效，只不过库里的会对于使用过的迭代器再去访问时强制警告，我们模拟实现vector中的erase不会强制警告。
auto pos = v1.begin();v1.erase(pos); erase以后，迭代器失效了，不能访问 vs进行强制检查，访问会直接报错cout << *pos << endl;++pos;cout << *pos << endl;for (auto e : v1){cout << e << " ";}cout << endl;对于这样的题目，我们想解决迭代器失效的问题，就要给迭代器重新赋值。
void test04(){///除去vecter<int>中的偶数///vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);for (auto e : v1){cout << e << " ";}cout << endl;auto it = v1.begin();while (it != v1.end()){if (*it % 2 == 0)// 不这么接收，有些编译器会报错,vs2022做了处理it = v1.erase(it);else++it;}for (auto e : v1){cout << e << " ";}cout << endl;}3. 迭代器失效深入剖析
迭代器的主要作用是让算法能够在操作容器时，不必关心底层数据结构，其底层实际上是一个指针，或者是对指针进行了封装。例如，vector 的迭代器就是原生指针 T*。因此，迭代器失效实质上是迭代器底层指针所指向的内存空间被销毁。当尝试使用一块已释放的内存时，程序可能会崩溃。
导致迭代器失效的操作
对于 vector，以下操作可能导致其迭代器失效：
底层空间改变的操作：任何可能引起底层内存重新分配的操作都会导致迭代器失效，例如：resize、reserve、insert、assign、push_back 等。
删除指定位置元素的操作：例如，调用 erase 函数删除 pos 指向的元素。尽管删除操作本身不会导致底层空间的变化，删除之后 pos 可能指向了一个无效的位置。
示例：
#include <iostream>#include <vector>using namespace std;int main() { vector<int> v{1, 2, 3, 4, 5, 6}; auto it = v.begin(); // 可能导致迭代器失效的操作 // v.resize(100, 8); // v.reserve(100); // v.insert(v.begin(), 0); // v.push_back(8); v.assign(100, 8); // 此时 it 仍指向之前的空间，但该空间已被释放 while (it != v.end()) { cout << *it << " "; ++it; } cout << endl; return 0;}上述代码中，assign 可能会导致 vector 的底层内存重新分配。此时，it 仍指向之前的内存空间，但这块内存已经被释放，使用 it 将导致程序崩溃。
解决方法
为避免迭代器失效，在执行可能改变底层空间的操作后，应重新赋值 it：
it = v.begin(); // 重新获取有效的迭代器删除元素导致的迭代器失效
删除元素时，虽然后续的元素会向前移动，但如果删除的元素是最后一个元素，pos 可能会指向 end，此时就会失效。
示例：
#include <iostream>#include <vector>using namespace std;int main() { vector<int> v{1, 2, 3, 4}; auto pos = find(v.begin(), v.end(), 3); v.erase(pos); cout << *pos << endl; // 此处会导致非法访问 return 0;}关键注意事项
Linux 与 VS 的表现差异：在 Linux 上，g++ 编译器对迭代器失效的检测不如 VS 严格。虽然代码可能运行，但输出结果可能不对。
扩容与迭代器失效：调用 reserve 可能会使迭代器失效，即使程序仍然能运行，输出的结果可能是不对的。
示例：
int main() { vector<int> v{1, 2, 3, 4, 5}; auto it = v.begin(); v.reserve(100); // 迭代器 it 失效 while (it != v.end()) { cout << *it << " "; // 此时可能输出错误 ++it; } cout << endl; return 0;}erase 操作后底层空间没有改变，删除最后一个元素后，it 仍然可能失效。 示例：
vector<int> v{1, 2, 3, 4, 5};auto it = v.begin();while (it != v.end()) { if (*it % 2 == 0) v.erase(it); // 此时 it 可能会失效 ++it;}总结
迭代器失效的问题在 vector 中非常常见，主要由于底层空间的改变和元素的移动。使用迭代器时应当谨慎，尤其是在进行插入、删除和扩容等操作后，应及时更新迭代器以确保其有效性。对于可能导致迭代器失效的操作，重新赋值是避免问题的简单有效的方法。
4. 尾插push_back
可以直接实现，也可以复用insert
//尾插void push_back(T x){/*if (size() == capacity()){reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finish = x;_finish++;*/insert(_finish, x);}5. 尾删pop_back
同样可以直接实现也可以复用erase
//尾删void pop_back(){/*assert(!empty());--_finish;*/erase(--_finish);}总结
到这里vector模拟实现就讲完了，下面是模拟实现的代码~
//vector.h//vector的定义和声明不要分开，原因后续会讲解#define _CRT_SECURE_NO_WARNINGS 1#pragma once#include<iostream>#include<vector>#include<assert.h>using namespace std;namespace jyf{template<class T>class vector{public://迭代器相关typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}//构造相关//无参默认构造vector(){}//构造为n个valvector(size_t n, const T& val = T()){resize(n, val);}vector(int n, const T& val = T()){resize(n, val);}//用一段迭代器区间初始化template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}//C++11支持{ }初始化的形式initializer_listvector(initializer_list<T> il){//提前开空间，提高插入效率，减小频繁开空间reserve(il.size());for (auto& e : il){push_back(e);}}//拷贝构造vector(const vector<T>& v){//传统写法_start = new T[v.capacity()];//memcpy是浅拷贝，对与有资源的内置类型不可以//memcpy(_start, v._start, sizeof(T) * v.size());//深拷贝for (int i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_endofstorage = _start + v.capacity();// 现代写法/*vector<T> tmp(v);swap(tmp);*/}//传统写法也可以像这样去复用/*vector(const vector<T>& v){reserve(v.capacity());for (auto e : v){push_back(e);}}*///赋值重载vector<T>& operator= (vector<T> v){//现代写法swap(v);return *this;}~vector(){if (_start){delete[] _start;_start = _finish = _endofstorage = 0;}}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}//operator[]T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}//获取sizesize_t size() const{return _finish - _start;}//获取capacitysize_t capacity() const{return _endofstorage - _start;}//判空bool empty() const{return _start == _finish;}//预开空间void reserve(size_t n){if (n > capacity()){size_t oldsize = size();T* tmp = new T[n];if (_start){//memcpy只是浅拷贝//memcpy(tmp, _start, sizeof(T) * oldsize);for (size_t i = 0; i < oldsize; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + oldsize;_endofstorage = _start + n;}}//改变size大小void resize(size_t n, const T& val = T()){if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}}//尾插void push_back(T x){/*if (size() == capacity()){reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finish = x;_finish++;*/insert(_finish, x);}//尾删void pop_back(){/*assert(!empty());--_finish;*/erase(--_finish);}//任意位置插入iterator insert(iterator pos, T x){assert(pos >= _start && pos <= _finish);if (size() == capacity()){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;}iterator i = _finish - 1;while (i >= pos){*(i + 1) = *i;--i;}*pos= x;_finish++;return iterator;}//删除任意位置的值iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator i = pos + 1;while (i != _finish){*(i - 1) = *i;++i;}--_finish;return pos;}private:iterator _start = nullptr; //表头位置iterator _finish = nullptr; //size大小结束位置下一个iterator _endofstorage = nullptr; //capacity下一个位置};void printf(const vector<int>& v){for (auto e : v){cout << e << " ";}cout << endl;}void test01(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);cout << "size = " << v1.size() << endl;cout << "capacity = " << v1.capacity() << endl;v1.push_back(5);cout << "size = " << v1.size() << endl;cout << "capacity = " << v1.capacity() << endl;for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;for (auto e : v1){cout << e <<" ";}cout << endl;cout << "//" << endl;v1.pop_back();v1.pop_back();v1.pop_back();v1.pop_back();v1.pop_back();cout << "size = " << v1.size() << endl;cout << "capacity = " << v1.capacity() << endl;for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;//v1.pop_back();cout << "//" << endl;vector<int>:: iterator it1 = v1.begin();while (it1 != v1.end()){cout << *it1 << " ";++it1;}cout << endl;}void test02(){/*vector<int> v1;v1.insert(v1.begin(), 1);v1.insert(v1.begin(), 2);v1.insert(v1.begin(), 3);v1.insert(v1.begin() + 2, 4);for (size_t i = 0; i < v1.size(); i++){cout << v1[i] << " ";}cout << endl;*/vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (auto e : v1){cout << e << " ";}cout << endl;v1.insert(v1.begin() + 2, 30);for (auto e : v1){cout << e << " ";}cout << endl;vector<int> v2 = { 1,2,3,4,5,6 };for (auto e : v2){cout << e << " ";}cout << endl;}void test03(){vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);for (auto e : v1){cout << e << " ";}cout << endl;/*v1.erase(v1.begin()+4);*/auto pos = v1.begin();v1.erase(pos); erase以后，迭代器失效了，不能访问 vs进行强制检查，访问会直接报错//vs2022做了优化，不报错了cout << *pos << endl;++pos;cout << *pos << endl;for (auto e : v1){cout << e << " ";}cout << endl;}void test04(){///除去vecter<int>中的偶数///vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);for (auto e : v1){cout << e << " ";}cout << endl;auto it = v1.begin();while (it != v1.end()){if (*it % 2 == 0)// 不这么接收，有些编译器会报错,vs2022做了处理it = v1.erase(it);else++it;}for (auto e : v1){cout << e << " ";}cout << endl;}void test05(){vector<int> v;v.resize(10, 0);for (auto e : v){cout << e << " ";}cout << endl;}void test06(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);vector<int> v1(v);for (auto e : v1){cout << e << " ";}cout << endl;vector<int> v2;v2.resize(10, 1);v1 = v2;for (auto e : v1){cout << e << " ";}cout << endl;}void test07(){vector<string> v;v.push_back("111111111111111111");v.push_back("222222222222222222");v.push_back("333333333333333333");v.push_back("444444444444444444");v.push_back("555555555555555555");for (auto& e : v){cout << e << " ";}cout << endl;vector<string> v1(v);for (auto& e : v1){cout << e << " ";}cout << endl;}void test08(){vector<string> v1 = { "123456", "456789", "asdasdasd" };for (auto& e : v1){cout << e << " ";}cout << endl;}void test09(){vector<int> v(10, 1);//vector<string> v1(10, "1111");//vector<int> v2(10, 1);// vector<int> v;for (auto e : v){cout << e << " ";}cout << endl;/*vector<int> v3(v.begin(), v.end());for (auto e : v3){cout << e << " ";}cout << endl;string str("hello world");vector<char> v4(str.begin(), str.end());for (auto e : v4){cout << e << " ";}cout << endl;int a[] = { 16,2,77,29 };vector<int> v5(a, a + 4);for (auto e : v5){cout << e << " ";}cout << endl;*/}}//test.cpp#include "vector.h"int main(){//jyf::test01();//jyf::test02();//jyf::test03();//jyf::test04();//jyf::test05();//jyf::test06();//jyf::test07();//jyf::test08();jyf::test09();return 0;}感谢支持~谢谢大家！
