[C++] STL_vector使用与常用接口的模拟实现
文章目录
- 1、vector的介绍
- 2、vector的使用
- 2.1 vector的定义
- 2.2 vector迭代器的使用
- 2.3 vector的空间增长问题
- 3、vector的增删查改
- 3.1 push_back(重点)
- 3.2 pop_back(重点)
- 3.3 operator[](重点)
- 3.4 insert
- 3.5 erase
- 3.6 swap
1、vector的介绍
vector文档介绍
- vector是表示可变大小数组的序列容器。
- 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。
- 本质讲,vector使用动态分配数组来存储它的元素。当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间。其做法是,分配一个新的数组,然后将全部元素移到这个数组。就时间而言,这是一个相对代价高的任务,因为每当一个新的元素加入到容器的时候,vector并不会每次都重新分配大小。
- vector分配空间策略:vector会分配一些额外的空间以适应可能的增长,因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何,重新分配都应该是对数增长的间隔大小,以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
- 因此,vector占用了更多的存储空间,为了获得管理存储空间的能力,并且以一种有效的方式动态增长。
- 与其它动态序列容器相比(deque, list and forward_list), vector在访问元素的时候更加高效,在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作,效率更低。比起list和forward_list统一的迭代器和引用更好。
2、vector的使用
vector在实际中非常的重要,在实际中我们熟悉常见的接口就可以,下面列出了哪些接口是要重点掌握的并且会模拟实现。
2.1 vector的定义
(constructor)构造函数声明 | 接口说明 |
---|---|
vector()(重点) | 无参构造 |
vector(size_type n, const value_type& val = value_type() | 构造并初始化n个val |
vector (const vector& x); (重点) | 拷贝构造 |
vector (InputIterator first, InputIterator last); | 使用迭代器进行初始化构造 |
代码实现:
template<class T>class vector{public:typedef T* iterator;//typedef愿意给别人用就放在public,不想就放在privatetypedef const T* const_iterator;vector(){}vector(int n, const T& value = T()){reserve(n);for (size_t i = 0; i < n; i++){push_back(value);}}template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;} }vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}private:iterator _start = nullptr; // 指向数据块的开始iterator _finish = nullptr; // 指向有效数据的尾iterator _endOfStorage = nullptr; // 指向存储容量的尾
};
2.2 vector迭代器的使用
在 vector 中迭代器底层也是原生指针。
iterator的使用 | 接口说明 |
---|---|
begin + end(重点) | 获取第一个数据位置的iterator/const_iterator, 获取最后一个数据的下一个位置的iterator/const_iterator |
rbegin + rend | 获取最后一个数据位置的reverse_iterator,获取第一个数据前一个位置的reverse_iterator |
模拟实现:
typedef T* iterator;//typedef愿意给别人用就放在public,不想就放在private
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;
}
使用:
迭代器一般使用在遍历,我们来看一下。
#include <iostream>
#include <vector>
using namespace std;int main()
{vector<int> v;//我们这里使用push_back来插入数据v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//迭代器方式遍历vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}return 0;
}
2.3 vector的空间增长问题
容量空间 | 接口说明 |
---|---|
size | 获取数据个数 |
capacity | 获取容量大小 |
empty | 判断是否为空 |
resize(重点) | 改变vector的size |
reserve(重点) | 改变vector的capacity |
reserve接口:
reserve只负责开辟空间,如果确定知道需要用多少空间,reserve可以缓解vector增容的代价缺陷问题。
void reserve(size_t n)//reserve只扩不缩
{if (n > capacity()){T* tmp = new T[n];size_t sz = size();//这里必须先记下sz,_finish要是直接+size()会出问题//_start指的是新空间,调用size(),size()内部会出问题//因此先记下来后面用最合适if (_start){//memcpy是浅拷贝,会出问题//memcpy(tmp, _start, sizeof(T) * sz);for (size_t i = 0; i < size(); i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_endOfStorage = _start + n;}
}
resize接口:
resize在开空间的同时还会进行初始化,影响size。
void resize(size_t n, const T& value = T())//匿名对象/临时对象具有常性,需要const修饰
{if (n <= size())//缩容{_finish = _start + n;}else{reserve(n);//这里可以不用判断是否要扩容,reserve里面会判断while (_finish < _start + n){*_finish = value;++_finish;}}
}
其他几个接口比较简单,直接实现:
size_t size() const
{return _finish - _start;
}size_t capacity() const
{return _endOfStorage - _start;
}bool empty()
{return _finish - _start == 0;
}
注意:
在扩容的时候有一个区别,vs下capacity是按1.5倍增长的,g++是按2倍增长的。不要固化的认为,vector增容都是2倍,具体增长多少是根据具体的需求定义的。vs是PJ版本STL,g++是SGI版本STL。
我们来测试一下:
#include <iostream>
#include <vector>
using namespace std;int main()
{vector<int> v;size_t sz = v.capacity();for (size_t i = 0; i < 100; i++){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed:" << sz << endl;}}return 0;
}
3、vector的增删查改
vector增删查改 | 接口说明 |
---|---|
push_back(重点) | 尾插 |
pop_back(重点) | 尾删 |
find | 查找 |
insert | 在position之前插入val |
erase | 删除position位置的数据 |
swap | 交换两个vector的数据空间 |
operator[](重点) | 像数组一样访问 |
3.1 push_back(重点)
我们梳理尾插的思路:
1、先判断容量是否满了,如果满了先扩容。这里注意,尾插的时候是否为空,这里使用三木操作符进行判断一下,如果为空先扩4个空间,否则2倍扩法。
2、尾插,再++_finish。
void push_back(const T& x)
{if (_finish == _endOfStorage){reserve(capacity() == 0 ? 4 : 2 * capacity());}*_finish = x;++_finish;
}
3.2 pop_back(重点)
在尾删的时候我们依然是先判断
这次我们需要判空,用断言assert(_finish - _start != 0),再去尾删,让_finish–就好了,下一次尾插的时候直接覆盖。
void pop_back()
{assert(_finish-_start != 0);--_finish;//erase(end() - 1);
}
3.3 operator[](重点)
[]的重载就是返回pos位置上数据就可以,比较简单直接秒杀。
我们这里给两个接口,一个是只读的,一个是可以修改的。
T& operator[](size_t pos)//写
{assert(pos < size());//判断位置是否合法return _start[pos];
}const T& operator[](size_t pos)const//读
{assert(pos < size());return _start[pos];
}
3.4 insert
insert是在pos位置插入一个数据。
思路:
1、先判断pos位置是否合法;
2、判满,如果满了就需要扩容,在扩容的时候需要注意迭代器失效的问题;
3、因为插入数据就存在挪动数据,因此需要先挪动数据,我们 从后往前 依次后移一个位置的数据,挪到pos位置;
4、再去给pos位置插入数据,最后返回pos位置。
iterator insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _endOfStorage){size_t len = pos - _start;//先记下_start到pos位置的距离,因为扩容后迭代器pos就会失效reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + len;//新的空间需要更新迭代器pos}iterator end = _finish - 1;//挪动数据while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;return pos;
}
3.5 erase
erase是删除pos位置的数据。
思路:
1、判断pos位置是否合法;
2、挪动数据,从 pos位置到尾 依次向前挪动数据,直接用pos+1的数据覆盖掉pos位置的数据即可;
3、–_finish,返回pos位置即可。
iterator erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;//挪动数据while (it < _endOfStorage){*(it - 1) = *it;++it;}--_finish;return pos;
}
3.6 swap
我们vector的swap直接套用库函数的swap来实现就好了。
void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);
}
*** 本篇结束 ***
相关文章:

[C++] STL_vector使用与常用接口的模拟实现
文章目录 1、vector的介绍2、vector的使用2.1 vector的定义2.2 vector迭代器的使用2.3 vector的空间增长问题 3、vector的增删查改3.1 push_back(重点)3.2 pop_back(重点)3.3 operator[](重点)3.4 insert3.…...

【LeetCode】167. 两数之和 II - 输入有序数组 - 双指针
目录标题 2023-8-23 09:25:08 2023-8-23 09:25:08 自己写的不是常量级的额外空间,但是写出来了,记录一下。 下次写的时候,请用双指针。 (其实我想了想一想,双指针就没感觉出来:因为我只想到双指针两个都…...

YOLOV1
YOU ONLY LOOK ONCE...

美团增量数仓建设新进展
摘要:本文整理自美团系统研发工程师汤楚熙,在 Flink Forward Asia 2022 实时湖仓专场的分享。本篇内容主要分为四个部分: 建设背景核心能力设计与优化业务实践未来展望 点击查看原文视频 & 演讲PPT 一、美团增量数仓的建设背景 美团数仓架…...
LeetCode解法汇总2337. 移动片段得到字符串
目录链接: 力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目: https://github.com/September26/java-algorithms 原题链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 描述: 给你两个字…...
Fpass与Fstop
在MATLAB中,“Fpass”、“Fstop”、"Apass"和"Astop"是数字滤波器设计中常用的参数。它们用于定义滤波器的频率响应和滤波器的性能。 "Fpass"表示通带频率,指的是滤波器允许通过的频率范围。在数字滤波器设计中࿰…...

Java快速入门体验
Java快速入门体验 一、环境信息1.1 硬件信息1.2 软件信息 二、Maven安装2.1 Maven介绍2.2 Maven安装包下载2.3 Maven安装2.4 Maven初始化 三、Java安装3.1 JDK下载3.2 JDK安装3.3 JDK初始化 四、开发环境搭建4.1 安装开发工具4.2 关联Maven环境4.2.1 新建JAVA项目4.2.2 Maven与…...
父组件传给子组件的数据是异步的,为什么会导致子组件比父组件先执行?
当父组件传递给子组件的数据是异步获取的时候,可能会导致子组件先执行的问题。这是因为在 Vue 的更新机制中,当组件的模板开始渲染时,会立即触发子组件的创建和挂载过程,而父组件的数据可能还没有完全加载完成。 具体来说…...

泛型编程 学习笔记
#include "iostream"using namespace std;template<typename T> void Print(T a) {cout << a << endl; }int main() {int a 5;double b 2.3;char c e;string d "sdfasd";Print(a);Print(b);Print(c);Print(d);return 0; } 它可以不用…...

电脑文件删除了可以找回吗?分享一种简单恢复删除电脑文件办法!
电脑文件删除了可以找回吗?可以。在原理上讲电脑删除的文件是有希望恢复的,因为操作系统在删除文件的时候并会不会立刻将文件彻底删除。当文件被删除的时候,其文件记录被删除,并且被文件占用的磁盘空间被标记为空闲。 这样对于用户…...
Pygame编程(4)event模块
Pygame编程(4)event模块 函数示例 函数 pygame.event.pump 让 Pygame 内部自动处理事件pygame.event.get 从队列中获取事件pygame.event.poll 从队列中获取一个事件pygame.event.wait 等待并从队列中获取一个事件pygame.event.peek 检测某类型事件是否在…...

Python数据采集实战-使用BeautifulSoup框架解析HTML文档并提取所需内容(附源码和实现效果)
实现功能 使用BeautifulSoup框架解析HTML文档并提取所需内容的例子:假设我们要从以下HTML文档中提取所有超链接的链接地址 实现代码 from bs4 import BeautifulSoup import requests# 发送请求并获取HTML文档 url "https://www.baidu.com" response r…...

Java“牵手”天猫商品列表数据,关键词搜索天猫商品数据接口,天猫API申请指南
天猫商城是一个网上购物平台,售卖各类商品,包括服装、鞋类、家居用品、美妆产品、电子产品等。要获取天猫商品列表和商品详情页面数据,您可以通过开放平台的接口或者直接访问天猫商城的网页来获取商品详情信息。以下是两种常用方法的介绍&…...

idea切换Git分支时保存未提交的文件
解决方案 我们现在有三个分支,如下图: 我们目前在tenant分支上进行开发,需要去修复master的Bug,假设我们在tenant分支上修改了一个文件,如下图: 方法一:使用Shelve Changes 1、选中tenant上你不…...
Qt串口通信学习文档
这是官方文档,我也在学习。 QSerialPort Class | Qt Serial Port 5.15.14https://doc.qt.io/qt-5/qserialport.html...
018-时间处理库,预处理
018-时间处理库,预处理 ⼀、C语⾔的时间处理库 time.h是C/C++中的⽇期和时间头⽂件,通过他可以获取系统时间及时间格式 转换 time库中常⽤函数介绍 1、函数名称: time 2、函数名称: localtime 3、函数名称: asctime 4、函数名称: ctime 5、函数名称: gmtime 6、函数名…...

Sketch 98 中文版-mac矢量绘图设计
Sketch是一款专为Mac操作系统设计的矢量图形编辑软件,被广泛应用于UI/UX设计、网页设计、移动应用设计等领域。Sketch提供了各种工具和功能,包括绘图、图形设计、排版等,可以帮助设计师轻松地创建高质量的矢量图形和模型。Sketch的主要特点包…...
Springboot继承Keycloak实现单点登陆与退出
由于网上博客大部分都只有登陆没有退出,自己花了一些时间研究了一下,这里将相关内容进行记录,基于Keyclaok 20的版本,实现springboot服务单点登录与退出 一、依赖 <!-- 在父工程中 --> <dependencyManagement><d…...

天眼查接口 查询企业信息API 企查查接口
item_get-获得tyc详情 tyc.item_get 公共参数 请求地址: https://api-gw.cn/tyc/item_get 名称类型必须描述keyString是调用key(必须以GET方式拼接在URL中)secretString是调用密钥api_nameString是API接口名称(包括在请求地址中࿰…...

Linux 网络编程 和 字节序的概念
网络编程概述 不同于之前学习的所有通讯方法,多基于Linux内核实现,只能在同一个系统中不同进程或线程间通讯,Linux的网络编程可以实现真正的多机通讯! 两个不相关的终端要实现通讯,必须依赖网络,通过地址…...

从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...

Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

排序算法总结(C++)
目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...