vector类的模拟实现

 实现基本的vector框架

参考的是STL的一些源码,实现的vector也是看起来像是一个简略版的,但是看完能对vector这个类一些接口函数更好的认识。

我们写写成员变量,先来看看STL的成元变量是那些

namespace tjl
{template<class T>class vector{public:typedef T* iterator;vector():_start(nullptr),_finish(nullptr),_eof(nullptr){}private:iterator _start;//iterator _finish;iterator _eof;//表示的是end_of_storage};}

这里的成员变量有些不一样,我们也用iterator来表示,其实这里就是一个指针,但是用迭代器的名称来称呼它,还有我们这里加上了模板,更加凸显了vector的不一样,这样的好处就是我们这个vector这个类就可以去适应各种不同的类型,达到一个____效果(填一个四字成语)。

实现构造函数

构造函数的意义就是来进行初始化,因为我们构造函数里面都是会走初始化列表的这个过程的,所以我们就可以写成这个样子。

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

但是要注意的是我们的库里面的构造函数可不是只有这些,大家可以也来查询我们的网站来查看

vector构造函数

我们可以看到他是可以支持迭代器进行构造的,也就是说我们这里可以使用任意类型来进行构造

也可以用给值的方式,所以vector的作用还是很大的。
 

析构函数的实现

析构函数的作用就是在我们程序结束的时候对我们的空间进行释放,所以我们可以这样写

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

这里我们可以增加if这个判断,因为_start可能是为空的,所以我们可以写一个对它进行检查的功能。

实现vector的size()和capacity()

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

我们这里的实现细节其实只要注意的是const,因为我们可能是const对象进行调用,所以这里可以加上const,防止我们的权限进行放大。

实现push_back

这里的实现会有点小细节值的我们注意,我们先来想想push_back是在尾部插入数据·就可以了,但是我们可不可能如果当我们的空间是满的时候,就会遇到需要扩容的问题,所以这个时候我们需要先来写一个reserve的函数来进行扩容

reserve函数的实现

因为我们每次扩容的时候到要用到这个函数,比如尾插还是随机插入都会用到,那我们的思路是那些还有注意事项呢?

首先我们得先知道一个问题就是我们当什么时候才是要扩容的时候,因为reserve会传一个参数n

表示我们得开多大的空间,所以我们需要做的时候就是先判断要不要开这么大的空间。

先来看我们的代码

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

思路就是我们重新开辟一块空间,然后把原来空间的内容拷贝到新内容上,这里要注意的是当我们赋值的时候,就是给_start和_finish给值的时候要先记录pos位置,因为我们扩容的时候是重新开辟的,可能存在_finish进行赋值的时候它还是指向空,这样就出现空指针的现象了。

那我们实现reserve之后就可以继续来实现push_back函数了。

void push_back(const T& val){if (_finish == _eof){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = val;++_finish;}

先检查空间是不是够,如果空间不够我们就需要进行扩容,其次就是大家这里要明白一个点,为什么我们可以对_finish进行解引用,然后直接进行给值,原因就是val的类型。

实现operator[]

这个很简单直接一把过了。

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

用[]进行遍历来看看。

void test1()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (int i = 0; i < v.size(); i++){cout << v[i] << " ";}
}

迭代器的实现

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

因为迭代器我们必须要给它命名begin和end要不然就不能使用范围for来进行遍历,我们现在可以用迭代器来对我们的数据进行遍历,也能使用范围for,这里两种方式都写出来给大家看看。

void test1(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (int i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;for (auto e : v){cout << e << " ";}auto it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;}

这样有三种方式可以对我们进行遍历了,完成迭代器只后需要来处理一些细节问题,还是我们权限放大的问题,因为当我们用const的对象去调用的时候就不行了,这里只需要在写一个const版本的🆗了,我们可以先typedef一下。

typedef const T* const_iterator;

这样就表示这个迭代器是const修饰过的迭代器。那它的begin和end就是这样写的。

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

不过我们对const的迭代器只能进行读的操作就不能进行写操作了。

迭代器失效问题

这个问题是出现在insert和erase的时候是会出现问题

首先我们实现insert需要注意的细节有哪些

和我们之前遇到的顺序表其实本质是没有多大区别的,这里用的是指针,而不是数组下标,因为这里模拟实现的时候,其实我们的迭代器就是原生指针,虽然和VS里的不一样,Vs里的iterator并不是原生指针,所以很好实现我们这里的insert,来看看代码吧。

iterator insert(iterator pos, const T& val = T()){assert(pos >= begin());assert(pos <= end());size_t len = pos - _start;if (_finish == _eof){reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = val;++_finish;return pos;}

其实这里我就一步到位了,但是还是有很多的细节值的我们去注意,第一个就是为什么说这里会有迭代器失效的问题,首先就是如果我们步扩容的时候迭代器是不会失效的,但是扩容之后的pos还是指向原来控空间的,因为我们这里的扩容的步骤是开空间,然后对我们的内容进行值拷贝,释放之前的空间,这样pos就是一个野指针,所以我们需要做的就是更新pos位置到新的空间上,可以先记住pos的相对位置,然后更新。所以这里这个坑是没有位置的,还有一个需要注意的是我们需要更新外面的pos,因为形参的改变是不会影响实参的改变的,所以这里的一个重要的步骤就是返回pos的值。

迭代器的失效:第一个重要的原因就是这个指针变成野指针了,我们需要更新它

第二个原因就是当我们进行insert的时候需要进行返回,因为我们在这个函数内改变了,但是在外面还是没有进行改变(形参的改变是不会影响实参的改变的)

我们来进行测试一下

void test2(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (auto e : v){cout << e << " ";}cout << endl;auto pos = find(v.begin(), v.end(), 2);v.insert(pos, 100);for (auto e : v){cout << e << " ";}}

发现最后的结果也是正确的,这样还要提醒大家,我们认为insert和erase之后的迭代器是失效的,不再使用,虽然我们可以接受pos位置,但是最好还是不要使用。

实现erase

iterator erase(iterator pos){assert(pos >= begin());assert(pos < end());iterator start = pos;while (start < _finish){*start = *(start + 1);start++;}_finish--;return pos;}

这个erase也是很简单,就是移动进行数据的覆盖就可以解决问题了。我们也来测试一下看看结果是不是对的。

void test3(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (auto e : v){cout << e << " ";}cout << endl;auto pos = find(v.begin(), v.end(), 2);v.erase(pos);for (auto e : v){cout << e << " ";}cout << endl;}

深浅拷贝问题

先来实现拷贝构造。

拷贝构造的实现可以有现代写法和原始写法,我们先来写原始写法那个,然后引出我们的深浅拷贝的问题。

	vector(const vector<T>& v){reserve(v.capacity());memcpy(_start, v._start, sizeof(T) * v.size());}

我们这里进行的值拷贝,是按照字节的拷贝的,如果我们T是内置类型的时候,我们的的代码是不会出现问题的,但是如果是string或者里面还是一个vector<int>的时候代码就会出现问题,我们可以先来看看string的结果。

void test4(){vector<string> v;v.push_back("111111");v.push_back("111111");v.push_back("111111");for (auto e : v){cout << e << " ";}cout << endl;vector<string> v1(v);for (auto e : v1){cout << e << " ";}}

我们这样写的时候就是会出现错误,原因是我们这里的拷贝构造是进行的值拷贝,不过如果我们不写这个拷贝构造的时候是不会出现问题的,原因string会去调用它自己的拷贝构造。

但是其根本原因还是我们扩容的是进行的是值拷贝和我们没有写拷贝构造造成的问题。现在来修改一下reserve。

void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];size_t pos = _finish - _start;if (_start){//memcpy(tmp, _start, sizeof(T) * size());for (size_t i = 0; i < size(); i++){tmp[i] = _start[i];}delete[]_start;}_start = tmp;_finish = _start + pos;_eof = _start + n;}}

然后加上我们的考拷贝构造。

vector(const vector<T>& v){reserve(v.capacity());for (size_t i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_eof = _start + v.capacity();}

这个就是原始的写法,这样我们的代码是没有问题的,但是这里为什么没有问题的第一个原因就是string是我们库里面的,进行赋值的时候会去调用它的赋值重载,但是如果我们这里的类型是vector<vector<int>>又会出现问题,我们可以来看看,如果我们需要拷贝一个杨辉三角的时候,会不会有问题。

下面来演示一下,我们可以先把杨辉三角的代码直接先拿过来

class Solution {public:vector<vector<int>> generate(int numRows) {vector<vector<int>> vv;vv.resize(numRows, vector<int>());//进行初始化//进行的是每行初始化,因为这里表示的是顺序表里面是个顺序表for (int i = 0; i < vv.size(); i++)//初始化没列{vv[i].resize(i + 1, 0);vv[i][0] = vv[i][vv[i].size() - 1] = 1;}for (int i = 0; i < vv.size(); i++){for (int j = 0; j < vv[i].size(); j++){if (vv[i][j] == 0){vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];}}}return vv;}};

然后进行拷贝一个杨辉三角,看看有没有什么问题

void test5(){vector<vector<int>> v = Solution().generate(5);auto v1(v);for (int i = 0; i < v1.size(); i++){for (int j = 0; j < v1[i].size(); j++){cout << v1[i][j] << " ";}cout << endl;}}

熟悉的感觉,真是太美妙了 

那我们其实可以通过调试来看看问题所在的地方。

 

可以看到什么不一样的地方,一个就是我们的外面的大vector是完成了深拷贝,里面还是没有,为什么其他类型的string就可以,因为string有它自己的赋值重载,我们这里没有写vector的赋值重载,所以才会有这样的问题,那我们只需要写一个赋值重载就可以解决问题了。

 

void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_eof, v._eof);}vector<T>& operator=( vector<T>& v){swap(v);return *this;}

这样我们的问题就能够很好的解决了。

那我们再来完善一下其他的接口函数就解决了。

pop_back的实现
void pop_back(){erase(--end());}
	template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}

完整的代码实现

#pragma once
#include<assert.h>
namespace tjl
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;vector():_start(nullptr),_finish(nullptr),_eof(nullptr){}vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _eof(nullptr){reserve(n);while (n--){push_back(val);}}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_eof, v._eof);}vector<T>& operator=( vector<T> v){swap(v);return *this;}vector(int n, const T& val = T()):_start(nullptr), _finish(nullptr), _eof(nullptr){reserve(n);while (n--){push_back(val);}}template<class inputiterator>vector(inputiterator first, inputiterator last): _start(nullptr), _finish(nullptr), _eof(nullptr){while (first != last){push_back(*first);++first;}}vector(const vector<T>& v): _start(nullptr), _finish(nullptr), _eof(nullptr){reserve(v.capacity());for (size_t i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_eof = _start + v.capacity();}void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];size_t pos = _finish - _start;if (_start){//memcpy(tmp, _start, sizeof(T) * size());for (size_t i = 0; i < size(); i++){tmp[i] = _start[i];}delete[]_start;}_start = tmp;_finish = _start + pos;_eof = _start + n;}}iterator begin(){return _start;}iterator end(){return _finish;}const T& operator[](size_t pos) const{return _start[pos];}T& operator[](size_t pos) {return _start[pos];}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}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(const T& val){if (_finish == _eof){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = val;++_finish;}size_t size()const{return _finish - _start;}size_t capacity() const{return _eof - _start;}iterator insert(iterator pos, const T& val = T()){assert(pos >= begin());assert(pos <= end());size_t len = pos - _start;if (_finish == _eof){reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = val;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= begin());assert(pos < end());iterator start = pos;while (start < _finish){*start = *(start + 1);start++;}_finish--;return pos;}~vector(){if (_start){delete[]_start;_start = _finish = _eof = nullptr;}}private:iterator _start;//iterator _finish;iterator _eof;//表示的是end_of_storage};class Solution {public:vector<vector<int>> generate(int numRows) {vector<vector<int>> vv;vv.resize(numRows, vector<int>());//进行初始化//进行的是每行初始化,因为这里表示的是顺序表里面是个顺序表for (int i = 0; i < vv.size(); i++)//初始化没列{vv[i].resize(i + 1, 0);vv[i][0] = vv[i][vv[i].size() - 1] = 1;}for (int i = 0; i < vv.size(); i++){for (int j = 0; j < vv[i].size(); j++){if (vv[i][j] == 0){vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];}}}return vv;}};void test1(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (int i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;for (auto e : v){cout << e << " ";}auto it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;}void test2(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (auto e : v){cout << e << " ";}cout << endl;auto pos = find(v.begin(), v.end(), 2);v.insert(pos, 100);for (auto e : v){cout << e << " ";}}void test3(){vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (auto e : v){cout << e << " ";}cout << endl;auto pos = find(v.begin(), v.end(), 2);v.erase(pos);for (auto e : v){cout << e << " ";}cout << endl;}void test4(){vector<string> v;v.push_back("111111");v.push_back("111111");v.push_back("111111");for (auto e : v){cout << e << " ";}cout << endl;vector<string> v1(v);for (auto e : v1){cout << e << " ";}}void test5(){vector<vector<int>> v = Solution().generate(5);auto v1(v);for (int i = 0; i < v1.size(); i++){for (int j = 0; j < v1[i].size(); j++){cout << v1[i][j] << " ";}cout << endl;}}}

今天的分享就到这里了,我们下次再见!!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/253606.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

无损音乐下载,最新音乐下载,mp3格式音乐下载,一键下载mp3格式音乐,我只用这个软件,歌曲资源丰富,全网音乐免费下载,稳定运行,告别收费

一、软件简介 现在很多支持一键下载mp3音乐/无损音质音乐的音乐播放器通常都是解析接口套了一个壳&#xff0c;一旦解析接口失效&#xff0c;软件就不能下载音乐了&#xff0c;因此一个稳定的解析接口是这类软件最大的保障。本次小编推荐的音乐下载软件接口非常稳定&#xff0…

C语言:函数

创作不易&#xff0c;友友们给个三连吧&#xff01;&#xff01; 一、函数的概念 数学中我们见过函数的概念&#xff0c;例如ykxb&#xff0c;k和b都是常数&#xff0c;给任意一个x就可以得到y 而C语言也引入了函数&#xff08;function&#xff09;这个概念&#xff0c;C语…

利用LLM大模型生成sql的深入应用探究

Chat2DB 是一款有开源免费的多数据库客户端工具,和传统的数据库客户端软件Navicat、DBeaver 相比 Chat2DB 集成了 AIGC 的能力&#xff0c;能够将自然语言转换为 SQL&#xff0c;也可以将 SQL 转换为自然语言&#xff0c;可以给出研发人员 SQL 的优化建议&#xff0c;极大地提升…

初识C语言·预处理详解

目录 1 预定义符号 2 define定义常量 3 #define定义宏 4 带有副作用的宏 5 宏替换的规则 6 宏和函数的对比 7 # 和 ## i) #运算符 ii) ##运算符 8 命名约定 9 命令行定义 10 条件编译 条件编译1&#xff1a; 条件编译2&#xff1a; 条件编译3&#xff1a; 条件…

单片机学习笔记---LED点阵屏的工作原理

目录 LED点阵屏分类 LED点阵屏显示原理 74HC595的介绍 一片74HC595的工作原理 多片级联工作原理 总结 LED点阵屏由若干个独立的LED组成&#xff0c;LED以矩阵的形式排列&#xff0c;以灯珠亮灭来显示文字、图片、视频等。LED点阵屏广泛应用于各种公共场合&#xff0c;如汽…

鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之ScrollBar组件

鸿蒙&#xff08;HarmonyOS&#xff09;项目方舟框架&#xff08;ArkUI&#xff09;之ScrollBar组件 一、操作环境 操作系统: Windows 10 专业版、IDE:DevEco Studio 3.1、SDK:HarmonyOS 3.1 二、ScrollBar组件 鸿蒙&#xff08;HarmonyOS&#xff09;滚动条组件ScrollBar&…

Logback - 日志框架

引言 在当今的企业级应用开发中&#xff0c;日志管理是一个不可或缺的部分。它不仅帮助我们进行错误跟踪&#xff0c;还能有效监控应用程序的运行状态&#xff0c;为性能优化提供数据支撑。Spring Boot作为一个简化Spring应用开发的框架&#xff0c;自带了强大的日志管理功能。…

如何用python进行数据分析?

前言 很多人可能会有这样的疑问&#xff0c;数据分析Excel挺强大的&#xff0c;会Excel就行&#xff0c;为什么还要去学python&#xff1f; 是的&#xff0c;Excel和python对于数据分析而言&#xff0c;这两者都只是不同的工具而已。 但&#xff0c;有一点我们要考虑&#x…

iOS 需求 多语言(国际化)App开发 源码

一直觉得自己写的不是技术&#xff0c;而是情怀&#xff0c;一个个的教程是自己这一路走来的痕迹。靠专业技能的成功是最具可复制性的&#xff0c;希望我的这条路能让你们少走弯路&#xff0c;希望我能帮你们抹去知识的蒙尘&#xff0c;希望我能帮你们理清知识的脉络&#xff0…

路由器、路由器的构成、交换结构

目录 1 路由器 1.1 路由器的结构 “转发”和“路由选择”的区别 1.1.1 输入端口对线路上收到的分组的处理 1.1.2 输出端口将交换结构传送来的分组发送到线路 2.2 交换结构 2.2.1 通过存储器 2.2.2 通过总线 2.2.3 通过纵横交换结构 (crossbar switch fabric) 1 路由器…

BUGKU-WEB 留言板

题目描述 题目无需登录后台&#xff01;需要xss平台接收flag&#xff0c; http协议需要http协议的xss平台打开场景后界面如下&#xff1a; 解题思路 看到此类的题目&#xff0c;应该和存储型xss有关&#xff0c;也就是将恶意代码保存到服务器端即然在服务器端&#xff0c;那就…

CSS 闪电按钮效果

<template><view class="const"><div class="voltage-button"><button>闪电按钮</button><svg version="1.1" xmlns="http://www.w3.org/2000/svg" x="0px" y="0px" viewBox=&q…

简易计算器的制作(函数指针数组的实践)

个人主页&#xff08;找往期文章包括但不限于本期文章中不懂的知识点&#xff09;&#xff1a; 我要学编程(ಥ_ಥ)-CSDN博客 前期思路&#xff08;菜单的制作等&#xff09;&#xff1a;利用C语言的分支循环少量的函数知识写一个猜数字的小游戏-CSDN博客 计算器的制作其实与游…

使用ChatGpt和文心一言辅助文章创作

近期在写数字水浒系列文章&#xff0c;使用了ChatGpt和文心一言进行辅助创作&#xff0c;整体感受不错&#xff0c;提高了工作效率。 在使用过程中&#xff0c;感觉文心的中文能力更强一些&#xff0c;主要体现在&#xff1a; 1 语料库更大&#xff0c;比如对水浒传了解的更多…

Postman(接口测试工具),什么是Postman接口

目录 一.基本介绍 Postman 是什么Postman 快速入门快速入门需求说明 二.Postman 完成 Controller 层测试 需要的代码&#xff1a; Java类request.jspsuccess.jsp1. 完成请求2. 完成请求3. 完成请求4. 完成请求5. 完成请求 三.发送join 目录 一.基本介绍 Postman 是什么 …

微信小程序解决华为手机保存图片到相册失败

1.新增隐私设置 2.优化代码 新增uni.authorize判断 _saveCode() {let that this;console.log(点击了保存图片)console.log(this.result)uni.authorize({scope: scope.writePhotosAlbum,success(e) {console.log(e)if (this.result ! "") {uni.saveImageToPhotosAlb…

一步步建立一个C#项目(连续读取S7-1200PLC数据)

这篇博客作为C#的基础系列,和大家分享如何一步步建立一个C#项目完成对S7-1200PLC数据的连续读取。首先创建一个窗体应用。 1、窗体应用 2、配置存储位置 3、选择框架 拖拽一个Button,可以选择视图菜单---工具箱 4、工具箱 拖拽Lable控件和TextBook控件 5、拖拽控件 接下来…

C# 实现微信自定义分享

目录 需求与调整 代码实现 获取令牌 生成合法票据 获取有效签名 客户端准备 客户端实现 小结 需求与调整 在微信中打开网页应用后&#xff0c;可以选择将地址发送给朋友进行分享&#xff0c;如下图&#xff1a; 在实际的应用中&#xff0c;我们可能不是简单的将该网页…

进程控制(Linux)

进程控制 一、进程创建1. 再识fork2. 写时拷贝 二、进程终止前言——查看进程退出码1. 退出情况正常运行&#xff0c;结果不正确异常退出 2. 退出码strerror和errno系统中设置的错误码信息perror异常信息 3. 退出方法exit和_exit 三、进程等待1. 解决等待的三个问题2. 系统调用…

Unity_ShaderGraph节点问题

Unity_ShaderGraph节点问题 Unity版本&#xff1a;Unity2023.1.19 为什么在Unity2023.1.19的Shader Graph中找不见PBR Master节点&#xff1f; 以下这个PBR Maste从何而来&#xff1f;