C++ Vector的模拟实现

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的一些接口：

namespace MyVector
{template<class T>class vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;iterator begin();iterator end();const_iterator cbegin() const;const_iterator cend() const;   // 初始化vector();// 析构~vector();vector(int n, const T& value = T());vector(size_t n, const T& val = T());//类模板的成员函数可以是函数模板template<class InputIterator>vector(InputIterator first, InputIterator last);vector(const vector<T>& v);vector<T>& operator= (vector<T> v);size_t size() const;size_t capacity() const;void reserve(size_t n);void resize(size_t n, const T& value = T());T& operator[](size_t pos);const T& operator[](size_t pos)const;bool empty();void push_back(const T& x);void pop_back();void swap(vector<T>& v);iterator insert(iterator pos, const T& x);iterator erase(iterator pos);private:iterator _start = nullptr; // 指向数据块的开始iterator _finish = nullptr; // 指向有效数据的尾iterator _endOfStorage = nullptr;// 指向存储容量的尾};
}

iterator begin()

        iterator begin(){return _start;}

iterator end()

        iterator end(){return _finish;}

const_iterator cbegin()

        const_iterator cbegin(){return _start;}

const_iterator cend() const

        const_iterator cend() const{return _finish;}

四个比较简单的迭代器

vector()

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

~vector()

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

初始化与析构

        //类模板的成员函数可以是函数模板template<class InputIterator> // InputIterator定义的一个迭代器类型vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endOfStorage(nullptr){while (first != last){push_back(*first);++first;}}

vector<T>& operator= (vector<T> v)

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

        // v1 = v3

size_t size() const

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

        // 有效数据的尾减去数据块的开始就是元素个数

size_t capacity() const

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

        // 开辟空间的容量

void reserve(size_t n)

        void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];size_t old_size = size();for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i]; // 深拷贝}delete[] _start;_start = tmp; // 老的_start已经失效，更新一下_finish = tmp + old_size;_endOfStorage = tmp + n;}}

void resize(size_t n, const T& value = T())

        void resize(size_t n, const T& value = T()){if (n > size()) // 超过就扩容{reserve(n);while (_finish < _start + n){*_finish = value;++_finish;}}else{_finish = _start + n;}}

vector(const vector<T>& v)

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

        // v2(v1) 用已经存在的 v1 去初始化 v2

T& operator[](size_t pos)

const T& operator[](size_t pos)const

        T& operator[](size_t pos){assert(pos < size()); // 保证下标为有效数据return _start[pos];}const T& operator[](size_t pos)const{assert(pos < size());return _start[pos];}

iterator insert(iterator pos, const T& x)

        iterator insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _endOfStorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());//如果扩容了要更新pospos = _start + len;}iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;--it;}*pos = x;++_finish;}

iterator erase(iterator pos)

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

vector(int n, const T& value = T())

        vector(int n, const T& value = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(value);}}

vector(size_t n, const T& val = T())

        vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}

bool empty()

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

void push_back(const T& x)

        void push_back(const T& x){insert(end(), x);}

void pop_back()

        void pop_back(){erase(end() - 1);}

void swap(vector<T>& v)

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

完整代码：

#pragma once#include <assert.h>namespace bit
{template<class T>class vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator cbegin(){return _start;}const_iterator cend() const{return _finish;}// construct and destroyvector():_start(nullptr),_finish(nullptr), _endOfStorage(nullptr){}vector(int n, const T& value = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(value);}}vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}//类模板的成员函数可以是函数模板template<class InputIterator>vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endOfStorage(nullptr){while (first != last){push_back(*first);++first;}}vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}vector<T>& operator= (vector<T> v){swap(v);return *this;}~vector(){delete[] _start;_start = _finish = _endOfStorage;}size_t size() const{return _finish - _start;}size_t capacity() const{return _endOfStorage - _start;}void reserve(size_t n){if (n > capacity()){T* tmp = new T[n];size_t old_size = size();for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;_start = tmp;_finish = tmp + old_size;_endOfStorage = tmp + n;}}void resize(size_t n, const T& value = T()){if (n > size()){reserve(n);while (_finish < _start + n){*_finish = value;++_finish;}}else{_finish = _start + n;}}T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos)const{assert(pos < size());return _start[pos];}bool empty(){return _start == _finish;}void push_back(const T& x){insert(end(), x);}void pop_back(){erase(end() - 1);}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}iterator insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _endOfStorage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());//如果扩容了要更新pospos = _start + len;}iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;--it;}*pos = x;++_finish;}iterator erase(iterator pos){assert(pos >= _start);assert(pos <= _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;--it;}--_finish;return pos;}private:iterator _start = nullptr; // 指向数据块的开始iterator _finish = nullptr; // 指向有效数据的尾iterator _endOfStorage = nullptr;// 指向存储容量的尾};}

测试代码：

#include <iostream>
#include<algorithm>
#include<vector>#include "Vector.h"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);cout << v.size() << endl;cout << v.capacity() << endl;for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;for (auto e : v){cout << e << " ";}cout << endl;v.reserve(30);cout << v.capacity() << endl;vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;vector<int> v1(v);v1.push_back(100);v1.push_back(200);v1.pop_back();for (auto e : v1){cout << e << " ";}
}

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

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

相关文章

使用c++栈刷题时踩坑的小白错误

使用c++栈刷题时踩坑的小白错误

根据图片中提供的代码&#xff0c;可以发现以下三处错误&#xff1a; 错误原因&#xff1a;条件判断语句的逻辑错误。 代码行&#xff1a;if (res.top() ! e || res.empty())&#xff08;第7行&#xff09; 问题&#xff1a;如果 res 为空&#xff08;res.empty() 为 true&…
阅读更多...
java的字节符输出流基类、File Writer类和Buffered Writer类

java的字节符输出流基类、File Writer类和Buffered Writer类

一、字节符输出流基类&#xff1a;Writer 1.属于抽象类 2.常用方法 二、字节符输出流Flie Writer类 1.是writer类的子类 2.以字符为数据处理单元向文本文件中写数据 3.示例 4.实现步骤 三、BufferedWriter类 1.是Writer类的子类。 2.带有缓冲区 默认情况下&#xff0c…
阅读更多...
线性代数基础概念：矩阵

线性代数基础概念：矩阵

目录 线性代数基础概念&#xff1a;矩阵 1. 矩阵的定义 2. 矩阵的运算 3. 矩阵的特殊类型 4. 矩阵的秩 5. 矩阵的初等变换 6. 矩阵的特征值与特征向量 7. 矩阵的应用 8. 矩阵总结 总结 线性代数基础概念&#xff1a;矩阵 矩阵是线性代数中的另一个重要概念&#xff0…
阅读更多...
jQuery+post 调用php接口实现md5编码器

jQuery+post 调用php接口实现md5编码器

https://andi.cn/page/621474.html
阅读更多...
【原创】springboot+mysql海鲜商城设计与实现

【原创】springboot+mysql海鲜商城设计与实现

个人主页&#xff1a;程序猿小小杨 个人简介&#xff1a;从事开发多年&#xff0c;Java、Php、Python、前端开发均有涉猎 博客内容&#xff1a;Java项目实战、项目演示、技术分享 文末有作者名片&#xff0c;希望和大家一起共同进步&#xff0c;你只管努力&#xff0c;剩下的交…
阅读更多...
Google Adsense----Wordpress插入谷歌广告

Google Adsense----Wordpress插入谷歌广告

1.搭建个人博客,绑定谷歌search consol,注册adsense 详细可以参考这个视频b站视频 2.将个人博客网站关联到Adsense 在adsense里新加网站,输入你的博客网址,双击网站 将这段代码复制到header.php的里面 在wordpress仪表盘的外观-主题文件编辑器,找到header.php将代码复制,…
阅读更多...
Scania斯堪尼亚SHL题库综合能力性格测试真题题型解析及面试经验

Scania斯堪尼亚SHL题库综合能力性格测试真题题型解析及面试经验

一、走进Scania斯堪尼亚 Scania是一家成立于1891年的瑞典公司&#xff0c;专注于重型卡车和巴士的制造&#xff0c;以其模块化系统和环保设计闻名。作为全球领先的运输解决方案提供商&#xff0c;Scania不仅提供高质量的车辆&#xff0c;还提供相关服务和融资解决方案。公司秉…
阅读更多...
【Unity服务器01】之【AssetBundle上传加载u3d模型】

【Unity服务器01】之【AssetBundle上传加载u3d模型】

首先打开一个项目导入一个简单的场景 导入怪物资源&#xff0c; AssetBundle知识点&#xff1a; 1.指定资源的AssetBundle属性标签 &#xff08;1&#xff09;找到AssetBundle属性标签 &#xff08;2&#xff09;A标签 代表&#xff1a;资源目录&#xff08;决定打包之后在哪…
阅读更多...
Java基础（二）——数组，方法，方法重载

Java基础（二）——数组，方法，方法重载

个人简介 &#x1f440;个人主页&#xff1a; 前端杂货铺 ⚡开源项目&#xff1a; rich-vue3 &#xff08;基于 Vue3 TS Pinia Element Plus Spring全家桶 MySQL&#xff09; &#x1f64b;‍♂️学习方向&#xff1a; 主攻前端方向&#xff0c;正逐渐往全干发展 &#x1…
阅读更多...
spring-依赖注入DI

spring-依赖注入DI

Setter注入&#xff1a; 1、引用类型&#xff1a;在bean中定义引用类型属性并提供可访问的set方法&#xff0c;配置中使用property标签ref属性注入引用类型对象&#xff1b; 2、简单类型&#xff1a;在bean中定义引用类型属性并提供可访问的set方法&#xff0c;在配置中使用pr…
阅读更多...
MySQL全解(基础)-(MySQL的安装与配置,数据库基础操作(CRUD,聚合,约束,联合查询),索引,事务)

MySQL全解(基础)-(MySQL的安装与配置,数据库基础操作(CRUD,聚合,约束,联合查询),索引,事务)

MySQL安装与配置 1.数据库介绍 存储数据用文件就可以了&#xff0c;为什么还要弄个数据库? 文件保存数据有以下几个缺点&#xff1a; 文件的安全性问题 文件不利于数据查询和管理 文件不利于存储海量数据 文件在程序中控制不方便数据库存储介质&#xff1a; 磁盘 内存 为了…
阅读更多...
Redis报错：MISCONF Redis is configured to save RDB snapshots

Redis报错：MISCONF Redis is configured to save RDB snapshots

错误提示内容&#xff1a; 2024-06-25 16:30:49 : Connection: Redis_Server > [runCommand] PING 2024-06-25 16:30:49 : Connection: Redis_Server > Response received : -MISCONF Redis is configured to save RDB snapshots, but it is currently not able to pers…
阅读更多...
RK3568平台开发系列讲解（调试篇）分析内核调用的利器 ftrace

RK3568平台开发系列讲解（调试篇）分析内核调用的利器 ftrace

🚀返回专栏总目录 文章目录 一. 指定 ftrace 跟踪器二、设置要 trace 的函数三、ftrace 的开关四、查看 trace五、trace-cmd 的使用六、trace-cmd 的常用选项6.1、查看可以跟踪的事件6.2、跟踪特定进程的函数调用6.3、函数过滤6.4、限制跟踪深度6.5、追踪特定事件沉淀、分享、…
阅读更多...
【手眼标定】使用kalibr对imu和双目摄像头进行联合标定

【手眼标定】使用kalibr对imu和双目摄像头进行联合标定

使用kalibr对imu和双目摄像头进行联合标定 前言一、IMU标定二、双目摄像头标定三、手眼标定&#xff08;imu和双目摄像头的联合标定&#xff09; 前言 由于本文的imu、双目摄像头都是在ros2环境下开发&#xff0c;数据传输自然也是在ros2中。 但想要使用kalibr进行标定&#x…
阅读更多...
VUE3 el-cascade组件实现省市区动态加载，完整代码！

VUE3 el-cascade组件实现省市区动态加载，完整代码！

实现动态加载省市区的功能&#xff0c;由于数据量有点多&#xff0c;所以第一次查询出来所有的省&#xff0c;点击省的时候调用接口查询下面的市&#xff0c;点击市的时候在调用接口显示下面的区。官网写的很不详细&#xff0c;泛泛而谈&#xff0c;以下提供完整代码。下面是前…
阅读更多...
STM32学习 修改系统主频

STM32学习 修改系统主频

前面时钟树的学习说明单片机的主频是可以修改的&#xff0c;那么怎么更改系统的主频&#xff0c;这里做一个简单的介绍。首先要明白&#xff0c;单片机的程序是如何运行&#xff0c;这里简单说明一下。 对应的代码在startup_stm32....文件里面&#xff0c;这里是复位程序的汇编…
阅读更多...
202485读书笔记|《我还有一片风景要完成》——溪水急着要流向海洋 浪潮却渴望重回土地 弱水长流，我只能尽一瓢饮，世界大千，我只能作一瞬观

202485读书笔记|《我还有一片风景要完成》——溪水急着要流向海洋 浪潮却渴望重回土地 弱水长流，我只能尽一瓢饮，世界大千，我只能作一瞬观

202485读书笔记|《我还有一片风景要完成》——溪水急着要流向海洋 浪潮却渴望重回土地 弱水长流&#xff0c;我只能尽一瓢饮&#xff0c;世界大千&#xff0c;我只能作一瞬观 《华语散文温柔的一支笔&#xff1a;张晓风作品集&#xff08;共5册&#xff09;》张晓风&#xff0c…
阅读更多...
iOS开发工具-网络封包分析工具Charles

iOS开发工具-网络封包分析工具Charles

想要获取更多更好用的工具可前往​​​​​​​那些年你用过的iOS开发工具-CSDN博客查看 一、Charles简介 Charles 是在 Mac 下常用的网络封包截取工具&#xff0c;在做 移动开发时&#xff0c;我们为了调试与服务器端的网络通讯协议&#xff0c;常常需要截取网络封包来分析。…
阅读更多...
问界M9累计大定破10万，创中国豪车新纪录

问界M9累计大定破10万，创中国豪车新纪录

ChatGPT狂飙160天&#xff0c;世界已经不是之前的样子。 更多资源欢迎关注 6月26日消息&#xff0c;华为常务董事、终端BG董事长、智能汽车解决方案BU董事长余承东今日宣布&#xff0c;问界M9上市6个月&#xff0c;累计大定突破10万辆。 这一成绩&#xff0c;也创造了中国市场…
阅读更多...
基于SpringBoot的私人健身与教练预约管理系统

基于SpringBoot的私人健身与教练预约管理系统

你好呀&#xff0c;我是计算机学姐码农小野&#xff01;如果有相关需求&#xff0c;可以私信联系我。 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SpringBoot框架&#xff0c;B/S架构 工具&#xff1a;Eclipse&#xff0c;Mysql 系统展示 首页 个…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023