C++标准模板库——vector的使用及其模拟实现

目录

一. vector的介绍
1.vector的介绍

二.vector的使用

  1. vector中常见接口的介绍
  2. vector的构造和析构函数
  3. vector的三种遍历方式

三.vector的模拟实现

  1. vector的增删查改
  2. vector容器的容量变化和大小增减
  3. vector迭代器失效问题
  4. vector的小框架 构造函数和析构函数
  5. 迭代器和operator[]的实现
  6. vector的拷贝构造函数和operator=
  7. memcpy拷贝问题
  8. 模拟实现整体源代码

一.vector的介绍

1.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统一的迭代器和引用更好。

二. vector的使用

1. vector的常见接口介绍

1.1vector的定义

在这里插入图片描述

1.2 vector 迭代器 的使用

在这里插入图片描述
在这里插入图片描述

1.3 vector的空间增长问题

在这里插入图片描述
测试代码：

#include<iostream>
#include<vector>
using namespace std;void Test_vector2()
{size_t sz;vector<int> v;sz = v.capacity();cout << "making v grow:\n";for (int i = 0; i < 100; ++i){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}int main()
{Test_vector2();return 0;
}

运行结果:
在这里插入图片描述

vs：运行结果：vs下使用的STL基本是按照1.5倍方式扩容

通过reserve()接口提前设置好容量，我们可以减少扩容次数，减少扩容对效率的损耗

测试代码：

#include<iostream>
#include<vector>
using namespace std;void Test_vector1()
{vector<int> v;for (size_t i = 0; i < 10; i++){v.push_back(i);}}void Test_vector2()
{size_t sz;vector<int> v;sz = v.capacity();cout << "making v grow:\n";for (int i = 0; i < 100; ++i){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}void Test_vector3()
{vector<int> v;size_t sz = v.capacity();v.reserve(100); // 提前将容量设置好，可以避免一遍插入一遍扩容cout << "making bar grow:\n";for (int i = 0; i < 100; ++i){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}int main()
{Test_vector3();return 0;
}

在这里插入图片描述

1.4vector的增删查改

在这里插入图片描述
测试代码：

void Test_vector1()
{vector<int> v;for (size_t i = 0; i < 10; i++){v.push_back(i);}cout << "尾插数据后：" << endl;for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";//像数组一样用[]访问vector中的元素}cout << endl;v.pop_back();v.pop_back();cout << "尾删两个数据后：" << endl;for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;vector<int>::iterator it = v.begin();v.insert(it+3, 30);//在下标为3的前面插入一个30for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;it = v.erase(it+3);//删除it位置的数，并把该位置被删除的后面的数的迭代器返回给itfor (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;
}

运行结果：
在这里插入图片描述

2.vector的构造函数和析构函数

在这里插入图片描述

在这里插入图片描述

3.vector的三种遍历方式

测试代码：

void Test_vector4()
{vector<int> v;for (size_t i = 0; i < 10; i++){v.push_back(i);}cout << "第一种用[]进行遍历：" << endl;for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;cout << "第二种用迭代器进行遍历：" << endl;vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;cout << "第三种用范围for进行遍历：" << endl;for (auto e : v){cout << e << " ";}cout << endl;
}

运行结果：
在这里插入图片描述

三.vector的模拟实现

开始时定义个自己的命名空间，然后利用类模板控制vector可以存放多种类型的数据,定义迭代器和私有成员变量，_start相当于vector常用接口中的begin(),_finish相当于end(),_endofstorage相当于_start+capacity();
在这里插入图片描述

#pragma once#include<assert.h>
#include<string.h>
#include<iostream>
using namespace std;
namespace  simulation
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;private:iterator _start;iterator _finish;iterator _endofstorage;};
}

1. vector的增删查改

代码：

//尾插
void  push_back(const T& x)
{if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);			}*_finish = x;_finish++;
}//在pos位置前插入x
void insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage){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 = x;_finish++;}//删除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;
}

测试代码：

void test_vector2()
{simulation::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);v.push_back(8);for (int e : v){cout << e << " ";}cout << endl;//在4前面插入一个40v.insert(v.begin() + 3, 40);for (int e : v){cout << e << " ";}cout << endl;//头插一个100v.insert(v.begin(), 100);for (int e : v){cout << e << " ";}cout << endl;//尾插1000v.insert(v.end(), 1000);for (int e : v){cout << e << " ";}cout << endl;//头删v.erase(v.begin());for (int e : v){cout << e << " ";}cout << endl;//尾删v.erase(v.end() - 1);for (int e : v){cout << e << " ";}cout << endl;
}

运行结果：
在这里插入图片描述

  1. vector容器的容量变化和大小增减

成员函数实现：

void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * sz);for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}}void resize(size_t n, const T& val = T()){if (n <= _finish){_finish = _start + n;}else{reserve(n);while (n + _start > _finish){*_finish = val;_finish++;}}}

在这里插入图片描述

  1. vector迭代器失效问题
    在这里插入图片描述
    在pos位置插入数据时，可能存在扩容问题，扩容一般情况下都会找一块新的空间，然后释放旧空间，把指针指向新的空间，但是此时传进去的参数pos没有跟着空间的变化而与_start发生相对变化，所以这时迭代器就失效了，不能再让迭代器往后使用了，此时想要不让迭代器失效只能保留pos与_start的偏移量，然后等到扩容后把pos位置的迭代器更新，那么pos位置的迭代器才能继续使用。

在这里插入图片描述
erase这个接口也会使得迭代器失效，原因在于删除pos位置的数据之后，pos指向的数据的值已经被删除，所以想要继续使用迭代器需要在该接口返回值那里返回一个迭代器，指向被删除的值的下一个位置的迭代器，方能继续使用.

所以这样实现才是合理的

//删除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;
}
  1. vector的小框架 构造函数和析构函数
    代码实现：
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);first++;}
}vector(size_t n, const T& val = T())
{reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}
}vector(int n, const T& val = T())
{reserve(n);for (int i = 0; i < n; i++){push_back(val);}
}vector():_start(nullptr),_finish(nullptr),_endofstorage(nullptr)
{}vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(v.capacity());for (auto& e : v){push_back(e);}
}vector<T>& operator=(vector<T> tmp)
{swap(tmp);return *this;
}void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);
}~vector()
{delete[] _start;_start = _finish = _endofstorage = nullptr;
}
  1. 迭代器和operator[]的实现
public: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;}T& operator[](size_t pos){assert(pos < size());return _start[pos];}T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}
  1. vector的拷贝构造函数和operator=
vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(v.capacity());for (auto& e : v){push_back(e);}
}vector<T>& operator=(vector<T> tmp)
{swap(tmp);return *this;
}void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);
}
  1. memcpy拷贝问题
    memcpy进行拷贝时会对自定义数据类型的数据进行浅拷贝，而浅拷贝在进行析构的时候，会进行两次析构，导致出现错误，所以拷贝的时候应该进行深拷贝
    如下是代码实现
void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * sz);for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}}

通过for循环一份一份的拷贝到新的空间就不会造成空间被释放两次

  1. 模拟实现整体源代码
#pragma once#include<assert.h>
#include<string.h>
#include<iostream>
using namespace std;
namespace  simulation
{template<class T>class vector{public: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;}size_t size() const{return _finish - _start;}size_t capacity() const{return _endofstorage - _start;}template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(val);}}vector(int n, const T& val = T()){reserve(n);for (int i = 0; i < n; i++){push_back(val);}}vector():_start(nullptr), _finish(nullptr), _endofstorage(nullptr){}vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr){reserve(v.capacity());for (auto& e : v){push_back(e);}}vector<T>& operator=(vector<T> tmp){swap(tmp);return *this;}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v._endofstorage);}~vector(){delete[] _start;_start = _finish = _endofstorage = nullptr;}T& operator[](size_t pos){assert(pos < size());return _start[pos];}T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}void reserve(size_t n){if (n > capacity()){size_t sz = size();T* tmp = new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * sz);for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_endofstorage = _start + n;}}void resize(size_t n, const T& val = T()){if (n <= _finish){_finish = _start + n;}else{reserve(n);while (n + _start > _finish){*_finish = val;_finish++;}}}void  push_back(const T& x){if (_finish == _endofstorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;_finish++;}void insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _endofstorage){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 = 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;iterator _finish;iterator _endofstorage;};
}

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

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

相关文章

基于Java的高校竞赛管理系统设计与实现（亮点：发起比赛、报名、审核、评委打分、获奖排名，可随意更换主题如蓝桥杯、ACM、王者荣耀、吃鸡等竞赛）

基于Java的高校竞赛管理系统设计与实现（亮点：发起比赛、报名、审核、评委打分、获奖排名，可随意更换主题如蓝桥杯、ACM、王者荣耀、吃鸡等竞赛）

高校竞赛管理系统 一、前言二、我的优势2.1 自己的网站2.2 自己的小程序&#xff08;小蔡coding&#xff09;2.3 有保障的售后2.4 福利 三、开发环境与技术3.1 MySQL数据库3.2 Vue前端技术3.3 Spring Boot框架3.4 微信小程序 四、功能设计4.1 主要功能描述4.2 系统角色 五、系统…
阅读更多...
vue获取本地缓存并转为json格式

vue获取本地缓存并转为json格式

场景 要求获取当前登录用户id&#xff0c;传入后台去筛选属于该用户的数据&#xff1b; 当前登录用户信息一般会在本地存储中&#xff0c;有些则是在session中&#xff0c;此处只对本地存储做讨论&#xff1b; 本地缓存的用法 1 存储数据 localStorage.setltem(userId,"…
阅读更多...
VS Code用AI写代码：Codeium插件

VS Code用AI写代码：Codeium插件

文章目录 Codeiumchat代码生成 Codeium Codeium是基于边缘计算的代码AI工具&#xff0c;提供超过70种编程语言的代码补全、对话、搜索等功能&#xff0c;相当霸道。 在插件栏搜索到Codeium之后&#xff0c;需要科学上网安装&#xff0c;安装完成后会提示注册。注册之后&#…
阅读更多...
2023-9-22 滑雪

2023-9-22 滑雪

题目链接&#xff1a;滑雪 #include <cstring> #include <algorithm> #include <iostream>using namespace std;const int N 310;int n, m; int h[N][N]; int f[N][N];int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};int dp(int x, int y) {int &v f…
阅读更多...
MySQL数据库简介+库表管理操作+数据库用户管理

MySQL数据库简介+库表管理操作+数据库用户管理

Mysql Part 1 一、数据库的基本概念1.1 使用数据库的必要性1.2 数据库基本概念1.2.1 数据&#xff08;Data&#xff09;1.2.2 表1.2.3 数据库1.2.4 数据库管理系统&#xff08;DBMS&#xff09;1.2.5 数据库系统 1.3 数据库的分类1.3.1 关系数据库 SQL1.3.2 非关系数据库 NoSQL…
阅读更多...
看阿里测试工程师如何玩转postman+newman+jenkins接口自动化

看阿里测试工程师如何玩转postman+newman+jenkins接口自动化

【软件测试面试突击班】如何逼自己一周刷完软件测试八股文教程&#xff0c;刷完面试就稳了&#xff0c;你也可以当高薪软件测试工程师&#xff08;自动化测试&#xff09; postman用来做接口测试非常方便&#xff0c;接口较多时&#xff0c;则可以实现接口自动化 一、环境准备…
阅读更多...
【DLL修复工具下载】一键修复电脑丢失d3dcompiler_47.dll问题方法

【DLL修复工具下载】一键修复电脑丢失d3dcompiler_47.dll问题方法

在我们使用电脑的过程中&#xff0c;有时候会遇到一些错误提示&#xff0c;其中“缺失 d3dcompiler_47.dll”就是比较常见的一种。那么&#xff0c;d3dcompiler_47.dll 到底是什么呢&#xff1f;为什么会出现缺失的情况&#xff1f;丢失 d3dcompiler_47.dll 又会对电脑产生什么…
阅读更多...
芋道商城，基于 Vue + Uniapp 实现，支持分销、拼团、砍价、秒杀、优惠券、积分、会员等级、小程序直播、页面 DIY 等功能

芋道商城，基于 Vue + Uniapp 实现，支持分销、拼团、砍价、秒杀、优惠券、积分、会员等级、小程序直播、页面 DIY 等功能

商城简介 芋道商城&#xff0c;基于 芋道开发平台 构建&#xff0c;以开发者为中心&#xff0c;打造中国第一流的 Java 开源商城系统&#xff0c;全部开源&#xff0c;个人与企业可 100% 免费使用。 有任何问题&#xff0c;或者想要的功能&#xff0c;可以在 Issues 中提给艿艿…
阅读更多...
低代码助力企业数字化转型

低代码助力企业数字化转型

在当今这个数字化快速发展的时代&#xff0c;企业面临的竞争越来越激烈&#xff0c;数字化转型已成为企业发展的必经之路。低代码平台作为一种新型的开发工具&#xff0c;正在逐渐成为企业数字化转型的重要助力。本文将从数字化转型背景、低代码平台介绍、低代码平台的应用、低…
阅读更多...
SIEM 中的事件关联

SIEM 中的事件关联

什么是 SIEM 中的事件关联 SIEM 中的事件关联可帮助安全团队识别来自不同来源的安全事件并确定其优先级&#xff0c;从而提供更全面的整体安全环境视图。 在典型的 IT 环境中&#xff0c;会跨各种系统和应用程序生成大量事件和日志。孤立地看&#xff0c;其中许多事件可能看起…
阅读更多...
聊一聊 TLS/SSL

聊一聊 TLS/SSL

哈喽大家好&#xff0c;我是咸鱼 当我们在上网冲浪的时候&#xff0c;会在浏览器界面顶部看到一个小锁标志&#xff0c;或者网址以 “https://” 开头 这意味着我们正在使用 TLS/SSL 协议进行安全通信。虽然它可能看起来只是一个小小的锁图标和一个 “https” &#xff0c;但…
阅读更多...
记录一次错误---想让U-net网络输入大小不一致的图片

记录一次错误---想让U-net网络输入大小不一致的图片

最近在看Deeplab系列的论文&#xff0c;文中提到了语义分割领域的一个难题是&#xff1a;将图片输入网络之前需要resize成统一大小&#xff0c;但是resize的话会造成细节信息的损失&#xff0c;所以想要网络处理任意大小的图片输入。我之前训练的U-net网络都是resize成224*224大…
阅读更多...
Linux 本地 Docker Registry本地镜像仓库远程连接【内网穿透】

Linux 本地 Docker Registry本地镜像仓库远程连接【内网穿透】

Linux 本地 Docker Registry本地镜像仓库远程连接 文章目录 Linux 本地 Docker Registry本地镜像仓库远程连接1. 部署Docker Registry2. 本地测试推送镜像3. Linux 安装cpolar4. 配置Docker Registry公网访问地址5. 公网远程推送Docker Registry6. 固定Docker Registry公网地址…
阅读更多...
【CSS】画个三角形或圆形或环

【CSS】画个三角形或圆形或环

首先通过调整边框&#xff0c;我们可以发现一些端倪 <!DOCTYPE html> <html><head><meta charset"utf-8"><title></title></head><style>.box{width: 150px;height:150px;border: 50px solid black;}</style&g…
阅读更多...
【docker安装Mysql并配置主从复制】

【docker安装Mysql并配置主从复制】

Mysql主从复制 目的&#xff1a; 是为了后面naocs集群的服务配置做准备工作 准备工作 准备至少两台虚拟机或服务器&#xff0c;安装好了docker&#xff0c;找到他们的ip地址 后面操作都用xshell操作来代替 拉取并启动mysql镜像和容器 主机的命令为mysql01&#xff0c;对…
阅读更多...
机器学习笔记：seq2seq attentioned seq2seq

机器学习笔记：seq2seq attentioned seq2seq

1 Seq2Seq 1.1 介绍 对于序列对<X,Y>&#xff0c;我们的目标是给定输入序列X&#xff0c;期待通过Encoder-Decoder框架来生成目标序列Y Encoder对输入的序列X进行编码&#xff0c;将输入序列通过非线性变换转化为中间语义表示C&#xff1a; Decoder根据序列X的中间语义…
阅读更多...
百度知道本地搭建环境无限制采集聚合【最新版】

百度知道本地搭建环境无限制采集聚合【最新版】

本工具是本地php环境搭建&#xff0c;根据关键词进行采集聚合某度知道&#xff0c;不限制ip&#xff0c;最新版新添加了违规词过滤&#xff0c;样式处理&#xff0c;自动匹配优质标题等功能&#xff0c;只需要导入关键词可以无限采集&#xff0c;是养站的好帮手&#xff01; 功…
阅读更多...
Golang代码漏洞扫描工具介绍——trivy

Golang代码漏洞扫描工具介绍——trivy

Golang代码漏洞扫描工具介绍——trivy Golang作为一款近年来最火热的服务端语言之一&#xff0c;深受广大程序员的喜爱&#xff0c;笔者最近也在用&#xff0c;特别是高并发的场景下&#xff0c;golang易用性的优势十分明显&#xff0c;但笔者这次想要介绍的并不是golang本身&a…
阅读更多...
2023 Sui Builder House全球之旅圆满收官

2023 Sui Builder House全球之旅圆满收官

2023年的最后一场Builder House于上周在新加坡举行&#xff0c;包括主题演讲、小组讨论和研讨会等聚焦Sui的现在和未来的活动。其中&#xff0c;zkLogin是本次活动的最大亮点。作为一种新的Sui原语&#xff0c;zkLogin允许用户使用Web2身份验证创建帐户&#xff0c;有望推动大规…
阅读更多...
产品解读 | 分布式多模数据库：KaiwuDB

产品解读 | 分布式多模数据库：KaiwuDB

1.KaiwuDB 是什么&#xff1f; KaiwuDB 是由浪潮创新研发的一款分布式、多模融合&#xff0c;支持原生 AI 的数据库产品&#xff0c;拥有“就地计算”等核心技术&#xff0c;具备高速写入、极速查询、SQL 支持、随需压缩、智能预计算、订阅发布、集群部署等特性&#xff0c;具…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023