【C++】vector容器初步模拟

在这里插入图片描述
送给大家一句话:
努力一点,漂亮—点,阳光一点。早晚有一天,你会惊艳了时光,既无人能替,又光芒万丈。

vector容器初步模拟

  • 1 认识vector
    • 开始了解
    • 底层实现
  • 2 开始实现
    • 成员变量
    • 构造函数 析构函数
    • 尾插
    • 迭代器
    • 插入 删除 寻找操作
    • 操作符重载
    • swap函数
  • 总结
  • Thanks♪(・ω・)ノ谢谢阅读!!!
  • 下一篇文章见!!!

今天我我来进行vector的模拟实现,先简单的实现一下初步功能,使其对内置类型可以适配。(大部分与string很类似)

1 认识vector

开始了解

  1. vector是表示可变大小数组的序列容器。
  2. 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。
  3. 本质讲,vector使用动态分配数组来存储它的元素。当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间。其做法是,分配一个新的数组,然后将全部元素移到这个数组。就时间而言,这是一个相对代价高的任务,因为每当一个新的元素加入到容器的时候,vector并不会每次都重新分配大小。
  4. vector分配空间策略:vector会分配一些额外的空间以适应可能的增长,因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何,重新分配都应该是对数增长的间隔大小,以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
  5. 因此,vector占用了更多的存储空间,为了获得管理存储空间的能力,并且以一种有效的方式动态增长
  6. 与其它动态序列容器相比(deque, list and forward_list), vector在访问元素的时候更加高效,在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作,效率更低。比起list和forward_list统一的迭代器和引用更好。

使用STL的三个境界:能用,明理,能扩展 ,那么下面学习vector,我们也是按照这个方法去学习

底层实现

我们来了解一下vector的底层实现是如何做到,首先就要了解其类成员是如何定义的,这样我们才能更好的复刻vector(以下是1996年的STL版本,还比较简单):

protected:typedef simple_alloc<value_type, Alloc> data_allocator;iterator start; iterator finish;iterator end_of_storage //容量结束;

可以看到受保护的内部成员变量是由三个迭代器构成的。
迭代器的底层是:

typedef T value_type;
typedef value_type* iterator;

也就是说底层是指针,T是模版类的参数。接下来我们在观察一下构造函数是如何操作的(参考一部分):

 vector() : start(0), finish(0), end_of_storage(0) {}vector(size_type n, const T& value) { fill_initialize(n, value); }vector(int n, const T& value) { fill_initialize(n, value); }vector(long n, const T& value) { fill_initialize(n, value); }

这个fill_initialize又是什么呢???是初始化函数,(在工程文件中,经常使用一层又一层的嵌套,由于我还没有丰富的工程经验,我看起来还是很费劲,晕乎乎的)。我们看一部分即可,现在我们开始手搓vector,针对内置类型进行操作。

2 开始实现

我们开始逐步进行实现。

成员变量

根据我们刚才所查看的源码,我们要使用三个迭代器,要使用迭代器,我们可以使用指针进行模拟。

//使用模版 兼容各种类型
template<typename T>
class vector {
public://重命名 指针即可模拟迭代器 常量与非常量都要提供哦typedef T* iterator;typedef const T* const_iterator;private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end = nullptr;};

写出三个迭代器(指针)后,我们对构造函数应该也有了大致思路:需要初始化三个迭代器,所以我们给与初始值nullptr。让后进行开辟空间。

构造函数 析构函数

这里的构造函数我设置三个接口,一个是空构造,一个是开辟 N 个空间并初始化为val,一个是拷贝构造:

//空构造
vector() 
{}
//开辟 N 个空间并初始化为val
vector(size_t n,T val = T()) {iterator tmp = new T[n];_start = tmp;for (iterator it = begin(); it < _start + n ;it++) {*it= val;}_finish = _start + n;_end = tmp + n ;}
/拷贝构造
vector(vector<T>& v) {//依次尾插即可完成操作for (auto s : v) {push_back(s);}
}

析构函数就是简单的释放空间即可:

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

我们完成了构造函数和析构函数,为了能够进行测试,我们现在来实现尾插操作:

尾插

尾插操作之前,根据我们实现string的经验来说,我们需要做一些准备工作,实现一些常用接口(size(),capacity(),reserve(),resize()):
注意:如果对象中涉及到资源管理时,千万不能使用memcpy进行对象之间的拷贝,因为memcpy是浅拷贝,否则可能会引起内存泄漏甚至程序崩溃。

		//注意const 保证不会进行权限的放大size_t size() const{return _finish - _start;}size_t capacity() const{return _end - _start;}bool empty(){return size() == 0;}//扩容void reserve(size_t newcapacity) {//记录位置size_t n = _finish - _start;T* tmp = new T[newcapacity];//拷贝memcpy(tmp, _start, size() * sizeof(T));_start = tmp;_finish = _start + n;_end = _start + newcapacity;}//改变大小void resize(size_t n, T val = T()) {//x需要扩容if ( n > size()){reserve(n);;while (_finish != _end) {*_finish = val;_finish++;}}//不需扩容else {_finish = _start + n;}}

实现了这些接口,就可以顺畅的进行尾插的书写,通过size()和capacity()可以判断是否需要扩容,reserve可以进行扩容。然后再_finish位置插入新的数据,再移动_finish即可。

		//尾插void push_back(T val) {if (size() == capacity()) {//扩容reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finish = val;_finish++;}

接下来我们在完善一下迭代器。

迭代器

迭代器的实现很简单,对指针进行重命名即可(真正的迭代器没有这么简单)

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; }

完成了begin() 和end()函数,就可以使用基于范围的for循环了。
我们进行一个简单的测试,来看看我们写的构造,尾插是否正常。

template<class T>
void print_vector(const vector<T> v) {for (size_t i = 0; i < v.size(); i++) {cout << v[i] << " ";}cout << endl;
}
//构造,尾插测试
void vector_test1() {cout << "---------构造 ,尾插测试---------\n";vector<int> v1;vector<int> v2(4);v2.push_back(1);v2.push_back(2);v2.push_back(3);v2.push_back(4);print_vector(v2);v1.push_back(5);v1.push_back(6);print_vector(v1);cout << v1.size() << endl;cout << v1.capacity() << endl;vector<int> v3(v1);print_vector(v3);
}

看一下效果:

在这里插入图片描述
没有问题!!!

插入 删除 寻找操作

这个也很简单,对数据进行挪动就可以完成:

//任意位置插入
void insert(size_t pos = 0,T val = T()) {
//保证在数据范围之内assert(pos >= 0);assert(pos <= size());//检查if (size() == capacity()) {//扩容reserve(capacity() == 0 ? 4 : 2 * capacity());}iterator it = end();//依次后移 然后插入while (it >= begin() + pos) {*(it + 1) = *it;it--;}it++;*it = val;_finish++;
}
void erease(size_t pos) 
{
//保证在数据范围之内assert(pos >= 0);assert(pos <= size());iterator it = begin() + pos;//依次前移while (it < end()) {*it = *(it + 1);it++;}_finish--;}
//尾删
void pop_back() {erease(size());}
size_t find(T val = T()) 
{//依次寻找for (iterator it = _start; it < _finish;it++) {if (*it == val) return it - _start;}return -1;
}

操作符重载

vector容器最重要的操作符应该就是[ ]操作了吧,此外重载一个 = :

//提供常量与非常量
T& operator[](size_t n) { assert(n >= 0); assert(n < size()); return *(_start + n); }
const T& operator[](size_t n) const { assert(n >= 0); assert(n < size()); return *(_start + n); }
//类似拷贝
vector<T>& operator=(vector<T>& v){T* tmp = new T[v.capacity()];memcpy(tmp, v._start, v.size() * sizeof(T));size_t pos = v.size();size_t n = v.capacity();_start = tmp;_finish = _start + pos;_end = _start + capacity();return *this;
}

这样就完成了:
我们进行一个测试来看看是否可行:

void vector_test2() {cout << "---------resize find insert erase测试---------\n";vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);print_vector(v1);cout << v1.find(2) << endl;v1.resize(10, 0);print_vector(v1);v1.insert(0, 0);print_vector(v1);v1.erease(5);print_vector(v1);}

来看效果:
在这里插入图片描述
成功!!!

swap函数

接下来在提供一个swap 函数以供交换,注意一定是深拷贝!!!

		void swap(vector& v) {T* tmp = new T[v.capacity()];memcpy(tmp, v._start, v.size() * sizeof(T));size_t pos = v.size();size_t n = v.capacity();v._start = _start;v._finish = _finish;v._end = _end;_start = tmp;_finish = _start + pos;_end = _start + capacity();}

来进行一个简单测试:

//交换测试
void vector_test3() {cout << "---------swap 测试---------\n";vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(6);print_vector(v1);vector<int> v2(4);v2.push_back(1);v2.push_back(3);v2.push_back(1);v2.push_back(4);print_vector(v2);v2.swap(v1);print_vector(v1);print_vector(v2);}

来看效果:
在这里插入图片描述
成功交换!!!

总结

我们初步完成了对vector 的模拟实现,但是依然有问题,比如不支持string等特殊类型。所以下一篇文章我们来一起完善一下。

Thanks♪(・ω・)ノ谢谢阅读!!!

下一篇文章见!!!

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

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

相关文章

集成学习 | 集成学习思想:Boosting思想 | XGBoost算法、LightGBM算法

目录 一. XGBoost 算法1. XGBoost 算法流程2. XGBoost 算法评价 二. LightGBM 算法2. LightGBM 算法优势 上一篇文章中&#xff0c;我们了解了Boosting思想的两种算法&#xff1a;Adboost和GBDT&#xff1b;其中对于GBDT算法&#xff0c;存在两种改进&#xff0c;即&#xff1a…

外包干了20天,技术退步明显.......

先说一下自己的情况&#xff0c;大专生&#xff0c;21年通过校招进入杭州某软件公司&#xff0c;干了接近2年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落! 而我已经在一个企业干了2年的功能测试…

1分钟带你学会使用Python操作 xlsx 文件绘制面积图

​我们工作中经常要处理海量的数据&#xff0c;如果没有一个直观的可视化工具&#xff0c;怎么可能一眼就看出数据背后的故事呢&#xff1f;数据可视化显得越来越重要&#xff0c;数据分析已经成了现代人必备的技能。 今天来和大家分享一个超有趣的数据可视化方法——绘制面积…

Redis中文乱码问题

最近排查问题&#xff0c;发现之前的开发将日志写在redis缓存中&#xff08;不建议这样做&#xff09;&#xff0c;我在查看日志的时候发现没办法阅读&#xff0c;详细是这样的&#xff1a; 查阅资料后发现是进制问题&#xff0c;解决方法是启动客户端的时候将redis-cli改为red…

流畅的 Python 第二版(GPT 重译)(四)

第二部分&#xff1a;函数作为对象 第七章&#xff1a;函数作为一等对象 我从未认为 Python 受到函数式语言的重大影响&#xff0c;无论人们说什么或想什么。我更熟悉命令式语言&#xff0c;如 C 和 Algol 68&#xff0c;尽管我将函数作为一等对象&#xff0c;但我并不认为 Py…

【机器学习】机器学习是什么?

文章目录 前言 机器学习 序列学习和对抗学习有什么不同 总结 前言 在当今快速发展的科技时代&#xff0c;人工智能已经成为推动社会进步的重要力量。机器学习&#xff0c;作为人工智能领域的一个重要分支&#xff0c;它的核心能力在于使计算机系统能够从数据中学习规律&…

Python RPA简单开发实践(selenium登陆浏览器自动输入密码登陆)

打开csdn博客&#xff0c;简单版 class BS:def __init__(self, url):self.url url# self.password password# self.username usernamedef login_url(self):from selenium import webdriver# 不自动关闭浏览器option webdriver.ChromeOptions()option.add_experimental_opt…

Vue 若依框架 form-generator添加表格组件和动态表单组件

效果图&#xff1a; 在若依框架自带的流程表单配置基础上添加这两个组件 config.js // 表单属性【右面板】 export const formConf {formRef: elForm,formModel: formData,other: other,size: medium,labelPosition: right,labelWidth: 100,formRules: rules,gutter: 15,dis…

LeetCode每日一题[c++]-322.零钱兑换

题目描述 给你一个整数数组 coins &#xff0c;表示不同面额的硬币&#xff1b;以及一个整数 amount &#xff0c;表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额&#xff0c;返回 -1 。 你可以认为每种硬币的数量是无…

游戏提示steam_api64.dll丢失怎样修复?教你5种快速修复的方法

在计算机系统中&#xff0c;如果未能成功找到或加载steam_api64.dll文件&#xff0c;可能会引发一系列的问题和故障现象。这个特定的DLL文件是Steam平台的核心组件之一&#xff0c;对于运行基于Steam平台的游戏或应用至关重要。当系统提示“找不到steam_api64.dll”时&#xff…

抖音视频关键词爬虫批量采集软件|视频提取下载工具

视频关键词批量采集软件 — 助力您快速获取所需视频 主要功能&#xff1a; 关键词批量提取视频和单独视频提取&#xff0c;提取后下载功能。 功能解析&#xff1a; 1. 关键词批量提取视频的解析 通过输入关键词进行视频搜索和提取。例如&#xff0c;输入“汽车配件”&#x…

N9010B EXA 信号分析仪 10 Hz 至 44 GHz

N9010B EXA 信号分析仪 10 Hz 至 44 GHz 产品综述 <<<<频率范围&#xff1a;10 Hz 至 44 GHz>>> keysight N9010B EXA 信号分析仪&#xff0c;10 Hz 至 44 GHz无论是增强产品性能还是提高测试吞吐量&#xff0c;您的通用型信号分析仪都要有能力满足各…

为什么电商系统一定要跟企业ERP做数据对接?

一篇文章告诉你&#xff0c;为什么电商系统一定要跟企业ERP做数据对接&#xff1f; 在电商日益发展的情况下&#xff0c;每个电商企业的单量越来越大。但是电商系统对于财务来说并不友好&#xff0c;所以企业会另外上一套财务系统方便财务做账和企业内部管理。那如果还是按照之…

后端常问面经之操作系统

请简要描述线程与进程的关系,区别及优缺点&#xff1f; 本质区别&#xff1a;进程是操作系统资源分配的基本单位&#xff0c;而线程是任务调度和执行的基本单位 在开销方面&#xff1a;每个进程都有独立的代码和数据空间&#xff08;程序上下文&#xff09;&#xff0c;程序之…

产品经理面试自我介绍,这3大错误千万别犯!

金三银四求职季&#xff0c;你是不是也有面试的冲动&#xff01;但面试并不是头脑一热就能取得好结果&#xff0c;在此之前&#xff0c;必须得有周全的准备&#xff0c;才能应对好面试官的“连环问”&#xff01; 所以&#xff0c;今天这篇产品经理面试干货分享给大家~ 今天文…

MySQL-1.数据库的基本操作

1. 数据库的基本操作 show databases; information_schema&#xff1a;信息图式&#xff0c;存储服务器管理数据库的信息 mysql&#xff1a;存放系统信息&#xff0c;用户名密码等 performance_schema&#xff1a;性能图式 sys&#xff1a;系统文件 1.1 创建数据库-studen…

流畅的 Python 第二版(GPT 重译)(六)

第三部分&#xff1a;类和协议 第十一章&#xff1a;一个 Python 风格的对象 使库或框架成为 Pythonic 是为了让 Python 程序员尽可能轻松和自然地学会如何执行任务。 Python 和 JavaScript 框架的创造者 Martijn Faassen。 由于 Python 数据模型&#xff0c;您定义的类型可以…

【设计模式】实战篇

目录标题 【实战一】模板方法模式抽象类子类 【实战一】模板方法模式 抽象类 定义一个抽象类&#xff1a;FarmWorkNodeRecord&#xff1a;表示其记录是用来操作计划的节点对象的。 public abstract class FarmWorkNodeRecordService {// 模拟Mapperprivate String plantPlan…

Arduino中的map函数

一、案例 val analogRead(dyPin); //读取模拟口的模拟量数值 dyValuemap(val,0,1023,0,500);//这个函数是将电位器调节的模拟量的值按比例转换成对应的电压量 问题&#xff0c;为什么不是0~499呢&#xff1f; 其实也行↓ 当map(val, 0, 1023, 0, 500)被调用时&#xff0…

关于异业联盟模式做成小程序的可行性分析

随着移动互联网的快速发展&#xff0c;小程序作为一种轻量级应用&#xff0c;受到了越来越多企业和用户的青睐。而异业联盟模式则是一种有效的商业合作方式&#xff0c;能够实现资源共享、优势互补和共同发展。将异业联盟模式做成小程序&#xff0c;不仅可以提高用户体验&#…