C++：一次性搞定vector模拟实现中必须关注的细节

2024-03-31 00:28
文章标签 c++ 实现 模拟 一次性 细节 vector 搞定 关注 必须

本文主要是介绍C++：一次性搞定vector模拟实现中必须关注的细节，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

vector模拟实现的细节

  • 1. vector的模拟实现源码
  • 2. 重要接口注意事项
    • 2.1 const修饰
    • 2.2 begin()和end()
    • 2.3 构造函数
      • （1）迭代器区间初始化
      • （2）构造函数冲突问题
        • 发现​问题
        • 分析问题
        • ​解决问题
      • （3）特殊的构造函数的实现
    • 2.4 insert
      • 注意点
      • 分析原因
      • 图解
    • 2.5 push_back
    • 2.6 reserve
      • 发现问题
      • 分析问题
      • 解决问题
      • 图解
    • 2.7 resize
    • 2.8 swap
  • 3. vector的迭代器失效
    • 3.1 insert造成的迭代器失效
      • 案例：往容量已满的vector容器中插入值（实现时默认为4个空间）
      • 分析问题
      • 解决方案
    • 3.2 erase造成的迭代器失效
      • 案例：删除值为偶数的位置
      • 图解
      • 分析问题
      • 解决问题
      • 总结

1. vector的模拟实现源码

vector本质是顺序表，因此其迭代器可以理解为原生指针。
我们通过原生指针来模拟实现vector.

namespace B
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//Iteratorsiterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}//constructor and destructorvector():_start(nullptr), _finish(nullptr), _endofstorage(nullptr){ }vector(initializer_list<T> il){//const T* it = il.begin();//while (it != il.end())//{//push_back(*it);//it++;//}//il本质是一个类，有begin()和end()，因此也可以使用迭代器reserve(il.size());for (auto& e : il){push_back(e);}}vector(size_t n, const T& val = T()){//_start = new T[n];//_finish = _endofstorage = _start + n;//复用reservereserve(n);for (size_t i = 0; i < n; i++)push_back(val);}vector(int n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++)push_back(val);}template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){*_finish = e;_finish++;}}//现代写法vector<T>& operator= (vector<T> v){swap(v);return *this;}~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}//capacitybool empty() const{return _finish == _start;}size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}void resize(size_t n , const T& val = T()){if (n > size()){reserve(n);for (size_t i = size(); i < n; i++)push_back(val);}else{//for (int i = size(); i > n; i--)//	pop_back();//我们可以直接改变指针_finish = _start + n;}}void reserve(size_t n){//不会缩容//错误写法//错因：我们的_start改变了 但是我们的_finsh和_endofstorage还没有改变//在调用size()时会出错 因为我们size()函数求大小时使用了_finish//if (n > capacity)//{//	T* tmp = new T[n];//	memcpy(tmp, _start, sizeof(T) * size());//	delete[] _start;//	_start = tmp;//	_finish = _start + size();//	_endofstorage = _start + n;//}//正确if (n > capacity()){size_t oldSize = size();T* tmp = new T[n];//memcpy(tmp, _start, sizeof(T) * size());//如果使用memcpy，对于类似vector<string>这样的类，就会出现浅拷贝的现象从而报错for (size_t i = 0; i < oldSize; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = _start + oldSize;_endofstorage = _start + n;}}//Element accessT& operator[](size_t pos){return *(_start + pos);}const T& operator[](size_t pos) const{return *(_start + pos);}//Modifyvoid push_back(const T& x){//扩容//if (_finish == _endofstorage)//{//	size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;//	reserve(newcapacity);//}//*_finish = x;//_finish++;//复用insert()insert(end(), x);}void pop_back(){assert(!empty());//_finish--;//复用erase()erase(end() - 1);}void swap(vector<T>& v){//注意：不能直接写成swap(_start,v._start);//swap(_start, v._start);std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}iterator insert(iterator pos, const T& x){assert(pos >= begin() && pos <= end());size_t ret = pos - _start;if (_finish == _endofstorage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);//必须要更新pos--->迭代器失效pos = _start + len;}iterator cur = _finish;//移动数据// _start         pos                 _finish(tmp)//    1      2     3     4      5while (cur > pos){*cur = *(cur - 1);cur--;}*cur = x;_finish++;return _start + ret;}iterator erase(iterator pos){assert(pos >= begin() && pos < end());//移动数据// _start         pos                 _finish//    1      2     3     4      5size_t len = pos - _start;iterator cur = pos;while (cur < _finish - 1){*cur = *(cur + 1);cur++;}_finish--;return pos;}void PrintVector(){for (auto& e : *this){cout << e << " ";}cout << endl;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};
}

2. 重要接口注意事项

2.1 const修饰

对于不修改成员变量的函数，如size(),capacity()，需要加上const，否则非const成员不能使用。

2.2 begin()和end()

注意对于常量型也必须写成begin()和end()，不能写成cbegin()和cend()，因为它们是C++11之后为了完整性新增加的，但是范围for迭代器只能替换begin()和end()。

实现代码：

		//Iteratorsiterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}

2.3 构造函数

（1）迭代器区间初始化

迭代器区间初始化，使用模板的目的是为了不只是vector类的迭代器区间可以使用，string等其他容器的迭代器区间也可以使用。通过模板，无论我们传入的是哪一个容器的迭代器，都可以进行初始化，比如使用库中的list等。

示例：
我们使用string的迭代器来对vector进行初始化。
在这里插入图片描述

实现代码：

template<class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);first++;}
}

（2）构造函数冲突问题

发现​问题

我们在使用如下代码想要初始化时，编译器报错。

void testvector4()
{//会报错vector<int> v(10, 1);v.PrintVector();//不会报错//vector<int> v(10u, 1);//v.PrintVector();
}

在这里插入图片描述

分析问题

我们想要调用的是第一个构造函数，但是编译器调用了第二个，调用到了我们所写的模板函数中去，由于int是内置类型，push_back时无法进行解引用，因此报错。
在这里插入图片描述
如果我们在10后面加上u，仅仅是传参的类型改变，但是却不会报错，程序正确执行，那么因此我们可以确定是类型引发的问题。

10和1这种内置类型如果我们没有额外说明，那么默认都为int类型，因此两个int类型，符合模板构造函数，而我们想要调用的构造函数由于n的类型为size_t，虽然两个int类型也可以调用，但是需要类型提升，比较麻烦，因此编译器在有两个函数参数类型相同的情况下，选择了调用函数模板实例化的函数。

​解决问题

==​因为编译器对于同名函数且参数类型相同的函数调用的规则是：有现有的函数调用现有的，没有现有的函数调用函数模板实例化出来的函数。==因此我们可以进行函数重载，重载一份n为int类型的函数，这样的话编译器就会先调用已经实现的函数啦。

实现代码：

vector(int n, const T& val = T())
{reserve(n);for (size_t i = 0; i < n; i++)push_back(val);}vector(size_t n, const T& val = T())
{reserve(n);for (size_t i = 0; i < n; i++)push_back(val);
}template<class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);first++;}
}

（3）特殊的构造函数的实现

​我们在OJ中经常能看到这种用法：

​ vector<int> v = { 1, 2, 3, 4 ,5};

而我们自己模拟实现的vector则不支持，会报错。

在这里插入图片描述
通过查阅文档，了解到这种用法是在C++11以后新增加的用法。
其中initializer list是一个类模板。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
通过该构造函数进行初始化，在内部使用其迭代器进行初始化。
在这里插入图片描述
实现代码：

vector(initializer_list<T> il)
{//方法一：//const T* it = il.begin();//while (it != il.end())//{//push_back(*it);//it++;//}//方法二：//il本质是一个类，有begin()和end()，因此也可以使用迭代器reserve(il.size());for (auto& e : il){push_back(e);}
}

2.4 insert

注意点

如果扩容，不更新pos的位置，会造成内部的迭代器失效问题。

分析原因

如果空间容量不足，那么会进行扩容，而扩容之后由于reserve内部实现了_start 和 _finish的更新，但是pos的迭代器位置错误造成迭代器失效仍然是一个问题。

图解

在这里插入图片描述

代码实现：

iterator insert(iterator pos, const T& x)
{assert(pos >= begin() && pos <= end());size_t ret = pos - _start;if (_finish == _endofstorage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);//必须要更新pos--->迭代器失效pos = _start + len;}iterator cur = _finish;//移动数据// _start         pos                 _finish(tmp)//    1      2     3     4      5while (cur > pos){*cur = *(cur - 1);cur--;}*cur = x;_finish++;return _start + ret;
}

2.5 push_back

​
注意点：

函数参数要加const，否则会因为权限放大而报错。

​vector<int> v;
​v.push_back(1);
​//1为常量，具有const属性，如果参数不加const则无法使用，会报错

实现代码：

void push_back(const T& x)
{//原始写法//扩容//if (_finish == _endofstorage)//{//	size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;//	reserve(newcapacity);//}//*_finish = x;//_finish++;//复用insert()insert(end(), x);
}

2.6 reserve

注意事项：

1.memcpy是按照字节数量进行拷贝的---->在使用时会出现问题 如果是有深拷贝的类 会出错
2.扩容的时候提前保留size--->如果后面_finish直接使用_start + size()，size()在计算时使用的是已经释放空间的_finish，而_start指向的是新空间的开始，因此会报错。
3._endofStorge改变时，不能直接让其等于n，因为类型不同

发现问题

如果对于vector< string >这样的容器，由于string类内部也有申请空间，如果还是使用memcpy就会报错。

分析问题

我们在reserve()的时候重新new空间只是对于vector进行了深拷贝，但是由于string也是一个需要深拷贝的类，我们直接使用memcpy拷贝的是字节，属于浅拷贝，即新旧空间中的str指向同一块地址，而旧空间free之后会把那里的空间释放掉，因此程序会出错。

解决问题

直接使用循坏，对于每一个值都采取赋值构造，因为string的赋值构造内部是已经写好的深拷贝，我们不需要关心其内部是如何实现的。在采取赋值构造时它会自己进行深拷贝。

图解

在这里插入图片描述
实现代码：

void reserve(size_t n)
{//不会缩容//错误写法//错因：我们的_start改变了 但是我们的_finsh和_endofstorage还没有改变//在调用size()时会出错 因为我们size()函数求大小时使用了_finish//if (n > capacity)//{//	T* tmp = new T[n];//	memcpy(tmp, _start, sizeof(T) * size());//	delete[] _start;//	_start = tmp;//	_finish = _start + size();//	_endofstorage = _start + n;//}//正确if (n > capacity()){size_t oldSize = size();T* tmp = new T[n];//memcpy(tmp, _start, sizeof(T) * size());//如果使用memcpy，对于类似vector<string>这样的类，就会出现浅拷贝的现象从而报错for (size_t i = 0; i < oldSize; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = _start + oldSize;_endofstorage = _start + n;}
}

2.7 resize

注意事项：

1.分情况
（1）n < size()时由于底层是原生指针因此我们可以直接改变指针的值，不需要循环pop_back()函数，可以直接_start + n
（2）n > size()时复用reserve，因为reserve内部对于空间足够的情况不会处理，只有空间不足时reserve内部才会重新分配空间
2.参数类型的缺省值如何给：匿名对象

实现代码：

void resize(size_t n , const T& val = T())
{if (n > size()){reserve(n);for (size_t i = size(); i < n; i++)push_back(val);}else{//删除//for (int i = size(); i > n; i--)//	pop_back();//我们可以直接改变指针_finish = _start + n;}
}

2.8 swap

​注意：

1.我们想要调用库的swap函数，因此必须指明std命名空间来调用。

因为编译器在搜索时会先搜索到我们实现的vector类中的swap，然后编译器会报错参数不匹配。

调用代码：

void swap(vector<T>& v)
{//错误写法swap(_start, v._start);swap(_finish, v._finish);swap(_endofstorage, v._endofstorage);
}
void testvector4()
{vector<int> v(10, 1);v.PrintVector();vector<int> v1(20, 2);v1.swap(v);
}

程序报错：
在这里插入图片描述

实现代码：

void swap(vector<T>& v)
{//注意：不能直接写成swap(_start,v._start);//swap(_start, v._start);std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);
}

3. vector的迭代器失效

3.1 insert造成的迭代器失效

在vector中insert导致的迭代器失效多为扩容导致的问题。

案例：往容量已满的vector容器中插入值（实现时默认为4个空间）

void testvector6()
{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();cout << *it << endl;v.insert(it, 40);cout << *it << endl;
}

输出结果：

在这里插入图片描述

分析问题

造成这种问题的原因是因为在insert函数执行时进行了扩容操作，原有的空间被释放，但是it仍然指向被释放的空间，因此打印出来为随机值。

解决方案

错误思路：

可能会有人说，在函数参数部分传引用，这样就可以让迭代器自动更新，但是如果传引用的话，则无法将begin()，end()直接作为参数传递，因为它们的返回值是临时变量，具有常性，如果需要接收则需要在参数部分增加const来修饰，但是增加const之后就不能修改。

正确思路：

在这里插入图片描述

​stl库在设计insert函数时增加返回值，从而便于使用返回值来更新迭代器。更新迭代器

3.2 erase造成的迭代器失效

案例：删除值为偶数的位置

场景一：

//场景：删除值为偶数的节点
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>::iterator it = v.begin();
while (it != v.end())
{if (*it % 2 == 0)v.erase(it);it++;
}
v.PrintVector();

输出结果：正确
在这里插入图片描述

场景二：

//场景：删除值为偶数的节点
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(4);
v.push_back(5);vector<int>::iterator it = v.begin();
while (it != v.end())
{if (*it % 2 == 0)v.erase(it);it++;
}
v.PrintVector();

输出结果：结果不符合预期，有跳过
在这里插入图片描述

场景三：

//场景：删除值为偶数的节点
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);vector<int>::iterator it = v.begin();
while (it != v.end())
{if (*it % 2 == 0)v.erase(it);it++;
}
v.PrintVector();

输出结果：编译器报错
在这里插入图片描述
我们从画图的过程来理解为什么相似的几段代码但是结果却不相同。

图解

场景一：
在这里插入图片描述

场景二：
在这里插入图片描述

场景三：
在这里插入图片描述

分析问题

出现上面的原因就是因为迭代器it没有及时更新还在使用所导致的。

解决问题

在这里插入图片描述
stl库在设计时erase是有返回值的，其返回值为正确的迭代器，因此每次使用后可以通过接收返回值来更新迭代器。

修改后代码：

//场景：删除值为偶数的节点
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(4);
v.push_back(5);
v.push_back(6);vector<int>::iterator it = v.begin();
while (it != v.end())
{if (*it % 2 == 0)it = v.erase(it);elseit++;
}
v.PrintVector();

总结

vector的insert和erase操作都可能使迭代器失效。
迭代器失效以后，不要直接使用，如果需要使用应该按照规则重新更新后使用。

以上是本次所有内容，如有可以提升的地方，希望各位佬可以指点，谢谢观看。

这篇关于C++：一次性搞定vector模拟实现中必须关注的细节的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/862973。

相关文章

MySQL中查找重复值的实现

MySQL中查找重复值的实现

《MySQL中查找重复值的实现》查找重复值是一项常见需求,比如在数据清理、数据分析、数据质量检查等场景下,我们常常需要找出表中某列或多列的重复值,具有一定的参考价值,感兴趣的可以了解一下... 目录技术背景实现步骤方法一：使用GROUP BY和HAVING子句方法二：仅返回重复值方法三：返回完整记录方法四：
阅读更多...
IDEA中新建/切换Git分支的实现步骤

IDEA中新建/切换Git分支的实现步骤

《IDEA中新建/切换Git分支的实现步骤》本文主要介绍了IDEA中新建/切换Git分支的实现步骤,通过菜单创建新分支并选择是否切换,创建后在Git详情或右键Checkout中切换分支,感兴趣的可以了... 前提：项目已被Git托管1、点击上方栏Git->NewBrancjsh...2、输入新的分支的
阅读更多...
Python实现对阿里云OSS对象存储的操作详解

Python实现对阿里云OSS对象存储的操作详解

《Python实现对阿里云OSS对象存储的操作详解》这篇文章主要为大家详细介绍了Python实现对阿里云OSS对象存储的操作相关知识,包括连接,上传,下载,列举等功能,感兴趣的小伙伴可以了解下... 目录一、直接使用代码二、详细使用1. 环境准备2. 初始化配置3. bucket配置创建4. 文件上传到os
阅读更多...
关于集合与数组转换实现方法

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》：本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方
阅读更多...
使用Python实现可恢复式多线程下载器

使用Python实现可恢复式多线程下载器

《使用Python实现可恢复式多线程下载器》在数字时代,大文件下载已成为日常操作,本文将手把手教你用Python打造专业级下载器,实现断点续传,多线程加速,速度限制等功能,感兴趣的小伙伴可以了解下... 目录一、智能续传：从崩溃边缘抢救进度二、多线程加速：榨干网络带宽三、速度控制：做网络的好邻居四、终端交互
阅读更多...
从入门到精通C++11 ＜chrono＞ 库特性

从入门到精通C++11 ＜chrono＞ 库特性

《从入门到精通C++11＜chrono＞库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段（Durat
阅读更多...
java实现docker镜像上传到harbor仓库的方式

java实现docker镜像上传到harbor仓库的方式

《java实现docker镜像上传到harbor仓库的方式》：本文主要介绍java实现docker镜像上传到harbor仓库的方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录1. 前 言2. 编写工具类2.1 引入依赖包2.2 使用当前服务器的docker环境推送镜像2.2
阅读更多...
C++20管道运算符的实现示例

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多，因为它实际属于c++20最为重要的
阅读更多...
Java easyExcel实现导入多sheet的Excel

Java easyExcel实现导入多sheet的Excel

《JavaeasyExcel实现导入多sheet的Excel》这篇文章主要为大家详细介绍了如何使用JavaeasyExcel实现导入多sheet的Excel,文中的示例代码讲解详细,感兴趣的小伙伴可... 目录1.官网2.Excel样式3.代码1.官网easyExcel官网2.Excel样式3.代码
阅读更多...
Visual Studio 2022 编译C++20代码的图文步骤

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性：
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2