C++(vector的实现)

news/2024/10/10 22:43:55/

 1. vector介绍

         vector本质其实就是和我们数据结构中的顺序表类似，都是对一个数组进行增删查改等操作，但是这里vector的实现和顺序表的实现有所不同，vector的底层源码的实现是通过三个迭代器实现的，一个是指向开始的位置_start，一个是指向有效数据末尾的迭代器_finish还有一个是指向有效空间的迭代器_end_of_storage；而顺序表则是一个指针指向一块空间，和两个计数器int size计算有效空间内有效的元素个数和int capacity 记录有效空间大小的整形变量；

2. vector的实现

2.1 vector的类的基本结构

        如上所述，vector的实现是通过三个成员即三个迭代器实现的；但库内的vector的使用通常有可以使用不同的类型例如vector<int>， vector<char>，vector<double>等等，所以我们就需要实现一个vector的模板，然后还要实现他们的迭代器，我们同源码的迭代器实现不同，但迭代器其实就跟指针的用法几乎一样，所以我们这里通过指针来实现迭代器；如下代码所示：

template<class T>
class vector
{
public:typedef T* iterator;typedef const T* const_iterator;
private://有三个迭代器iterator _start = nullptr; //指向开头iterator _finish = nullptr;   //指向有效元素末尾后一个位置iterator _end_of_storage = nullptr;  //指向有效空间末尾
};

2.2 vector构造和析构函数的实现

        如上三个迭代器成员可见，我们已经给了缺省参数nullptr，那么在实例化的过程中我们只需要有一个构造函数，他们就会自动走初始化列表使用缺省参数进行初始化；而这里我们有了个创建一个构造函数的新的用法，这是在C++11才加进的；如下代码所示：

vector() = default;

然后是拷贝构造，拷贝构造其实就是实例化出一个新的对象，而新的对象的值和传入拷贝的对象的值相同，那我们就可以直接通过一个范围for让把被拷贝的对象的值依次插入实例化出的新的对象里面即可，这里先提前使用下面会讲到的内容，我们只需要知道push_back就是往里插入数据；

	vector(const vector<T>& v){for (auto e : v){push_back(e);}}

再者就是传入一段迭代器进行构造实例化出新的对象；但我们这里要重新写一个模板，这样我们就可以把一些不同类型的不同结构的对象存到vector里面来；

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

最后是析构函数就不过多介绍；

	~vector(){if (_start)delete[]_start;_start = nullptr;_finish = nullptr;_end_of_storage = nullptr;}

2.3 赋值运算符重载、swap、begin()、end()、capacity()、size()

swap的实现：由于和string类的实现一样，如果说我们调用库的swap并且是大量的数据进行交换的话效率会降低效率；如下图：

至于为什么会降低效率是因为红色方框那里会调用一次拷贝构造；然后绿色方框那也说了会降低效率，所以我们自主实现一个在类内且不会调用拷贝构造的swap；如下代码所示： 

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

赋值运算符重载的实现：如下图

赋值运算符重载其实只需要调用swap就可以，而且我们的参数是传值 不是传引用，所以不会对v的原数据造成影响，最后再返回*this即可；如下代码所示：

	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& operator=(vector<T> v){swap(v);return *this;}

然后是begin()传回首元素的迭代器、end()传回尾部元素的迭代器、capacity()传回有效空间大小、size()传回有效元素个数以及empty()判断vector容器是否为空的实现如下；

begin()和end()其实就是直接返回_start和_finish即可，但是他们还有一个const_iterator就是指向不可被修改的所以实现了两种；如下代码所示：

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

capacity()和size()这里返回他们的大小，应该是整型才对，但是我们的底层是迭代器，那该怎么办呢？ 其实这里涉及到我们指针的一个知识点，那就是指针减指针返回的是两个指针之间的元素个数，那我们就用用到这里来；如下代码所示：

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

最后一个是判空empt()，这个其实只需要看他的_start指向的空间和_finish指向的空间是否是同一块空间即可如下代码所示：

	bool empty(){return _start == _finish;}

2.4 reserve的实现（重点）

reserve就是预先开空间，如果说开的空间比原有的空间小的话capacity 和size不会变化，但是比原有的空间大的话就会给他们开足n个空间；如下测试可知：

#include<vector>
#include<iostream>
using namespace std;int main()
{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);v.push_back(7);cout << "capcaity is:> " << v.capacity() << endl;cout << "size is:> " << v.size() << endl;v.reserve(3);cout << "After reserve(3) capcaity is:> " << v.capacity() << endl;cout << "After reserve(3) size is:> " << v.size() << endl;v.reserve(20);cout << "After reserve(20) capcaity is:> " << v.capacity() << endl;cout << "After reserve(20) size is:> " << v.size() << endl;return 0;}

👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇

运行结果为：

那我们的实现也要和源码的功能一样，如果n比capacity小则不出现变化，如果比capacity大的话就需要进行扩容，而这里也涉及了深浅拷贝问题，我们需要自己new一段n一样大的空间然后把数据往里放，我先直接上代码，里面有些需要注意的地方在下面进行讲解：

	void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* temp = new T[n];//memcpy(temp, _start, size() * sizeof(T));for (size_t i = 0; i < old_size; i++){temp[i] = _start[i];}delete[]_start;_start = temp;//_finish = temp + size();//这个是错误的示范，因为delete掉_start了，//那temp = _strt +size()（_finish-_start) 就为_finish，但是finish为NULL//因为已经被释放了_finish = temp + old_size;_end_of_storage = temp + n;}}

重点！重点！重点！重点！重点！重点！重点！重点！重点！重点！重点！重点！重点！

（内心所言：换个颜色的字体会不会让眼睛看的舒服点哈哈哈哈）

首先需要注意的第一点是：上面代码加了一个old_size进行记录size()并不是多余，如果说上面不加的话会出现错误，因为前面已经释放了_start，而size() = _finish - _start， 而_finish还指向原来已经被释放的空间，_finish = temp + _finish - _start；而_start = temp，_finish被释放了为NULL， 所以最后的结果会为NULL，所以我们需要预先把size()保存下来；

然后先说一下赋值运算符重载vv = v的实现实质上是把vv原有的空间释放掉，然后开一片和v一样大的空间，上面做到了开一样的空间，而只需要把v的值复制到vv就可以，但为什么我把memcpy注释掉了呢？ 因为memcpy只是进行单纯的值和值赋值操作，如果说我用一个vector容器储存string类呢？ 只进行值的拷贝就会导致浅拷贝而出现错误；下面举出了例子：

template<class T>
class vector
{
public:typedef T* iterator;typedef const T* const_iterator;void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* temp = new T[n];memcpy(temp, _start, size() * sizeof(T));delete[]_start;_start = temp;_finish = temp + old_size;_end_of_storage = temp + n;}}private://有三个迭代器iterator _start = nullptr; //指向开头iterator _finish = nullptr;   //指向有效元素末尾后一个位置iterator _end_of_storage = nullptr;  //指向有效空间末尾
};void test2()
{vector<string> v;v.push_back("11111111111111111111");v.push_back("11111111111111111111");v.push_back("11111111111111111111");v.push_back("11111111111111111111");Print_Container(v);v.push_back("11111111111111111111");Print_Container(v);
}int main()
{test2();return 0;
}

这里就是把memcpy解开了，那让我们来看看结果如何

👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇

运行结果为：

出现很多随机值，正如我们所说，单纯的memcpy只会把值进行浅拷贝如下图所示：

但为什么我们只进行单纯的赋值操作就可以实现深拷贝了呢？那是因为我们传了string类型即vector<string>，而改段赋值其实就是调用了string里的赋值运算符，库内的已经重载过了，所以会进行深拷贝操作；

2.5 push_back和pop_back()操作实现

其实也没有什么可讲的，因为和string类实现的非常相似，我们只需要注意当容器满的时候就需要进行扩容，然后把值放到*_finish里，然后finish还要往后走；而尾删pop_back更简单，因为她不需要考虑空间是否充足，只需要看空间是否为空即可；如下代码所示：

		void push_back(const T& x){if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}(*_finish) = x;_finish++;}void pop_back(){assert(!empty());--_finish;}

2.6 resize的实现

resize顾名思义就是改变size的，实现他的话有两种需要注意的情况，第一种如果说改变的大小n如果size < n < capacity的话则需要改变_finish的位置，但是capacity不会变；第二种如果说n>capacity的话则需要扩容，如果有给值则初始化新开的空间的值，如果没有则给匿名对象实例化出的值进行初始化如下代码所示：

		void resize(size_t n, T val = T()){if (n < size()){_finish = _start + n;}//这里包括两种情况，一种是 size < n < capacity;//还有一种是capacity < n 那就需要拿n来进行扩容操作，而这步操作在reserve(n)//会实现else{reserve(n);while (_finish < _start + n){*_finish = val;_finish++;}}}

这里第二个参数是T val = T()，T()其实就是匿名对象（这也看出匿名对象的作用，就是给不知道给什么类型缺省值的参数用的）；

2.7 insert和erase的实现

insert不单纯只是说插入数据，这里面还涉及到一个迭代器失效的知识点，就是当如果调用v.insert(p,10) 想在p的位置插入10的，但出现了空间不足需要扩容的情况后，p迭代器需要被更新，因为扩容后是新开的一块空间，但p还指向原来的空间，所以会出现野迭代器的情况；而解决方案是，我们先记录相对位置，即len = _start到pos位置的距离，最后再让pos走到相对位置处即pos = _start +len最后再返回pos即可；

上面标色的是特殊的迭代器失效的情况；下面是实现insert的思路：

1. 首先判断空间是否充足，因为你要插入数据；

2. 插入数据前需要把数据往后挪，然后再在pos位置插入数据；

3. 最后记得让_finish++, 因为插入数据后容量发生变化；如下代码所示：

		iterator insert(iterator pos, const T& v){if (_finish == _end_of_storage){//记下相对位置,因为扩容会让迭代器失效，成为野迭代器size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = v;++_finish;return pos;}

erase的实现：

erase也会出现迭代器失效的问题，如果说编译器出现缩容的情况下也会出现和上面insert的一样，而且还有一种情况就是如果说erase了某个迭代器，那么我们就不能对这个迭代器进行访问，因为编译器会强行检察报错，他们不允许再使用一个调用了erase且未更新的迭代器；如下代码所示：

	void testErase(){std:: vector<int>v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5); auto it = v.begin();while (it != v.end()){if (*it % 2 == 0){v.erase(it);}else{++it;}}}

👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇

调试结果为：

直接崩掉了，但我们加上it = v.erase更新他的话就可以过；如下代码所示：

	void testErase(){std:: vector<int>v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5); auto it = v.begin();while (it != v.end()){if (*it % 2 == 0){it = v.erase(it);}else{++it;}}}

👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇  👇

运行结果为：

所以由此可见erase的返回值应该是个迭代器，那么我们就可以来实现自己的erase；

实现思路：

1、首先要判断pos的位置不能不在有效数据内

2、删除操作和顺序表一样，直接让后面的数覆盖需要删除的数即可；

3、最后需要--finish 因为删掉了数据，然后还要返回pos；如下代码所示：

		iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);auto it = pos + 1;while (it != end()){*(it - 1) = *it;++it;}--_finish;return pos;}

2.8 方括号重载即下标访问

直接返回对应下标的值即可直接上代码：

		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.9 实现Print_vector操作

打印值其实很简单，但是里面有一点需要注意的是：在没有实例化的类模板里，编译器不能区分const_iterator是类型还是静态成员变量所以需要在前面加个typename，还有另外的解决方案如下代码所示：

	template<class T>void Print_vector(const vector<T>& v){// 规定，没有实例化的类模板里面取东西，编译器不能区分这里const_iterator// 是类型还是静态成员变量，需要在前面加个typenamevector<T>::const_iterator it = v.begin();//或者换一种//auto it = v.begin();//第一种遍历vector容器while (it != v.end()){cout << *it << " ";++it;}cout << endl;//第二种遍历vector容器//for (auto e : v)//{//	cout << e << " ";//}//cout << endl;}

2.10 实现打印所有容器（加餐）

	template <class Container>void Print_Container(const Container& v){for (auto e : v){cout << e << " ";}cout << endl;}

3. 完整的vector实现代码如下

vector.h

#pragma once
#include<iostream>
#include<assert.h>
#include <vector>
namespace Tao
{using namespace std;template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//构造函数//这个是前置构造函数vector() = default;vector(const vector<T>& v){for (auto e : v){push_back(e);}}template<class InterIterator>vector(InterIterator first, InterIterator last){while (first != last){push_back(*(first));++first;}}~vector(){if (_start)delete[]_start;_start = nullptr;_finish = nullptr;_end_of_storage = nullptr;}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& operator=(vector<T> v){swap(v);return *this;}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}size_t capacity()const{return _end_of_storage - _start;}size_t size()const{return _finish - _start;}bool empty(){return _start == _finish;}//reserve开空间void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* temp = new T[n];//memcpy(temp, _start, size() * sizeof(T));for (size_t i = 0; i < old_size; i++){temp[i] = _start[i];}delete[]_start;_start = temp;//_finish = temp + size();//这个是错误的示范，因为delete掉_start了，//那temp = _strt +size()（_finish-_start) 就为_finish，但是finish为NULL//因为已经被释放了_finish = temp + old_size;_end_of_storage = temp + n;}}void push_back(const T& x){if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}(*_finish) = x;_finish++;}void pop_back(){assert(!empty());--_finish;}void resize(size_t n, T val = T()){if (n < size()){_finish = _start + n;}//这里包括两种情况，一种是 size < n < capacity;//还有一种是capacity < n 那就需要拿n来进行扩容操作，而这步操作在reserve(n)//会实现else{reserve(n);while (_finish < _start + n){*_finish = val;_finish++;}}}iterator insert(iterator pos, const T& v){if (_finish == _end_of_storage){//记下相对位置,因为扩容会让迭代器失效，成为野迭代器size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = v;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);auto it = pos + 1;while (it != end()){*(it - 1) = *it;++it;}--_finish;return pos;}T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i)const{assert(i < size());return _start[i];}private://有三个迭代器iterator _start = nullptr; //指向开头iterator _finish = nullptr;   //指向有效元素末尾后一个位置iterator _end_of_storage = nullptr;  //指向有效空间末尾};template<class T>void Print_vector(const vector<T>& v){// 规定，没有实例化的类模板里面取东西，编译器不能区分这里const_iterator// 是类型还是静态成员变量，需要在前面加个typenamevector<T>::const_iterator it = v.begin();//或者换一种//auto it = v.begin();//第一种遍历vector容器while (it != v.end()){cout << *it << " ";++it;}cout << endl;//第二种遍历vector容器//for (auto e : v)//{//	cout << e << " ";//}//cout << endl;}template <class Container>void Print_Container(const Container& v){for (auto e : v){cout << e << " ";}cout << endl;}

END!


http://www.ppmy.cn/news/1537153.html

相关文章

vim寄存器使用

vim寄存器使用

前言 我们需要知道 当我们在vim中拷贝或者剪切一段数据之后&#xff0c;数据就会被存放到指定的寄存器中&#xff0c;而当我们粘贴数据时&#xff0c;数据便会从相应的寄存器把数据粘贴到光标对应位置默认情况下&#xff0c;我们需要拷贝的数据会被存放在匿名寄存器("&qu…
阅读更多...
MySQL 日志 - Binlog

MySQL 日志 - Binlog

文章目录 binlog 的格式mysqbinlog 工具SHOW binlog events;binlog 和 redo log 对比 https://dev.mysql.com/doc/refman/8.4/en/binary-log.html binlog 全称 BinaryLog&#xff0c;是 MySQL 数据库中用于记录所有更改数据库状态的事件的日志文件。它主要用于以下几个目的&am…
阅读更多...
Spark常用RDD算子：transformation转换算子以及action触发算子

Spark常用RDD算子：transformation转换算子以及action触发算子

文章目录 1. 算子&#xff08;方法&#xff09;介绍2. 常用transformation算子2.1 map 2.2 flatMap2.3 filter2.4 distinct2.6 groupBy2.7 sortBy()2.8 k-v数据[(k,v),(k1,v1)] 3. 常用action算子 1. 算子&#xff08;方法&#xff09;介绍 rdd中封装了各种算子方便进行计算&a…
阅读更多...
python34_可变字符串

python34_可变字符串

可变字符串 说明 在 Python 中&#xff0c;字符串属于不可变对象&#xff0c;不支持原地修改&#xff0c;如果需要修改其中的值&#xff0c;智能创建新的字符串对象。 但是&#xff0c;经常我们确实需要原地修改字符串&#xff0c;可以使用 io.StringIO对象或 array 模块impo…
阅读更多...
【论文阅读】Segment Anything Model for Road Network Graph Extraction

【论文阅读】Segment Anything Model for Road Network Graph Extraction

【论文阅读】Segment Anything Model for Road Network Graph Extraction (CVPRW 2024) Paper链接&#xff1a;https://openaccess.thecvf.com/content/CVPR2024W/SG2RL/html/Hetang_Segment_Anything_Model_for_Road_Network_Graph_Extraction_CVPRW_2024_paper.html 文章目录…
阅读更多...
关系运算（2）

关系运算（2）

关系代数 上一篇博客已经讲了基本关系代数运算的内容&#xff0c;今天来讲附加关系代数运算。 附加关系代数运算 交运算∩ 查询计算机系年龄大于等于18的学生的信息 跟并集∪一样都是需要先进行选择运算然后再进行二元的交集运算。 其实交运算也可以用差运算来表示&#xff…
阅读更多...
国际 Android WPS Office v18.13 解锁版

国际 Android WPS Office v18.13 解锁版

WPS Office 移动版&#xff0c;设计不断优化&#xff0c;性能再次提升&#xff01;融入Google Android最新设计标准&#xff0c;Material Design设计风格&#xff0c;完美支持沉浸式&#xff01;简化文档操作&#xff0c;全新移动办公力作。全新界面更清晰舒适&#xff0c;功能…
阅读更多...
27.数据结构与算法-图的遍历（DFS,BFS）

27.数据结构与算法-图的遍历（DFS,BFS）

遍历定义与遍历实质 图的特点 图的常用遍历方法 深度优先搜索-DFS 邻接矩阵表示的无向图深度遍历实现 DFS算法效率分析 非连通图的遍历 广度优先搜索遍历-BFS 邻接表表示的无向图广度遍历实现 BFS算法效率分析 非连通图的广度遍历 DFS和BFS算法效率比较
阅读更多...
最新文章

Copyright @ 2022~2023