C++手撕简易vector

ops/2024/10/18 7:54:29/

提前准备工作

由于vector跟string不同，vector是可以存储不同类型的变量的容器，因此实现类模板是肯定的

在原本的STL的vector容器中，主要成员变量有，start，finish，和 end_of_storage

所以

template<class T>
class vector{
public:private:iterator _start;		//vector容器的起始位置iterator _finish;		//vector容器的有效结束位置iterator _endofstorage;	//vector容器的结束位置
};

构造函数 

这里的构造函数 不会那么多麻烦，可走缺省参数，也可以走参数列表

		vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr){ }

析构函数

		~vector() {if (_start) {	//当vector不为空时才析构delete[] _start;_start = _finish = _endofstorage = nullptr;}}

要先判断_strat是否为空指针，以免对空指针进行delete[ ]

定义迭代器begin( ) 和 end( )

在我们手撕vector中，所使用的依旧用指针当iterator

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;}
		size_t size() const{return _finish - _start;}size_t capacity() const() {return _endofstorage - _start;}

size( ) 和 capacity（ ）

		size_t size() const{return _finish - _start;}size_t capacity() const {return _endofstorage - _start;}

 测试：

	void test3() {vector<int> v;v.push_back(1);v.push_back(1);v.push_back(1);v.push_back(1);v.push_back(1);cout << "我现在的数量是：" << v.size() << endl;cout << "我现在的容量是：" << v.capacity() << endl;}

push_back尾插

		void push_back(const T& x) {//先判断空间够不够if (_finish == _endofstorage) {size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);	//不够扩容}*_finish = x;++_finish;	//最后一步要++}

reserve

void reserve(size_t i) {if (i > capacity()) {T* tmp = new T(i);if (_start) {memcpy(tmp, _start, sizeof(T) * n);delete[] _start;}_start = tmp;_finish = _start + size( );_capacity = i;}
}

此处看起来没有什么任何问题

我们开测试一下

测试

	void test1() {vector<int> v;v.push_back(1);v.push_back(1);v.push_back(1);v.push_back(1);for (auto e : v) {cout << e << " ";}cout << endl;}

 

分析

结果崩了，何以至此？

它说我们的finish是空指针

为何如此

_finish在扩容时是怎么更新的？

_start 没有问题，那么size( )?

我们可以发现，在经历了reserve了的时候，我们的 _start 的地址已经发生了变化 

问题就出于此，当我们返回 size( ) 的时候，我们的 _finish 还是空指针的，但是 _start 已经是有值了，相减为负，出来之后

便相当于变为 ： _start + _finish + _start = _finish

所以此时 _finish 依旧是 空指针，这就是问题所在

解决办法

因此需要用一个值来记录原本 size( ) 返回的数值

		void reserve(size_t n) {if (n > capacity()) {size_t old = size();	//来记录_finish 距离 _start 的距离T* tmp = new T[n];      //，防止被更改if (_start) {memcpy(tmp, _start, sizeof(T) * n);delete[] _start;}_start = tmp;_finish = _start + old;_endofstorage = _start + n;}}

 此刻便能运行成功

自定义类型扩容：vector<string>

 我们可以看到此刻的代码是没有任何毛病的

再塞一个，代码就寄了，为什么呢？

这是原函数在扩容前

 这里扩容的原则是，从0开始，一开始开辟四个空间，四个空间后，每次以两倍方式扩容

扩容的基本方法是，开辟新空间，释放旧空间

但是问题就出现在memcpy，所创建的新空间所指向的 _str 是跟原来的就空间指向的内容是一样的，也就是说当原空间释放的 时候，新空间所指向的内容也是被释放了，因为这是浅拷贝，而不是深拷贝

解决办法

因此，我们需要为容器里的容器也写一个深拷贝，或者想办法保护好_str，因此memcpy不能够再次使用了

将memcpy 换成下列循环就ok了

 pop_back尾删

		void pop_back() {assert(size() >= 0 || (!_start));I--_finish;}

operator [ ] 

		T& operator[](size_t pos) {assert(pos < size());return _start[pos];}
		const T& operator[](size_t pos) const {assert(pos < size());return _start[pos];}

测试

打印自定义的vector类

		void print(const vector<T>& v) {for (auto e : v) {cout << e << " ";}cout << endl;}

其实没什么用，我觉得，但是写这个函数的前提是要有const_iterator

insert

在pos位置之前插入一个数值

		void insert(iterator pos, const T& x) {assert(pos <= _finish);assert(pos >= _start);if (_finish == _endofstorage) {size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}memmove(pos + 1, pos, sizeof(_finish - pos) * (T));*pos = x;++finish;}

 测试

		cout << "-----------------------" << endl;cout << "现在进行插入测试" << endl;v.insert(v.begin(), 100);v.print(v);

程序崩溃

 

可以看出，pos指针出现问题了

分析 

根据代码回溯，我们可以发现，就我们传指针的时候设计到了pos迭代器，那我们从这开始

先判断是不是需要扩容 可以看到，是需要扩容的，我们接着往下看 

问题就出现在这里

扩容函数从来都不会说考虑pos的位置，也就是说当我扩容是，原来的pos并没有过来，反而是留在了原来的空间里被释放变成野指针，所以才出现了报错 

此种类型就是迭代器失效，本质就是pos扩容后失效了 

解决办法

同样要记录下原本pos的位置

		void insert(iterator pos, const T& x) {assert(pos <= _finish);assert(pos >= _start);cout << "我现在的数量是：" << size() << endl;cout << "我现在的容量是：" << capacity() << endl;if (_finish == _endofstorage) {size_t len = pos - _start;	//记录原本要的长度，用于恢复possize_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len;			//恢复pos}memmove(pos + 1, pos, sizeof(T)* (_finish - pos));*pos = x;++_finish;}

 自定义类型插入

此处跟reserve所用一样，采用vector<string>

结果处一样，同样无法达到string类深拷贝的问题

 swap

		void swap(vector<T>& v) {std::swap(_start, v._start);std::swap(_finish,v._finish);std::swap(_endofstorage,v._endofstorage);}

 operator=

		vector<T>& operator==(vector<T> v) {swap(v);return *this;}

注意

参数那里不能带引用，不带引用的话，只是一个拷贝，v只是一个拷贝对象，跟this内的内容交换就交换了，出了作用域也是要被销毁的，但是用来引用的话，就是原对象本身，这样原对象的值会被干掉的，变成this里的值

测试

	void test2() {vector<int> v1,v2;v1.push_back(1);v1.push_back(2);v2.push_back(3);v2.push_back(4);cout << "我原本的v1是：" << " ";for (auto e : v1) {cout << e << " ";}cout << endl;v1 = v2;cout << "我现在的v1是：" << " ";for (auto e : v1) {cout << e << " ";}cout << endl;}

报错了，那是因为我还没有构造函数呢

构造函数

		vector(const vector<T>& v) {_start = new T[v.capacity()];memcpy(_start, v._start, sizeof(T) * v.size());_finish = _start + v.size();_endofstorage = _start + v.capacity();}

此刻就很完美了 

resize

resize有三种情况

  • 一种是比原size大，但是未能超过capacity
  • 一种是超过capacity
  • 一种是比原size小

内置类型的默认构造

原本我们会认为 只有自定义类型才有默认构造，但是自C++不断发展以来，为了更好的与之兼容，比如，类模板的出现，让这个类显示的去推类型，从而知道它的初始值是什么。即当类模板一旦推出这个类型，就给予赋相应的值。

 

测试 

但是我们可以通过用reserve将第一种跟第二种直接连续起来 

		void resize(size_t n,T val=T()) {if (size() < n) {reserve(n);while (_finish != _start+n) {*_finish = val;_finish++;}}else {_finish = _start + n;}}

earse

		void earse(iterator pos) {assert(pos < _finish);assert(pos >= _start);iterator it = pos + 1;while (*it < _finish) {*(it - 1) = *it;}_finish--;}

测试

测试1

		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);for (auto e : v) {cout << e << " ";}cout << endl;v.earse(v.begin() + 3);for (auto e : v) {cout << e << " ";}cout << endl;

 

测试2

删除所有的偶数

		vector<int>::iterator it = v.begin();while (it != v.end()) {if (*it % 2 == 0) {v.erase(it);}else {it++;}}for (auto e : v) {cout << e << " ";}cout << endl;

我们看着好像一点问题都没有，其实不是，这种写法只是带有平常的偶然性罢了

我们换成STL里面的库来试试

测试3

	std::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);for (auto e : v) {cout << e << " ";}cout << endl;std::vector<int>::iterator it = v.begin();while (it != v.end()) {if (*it % 2 == 0) v.erase(it);elseit++;}for (auto e : v) {cout << e << " ";}cout << endl;}

这就报错了，也就是说换成stl的库里面的vector就顶不住 

分析

在VS下，它会进行强制的检查验证，它会认为erase了以后，这个it就会失效，不让我们再次使用了，我们回到STL文档里，看看设计者们是怎么解决的

 

解决方案

 STL中的vector容器对于erase，它会采取使用返回值的做法，就它会返回调用函数之后被删除的元素后面的那个元素，就直接指向新元素

 此刻就是没事的

构造函数再续

vector还有两种构造

 类模板里面的模板

类模板里是支持可以再次创建自己所需要的模板的

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

这里用 first != last 而不用 first< last的原因是

有些容器的迭代器底层并不是物理连续的！

另一个构造函数就跟resize的实现原理一模一样，这里就不再过多阐述，但是实现后的类模板会与上面的类模板构造函数，发生冲突。因为编译器会觉得这个构造要隐式转换，另外一个不会隐式转换，所以选类模板构造函数

以上就是本次博文的学习内容，如有错误，还望大佬指正，谢谢阅读


http://www.ppmy.cn/ops/89581.html

相关文章

【5G NAS】全球唯一临时标识符GUTI介绍

【5G NAS】全球唯一临时标识符GUTI介绍

博主未授权任何人或组织机构转载博主任何原创文章&#xff0c;感谢各位对原创的支持&#xff01; 博主链接 本人就职于国际知名终端厂商&#xff0c;负责modem芯片研发。 在5G早期负责终端数据业务层、核心网相关的开发工作&#xff0c;目前牵头6G技术研究。 博客内容主要围绕…
阅读更多...
C语言程序设计-[4] 算法和程序结构

C语言程序设计-[4] 算法和程序结构

1、算法 一个程序至少包含两个方面&#xff1a;数据结构和算法&#xff0c;算法就是为解决一个问题而采取的方法和步骤&#xff0c;即对程序操作步骤的描述。 算法有一定的评价标准和表示方法&#xff0c;其中流程图法和N-S结构图法是本章需要介绍的两种方法。 &#xff08;…
阅读更多...
Ability框架介绍

Ability框架介绍

Ability Ability是应用所具备能力的抽象&#xff0c;也是应用程序的基本组成部分&#xff0c;主要包括组件生命周期回调、系统环境变化通知、应用跳转、卡片开发等能力。 Ability框架模型两种形态 FA模型Stage模型 Stage模型 Stage模型中的应用组件是由Ability这个基础概念…
阅读更多...
安卓自定义控件

安卓自定义控件

文章目录 引入布局创建自定义控件 引入布局 首先创建一个项目&#xff0c;创建一个空的活动。然后右键单击res/layout创建一个Layout Resource File文件&#xff0c;取名title.xml。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmln…
阅读更多...
经典图论算法回顾之Bellman-Ford算法

经典图论算法回顾之Bellman-Ford算法

Dijkstra最短路径算法存在的一个问题是不能处理负权图&#xff08;详见&#xff1a;经典图论算法回顾之Dijkstra算法。今天要回顾的Bellman-Ford算法&#xff08;wikipedia&#xff1a;Bellman–Ford algorithm&#xff09;可以求出有负权图的最短路径&#xff0c;并可以对最短…
阅读更多...
【前端 20】Element-UI快速入门

【前端 20】Element-UI快速入门

探索Element UI组件库&#xff1a;快速搭建Vue应用的必备工具 在现代Web开发中&#xff0c;Vue.js以其轻量级和灵活性赢得了广泛的关注。而Element UI&#xff0c;作为Vue.js的一个UI组件库&#xff0c;更是为开发者们提供了丰富、易用的前端组件&#xff0c;极大地加速了开发过…
阅读更多...
TCL 实业 x TiDB丨从分销转向零售，如何考虑中台建设和数据库选型？

TCL 实业 x TiDB丨从分销转向零售，如何考虑中台建设和数据库选型？

导读 在数字化转型的浪潮中&#xff0c;TCL 实业通过“新方舟”项目构建统一中台&#xff0c;实现了从分销向零售的转型&#xff0c;显著提升了业务精准度和效率。本文根据 InfoQ 记者高玉娴对 TCL 实业企业架构部架构师蔡玖发的采访整理&#xff0c;揭秘了 TCL 实业在这一转型…
阅读更多...
Cocos Creator 3.8.x bundle核心知识点

Cocos Creator 3.8.x bundle核心知识点

bundle官网知识文档&#xff1a; https://docs.cocos.com/creator/3.8/manual/zh/asset/bundle.html bundle核心知识点如下&#xff1a;
阅读更多...
最新文章

Copyright @ 2022~2023