C++模版vector模拟实现

devtools/2025/3/10 21:15:41/

目录

vector类模板结构介绍

迭代器部分

函数介绍

完整代码

一、vector类模板结构介绍

该vector类模板包含以下成员函数：

  1. begin()和end()：返回迭代器，用于指向vector的起始和结束位置。
  2. cbegin()和cend()：返回常量迭代器，用于指向vector的起始和结束位置。
  3. capacity()：返回vector的容量，即分配的内存空间大小。
  4. size()：返回vector中元素的个数。
  5. resize()：调整vector的大小，如果n小于当前容量，则直接修改size()的值；如果n大于当前容量，则先通过reserve()函数进行内存的重新分配，再插入新的元素。
  6. swap()：交换两个vector对象的内容。
  7. reserve()：申请至少能容纳n个元素的内存空间，如果n大于当前容量，则重新分配内存；否则不进行操作。
  8. pop_back()：删除vector的最后一个元素。
  9. push_back()：在vector的末尾添加一个元素。
  10. insert()：在指定位置插入一个元素。
  11. erase()：删除指定位置的元素。

此外，还包括构造函数、拷贝构造函数、赋值运算符重载和析构函数。

私有成员

  1. _start 是指向存储区域的起始位置的迭代器，表示第一个元素的位置。
  2. _finish 是指向实际存储数据区域的最后一个元素之后的空闲位置的迭代器，表示当前已经存储的元素数量。
  3. _endOfStorage 是指向分配的内存空间的最后一个位置之后的位置的迭代器，表示当前 vector 可以存储的最大元素数量。如果 _finish 等于 _endOfStorage，那么 vector 已达到最大容量，此时需要扩容才能继续添加元素。
private:iterator _start;iterator _finish;iterator _endOfStorage;

二、迭代器部分

  • 在该代码中，通过使用typedef关键字将T和const T定义为iterator和const_iterator类型，分别表示可修改和只读的迭代器。

  • 然后，定义了以下成员函数来获取迭代器：

  1. begin()：返回一个指向vector起始位置的迭代器。
  2. end()：返回一个指向vector结束位置的迭代器，即最后一个元素的下一个位置。
  3. cbegin()：返回一个指向vector起始位置的常量迭代器，不允许修改元素。
  4. cend()：返回一个指向vector结束位置的常量迭代器，不允许修改元素。 通过使用迭代器，可以方便地遍历vector容器中的元素

代码如下：

typedef T* iterator;typedef const T* const_iterator;//迭代器部分iterator begin(){return _start;}iterator end(){return _finish;}const_iterator cbegin()const{return _start;}const_iterator cend()const{return _finish;}

三、函数部分

capacity函数
在实现中，使用指针之间的减法运算符来计算 _endOfStorage - _start 的值。其中 _endOfStorage 表示已分配内存空间的尾部位置， _start 表示 vector 的起始位置。

size_t capacity()const{return _endOfStorage - _start;}


size函数
在实现中，使用指针之间的减法运算符来计算偏移量，从而得到 _finish - _start 的值。其中 _finish 表示 vector 的结束位置， _start 表示 vector 的起始位置。

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


resize函数
在函数实现中，首先判断 n 是否小于当前的容量 capacity()。如果是，则直接将结束位置 _finish 设置为 _start + n，即截断 vector，不需进行内存重新分配。

如果 n 大于或等于当前的容量，意味着需要重新分配内存空间。此时调用 reserve(n) 函数来扩展 vector 的容量至至少 n，确保有足够的空间容纳新的元素。然后使用循环将元素 val 依次添加到 vector 中，使用 push_back() 函数将元素添加至末尾。这样就实现了重新分配内存并初始化新元素的功能。

void resize(size_t n, const T& val = T()){if (n < capacity()){_finish = _start+n ;}else{reserve(n);for (int i = 0; i < n; i++){push_back(val);}}}


reserve函数

  1. 在函数实现中，首先判断 n 是否大于当前的容量 capacity()。如果是，则需要重新分配内存空间。
  2. 首先创建一个临时指针 tmp，调用 new 运算符申请一个大小为 n 的新数组。然后通过循环将原始 vector 中的元素逐个复制到新的数组中。
  3. 接下来释放原始内存空间，使用 delete[] 运算符删除原始指针 _start 所指向的数组。然后将新的数组指针 tmp 赋值给 _start，以更新 vector 的起始位置。
  4. 同时，更新 vector 的结束位置 _endOfStorage 为 _start + n，表示分配的内存空间的末尾位置。将 vector 的实际使用大小 _finish 更新为之前的大小 sz。
//申请内存void reserve(size_t n)//返回类型是引用{if (n > capacity()){T* tmp = new T[n];int sz = size();if (_start != nullptr){for (int i = 0; i < size(); i++){tmp[i] = _start[i];}}delete[] _start;_start = tmp;_endOfStorage = _start + n;_finish = _start + sz;}}

pop_back函数
在函数实现中，首先利用 assert() 函数对 vector 的大小进行检查，确保 vector 不为空。如果 vector 为空，则会触发断言错误，程序终止运行。

然后将 vector 的 _finish 指针向前移动一位，指向新的最后一个元素。由于 _finish 是指向最后一个元素的下一个位置，因此该操作实际上是将最后一个元素“弹出”了 vector。

//尾删void pop_back(){assert(size() >= 0);_finish--;}


push_back函数

  1. 在函数实现中，首先判断 _finish 是否达到 vector 可用空间的末尾 _endOfStorage。如果是，则表示当前的内存空间已经完全使用，需要进行内存重新分配。
  2. 在重新分配内存空间时，调用 reserve() 函数，将 vector 的容量扩展为原来的两倍（或4，如果当前容量为0）。
  3. 然后，将新元素 x 赋值给 _finish 所指向的位置，即插入到 vector 的末尾。最后，将 _finish 指针向后移动一位，表示 vector 的大小增加了1。
void push_back(const T& x){if (_finish == _endOfStorage){reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finish = x;_finish++;}


构造函数

  1. vector(InputIterator first, InputIterator last) 构造函数使用迭代器范围 [first, last) 内的元素来初始化 vector。通过循环遍历迭代器范围内的每个元素，并调用 push_back() 函数将其添加到 vector 中。
  2. vector(const vector& v)构造函数使用另一个 vector 对象 v 来初始化新创建的 vector 对象。首先通过 reserve() 函数为新 vector 分配与 v 相同大小的内存空间。然后通过循环遍历 v 中的每个元素，并调用 push_back() 函数将其添加到新 vector 中。
  3. vector() 默认构造函数创建一个空的 vector 对象，没有分配任何内存空间。所有指针成员 _start、_finish 和 _endOfStorage 都被设置为 nullptr。
  4. vector(int n, const T& val = T()) 构造函数创建一个包含 n 个元素的 vector 对象，并使用参数 val 的值进行初始化。通过循环调用 push_back() 函数 n 次，将 val 添加到 vector 中。
//构造函数template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*(InputIterator));first++;}}vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endOfStorage(nullptr){reserve(v.size());for (auto i = v.cbegin();i!=v.cend();i++){push_back(*i);}}
vector(): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){}vector(int n, const T& val = T()){for (int i = 0; i < n; i++){push_back(val);}}

swap函数
函数使用 std::swap() 函数来交换 _start、_finish 和 _endOfStorage 指针成员的值。通过调用 std::swap() 函数，将当前 vector 对象的指针成员与参数 v 的对应指针成员进行交换，实现两个 vector 对象之间的内容交换。

 

 //交换函数void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}                        

        
=运算符重载
函数创建了一个临时的 vector 对象 tmp，并将参数 v 复制到该对象中。然后通过调用成员函数 swap() 将当前对象和临时对象的内容进行交换，从而实现将当前 vector 对象赋值为参数 v 的操作。

 

 vector<T>& operator= (vector<T> v){vector<int> tmp(v);swap(tmp);}


析构函数
析构函数首先使用 delete[] 关键字释放 _start 指针指向的动态分配的数组内存空间。然后将 _start、_finish 和 _endOfStorage 的值设置为 nullptr，以避免悬挂指针的问题。

  //析构函数~vector(){delete[] _start;_start = nullptr;_finish = nullptr;_endOfStorage = nullptr;}


[]运算符重载

  1. T& operator[](size_t pos) 是非常规则的重载函数，用于通过下标 pos 访问 vector 中的元素，并返回对应位置的引用。在函数体内部，它直接返回 _start[pos] 的引用，从而允许调用者对该元素进行读写操作。
  2. const T& operator[](size_t pos)const 是常规则的重载函数，用于在常量对象上进行下标访问。它与第一个版本的区别在于，在函数声明中加入了 const 限定符，表明该函数不会修改 vector 对象的内容。在函数体内部，它同样返回 _start[pos] 的引用，但由于函数是 const 成员函数，所以返回的引用是常量引用，只能用于读取元素的值，不能进行写操作。

 

 //[]运算符重载T& operator[](size_t pos){return _start[pos];}const T& operator[](size_t pos)const{return _start[pos];}


insert函数

  1. 首先，函数使用 assert() 断言来确保插入位置 pos 在有效范围内，即在 _start 和 _finish 之间（包括 _start 和 _finish）。
  2. 然后，函数检查当前 vector 是否已经满了，即 _finish 是否等于 _endOfStorage。如果是满的，则需要进行扩容操作。函数通过调用 reserve() 来扩容，扩容大小为当前容量的两倍。值得注意的是，由于扩容操作可能导致原来的迭代器失效，所以在扩容之前需要记录插入位置 pos 相对于 _start 的偏移量 sz，然后在扩容后重新计算插入位置 pos。
  3. 接下来，函数利用迭代器将从 pos 到 _finish-1 的所有元素向后移动一个位置。具体而言，迭代器 en 初始化为 _finish-1，然后循环将 en 指向的元素复制到 en+1 指向的位置，直到 en 等于 pos。
  4. 最后，将元素 x 赋值给 pos 指向的位置，增加 _finish 的值，并返回指向插入位置的迭代器 pos。

  

//随机插入iterator insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _endOfStorage){int sz = pos - _start;//记录pos与_start的相对位置reserve(capacity() == 0 ? 4 : 2 * capacity());//注意迭代器失效pos = _start + sz;//重置迭代器}iterator en = _finish-1;while (en >= pos){*(en+1) = *(en);en--;}*pos = x;_finish++;return pos;}

erase函数

  1. 首先，函数使用 assert() 断言来确保删除位置 pos 在有效范围内，即在 _start 和 _finish 之间（包括 _start 和 _finish）。
  2. 然后，函数利用迭代器将从 pos+1 到 _finish-1 的所有元素向前移动一个位置。具体而言，迭代器 a 初始化为 pos+1，然后循环将 a 指向的元素复制到 a-1 指向的位置，直到 a 等于 _finish。
  3. 最后，将 _finish 减一，并返回指向删除位置的迭代器 pos。需要注意的是，虽然 pos 已经失效了，但是这里返回的仍然是指向原来的位置的迭代器，因为要保证与 STL 标准库的接口兼容。
  iterator erase(iterator pos){assert(pos >= _start);assert(pos <= _finish);iterator a = pos+1;while (a != _finish){*(a-1) = *a;a++;}_finish--;return pos;}

四、完整代码 

#pragma once
#include<assert.h>
namespace hqj
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//迭代器部分iterator begin(){return _start;}iterator end(){return _finish;}const_iterator cbegin()const{return _start;}const_iterator cend()const{return _finish;}size_t capacity()const{return _endOfStorage - _start;}size_t size()const{return _finish - _start;}void resize(size_t n, const T& val = T()){if (n < capacity()){_finish = _start+n ;}else{reserve(n);for (int i = 0; i < n; i++){push_back(val);}}}//交换函数void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}//申请内存void reserve(size_t n)//返回类型是引用{if (n > capacity()){T* tmp = new T[n];int sz = size();if (_start != nullptr){for (int i = 0; i < size(); i++){tmp[i] = _start[i];}}delete[] _start;_start = tmp;_endOfStorage = _start + n;_finish = _start + sz;}}//尾删void pop_back(){assert(size() >= 0);_finish--;}//尾插void push_back(const T& x){if (_finish == _endOfStorage){reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finish = x;_finish++;}//构造函数template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*(InputIterator));first++;}}vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endOfStorage(nullptr){reserve(v.size());for (auto i = v.cbegin();i!=v.cend();i++){push_back(*i);}}vector<T>& operator= (vector<T> v){vector<int> tmp(v);swap(tmp);}vector(): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr){}vector(int n, const T& val = T()){for (int i = 0; i < n; i++){push_back(val);}}//析构函数~vector(){delete[] _start;_start = nullptr;_finish = nullptr;_endOfStorage = nullptr;}//[]运算符重载T& operator[](size_t pos){return _start[pos];}const T& operator[](size_t pos)const{return _start[pos];}//随机插入，随机删除iterator insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _endOfStorage){int sz = pos - _start;//记录pos与_start的相对位置reserve(capacity() == 0 ? 4 : 2 * capacity());//注意迭代器失效pos = _start + sz;//重置迭代器}iterator en = _finish-1;while (en >= pos){*(en+1) = *(en);en--;}*pos = x;_finish++;return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos <= _finish);iterator a = pos+1;while (a != _finish){*(a-1) = *a;a++;}_finish--;return pos;}private:iterator _start;iterator _finish;iterator _endOfStorage;};

http://www.ppmy.cn/devtools/166106.html

相关文章

Linux安装升级docker

Linux安装升级docker

Linux 安装升级docker Linux 安装升级docker背景升级停止docker服务备份原docker数据目录移除旧版本docker安装docker ce恢复数据目录启动docker参考 安装找到docker官网找到docker文档删除旧版本docker配置docker yum源参考官网继续安装docker设置开机自启配置加速测试 Linux …
阅读更多...
nginx反向代理功能

nginx反向代理功能

如上图所示&#xff0c;当配置好nginx反向代理服务器的时候&#xff0c;客户端向nginx反向代理服务器发送请求&#xff0c;nginx反向代理服务器再向真实服务器转发请求。 nginx作为反向代理就是利用nginx高并发&#xff0c;速度快的特性&#xff0c;让nginx能够承受更多的链接…
阅读更多...
LLM+多智能体协作：基于CrewAI与DeepSeek的邮件自动化实践

LLM+多智能体协作：基于CrewAI与DeepSeek的邮件自动化实践

文章目录 引言理解 Flows&#xff08;工作流&#xff09;与 Crews&#xff08;协作组&#xff09;一、环境准备与工具安装1.1 Python环境搭建1.2 创建并激活虚拟环境1.3 安装核心依赖库&#xff08;crewai、litellm&#xff09; 二、本地DeepSeek R1大模型部署2.1 Ollama框架安…
阅读更多...
使用express创建服务器保存数据到mysql

使用express创建服务器保存数据到mysql

创建数据库和表结构 CREATE DATABASE collect;USE collect;CREATE TABLE info (id int(11) NOT NULL AUTO_INCREMENT,create_date bigint(20) DEFAULT NULL COMMENT 时间,type varchar(20) DEFAULT NULL COMMENT 数据分类,text_value text COMMENT 内容,PRIMARY KEY (id) ) EN…
阅读更多...
查看电脑信息

查看电脑信息

搜索关键字&#xff1a;怎么查看windows版本的xxxx 怎么查看戴尔/联想电脑的xxx 总结&#xff1a; Win R cmd 硬盘序列号 wmic diskdrive get serialnumber 系统安装日期 systeminfo 设备序列号 wmic bios get serialnumber MAC及IP ipconfig Win R msinfo32 品牌型号/系统…
阅读更多...
电脑的常见问题的原因+解决方法

电脑的常见问题的原因+解决方法

电脑常见问题涵盖软件和硬件两方面&#xff0c;以下是一些常见问题及解决方法&#xff1a; 软件问题 系统运行缓慢 原因&#xff1a;可能是开机启动项过多、系统垃圾文件堆积、病毒或恶意软件入侵、硬件驱动不兼容等。解决方法&#xff1a;利用系统自带的任务管理器或第三方软…
阅读更多...
Spring Boot 内置工具类，功能齐全！！

Spring Boot 内置工具类，功能齐全！！

01断言 断言是一个逻辑判断&#xff0c;用于检查不应该发生的情况 Assert 关键字在 JDK1.4 中引入&#xff0c;可通过 JVM 参数-enableassertions开启 SpringBoot 中提供了 Assert 断言工具类&#xff0c;通常用于数据合法性检查 // 要求参数 object 必须为非空&#xff08…
阅读更多...
【Unity】 HTFramework框架（六十一）Project窗口文件夹锁定器

【Unity】 HTFramework框架（六十一）Project窗口文件夹锁定器

更新日期&#xff1a;2025年3月7日。 Github源码&#xff1a;[点我获取源码] Gitee源码&#xff1a;[点我获取源码] 索引 Project窗口文件夹锁定器框架文件夹锁定自定义文件夹锁定限制条件 Project窗口文件夹锁定器 在Project窗口中&#xff0c;文件夹锁定器能够为任何文件夹加…
阅读更多...
最新文章

Copyright @ 2022~2023