【简易版tinySTL】 vector容器
文章目录
- 基本概念
- 功能
- 思路
- 代码实现
- vector.h
- test.cpp
- 代码详解
- 变量
- 构造函数
- 析构函数
- 拷贝构造
- operator=
- push_back
- operator[]
- insert
- printElements
- 本实现版本 和 C++ STL标准库实现版本的区别:
基本概念
- vector数据结构和数组非常相似,也称为单端数组
- vector与普通数组区别: 不同之处在于数组是静态空间,而vector可以动态扩展
- 动态扩展: 并不是在原空间之后续接新空间,而是找更大的内存空间,然后将原数据拷贝新空间,释放原空间
功能
设计一个 Vector 类,该类应具备以下功能和特性:
1、基础成员函数:
- 构造函数:初始化 Vector 实例
- 析构函数:清理资源,确保无内存泄露
- 拷贝构造函数:允许通过现有的 MyVector 实例来创建一个新实例
- 拷贝赋值操作符:实现 MyVector 实例之间的赋值功能
2、核心功能:
- 添加元素到末尾:允许在 Vector 的末尾添加新元素
- 获取元素个数:返回 Vector 当前包含的元素数量
- 获取容量:返回 Vector 可以容纳的元素总数
- 访问指定索引处的元素:通过索引访问特定位置的元素
- 在指定位置插入元素:在 Vector 的特定位置插入一个新元素
- 删除数组末尾元素:移除 Vector 末尾的元素
- 清空数组:删除 Vector 中的所有元素,重置其状态
3、遍历:
- 遍历并打印数组元素:提供一个函数,通过迭代器遍历并打印出所有元素
4、高级特性:
- 容器扩容:当前容量不足以容纳更多元素时,自动扩展 Vector 的容量以存储更多元素
思路
内存分配
当容量不足以容纳新元素时,std::vector
会分配一块新的内存空间,将原有元素复制到新的内存中,然后释放原内存。这个过程确保了元素的连续存储。
动态扩容
当需要进行扩容时,std::vector
通常会将容量翻倍,以避免频繁的内存分配操作,从而减少系统开销。
涉及以下步骤:
- 分配一个更大的内存块,通常是当前大小的两倍(这个增长因子取决于实现)。
- 将当前所有元素移到新分配的内存中。
- 销毁旧元素,并释放旧内存块。
- 插入新元素。
- 在上图中, 有一个
vector<int> v
对象, 其成员变量存储在在了栈上, 包括size
,capacity
,data pointer
,分别表示数组已经使用的大小、数组的容量、数组的首地址, 最左边表示初始时刻的堆栈状态, - 某时刻调用
v.push_back(20)
, 检查发现此操作不会超出容量上限, 因此在中间的堆栈示意图中插入了20, 并更新控制结构中的size = 2
- 下一时刻调用
v.push_back(30)
, 此时检查发现此操作要求的容量不足, 因此需要重新在堆内存申请容量为4的内存空间, 如右边的示意图所示, 并且复制原来的内容到新的地址, 完成此操作后可以丢弃原来的堆内存空间, 并插入30
代码实现
vector.h
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <stdexcept>namespace mystl{
template <typename T>
class Vector
{
private:T *elements; size_t capacity; size_t size; public:Vector():elements(nullptr), capacity(0), size(0){};~Vector(){delete[] elements; }Vector(const Vector& other):capacity(other.capacity),size(other.size){elements = new T[capacity];std::copy(other.elements, other.elements+size, elements);}Vector& operator=(const Vector& other) {if(this != &other) {delete[] elements; capacity = other.capacity;size = other.size;elements = new T[capacity];std::copy(other.elements, other.elements+size, elements);}return *this; }void push_back(const T& value){if(size == capacity){reserve(capacity==0? 1:2*capacity);}elements[size++] = value;}size_t getSize() const{return size;}size_t getCapacity() const{return capacity;}T& operator[](size_t index){if(index >= size){throw std::out_of_range("Index out of range");}return elements[index];}void insert(size_t index, const T& value){if(index > size){throw std::out_of_range("Index out of range");}if(size == capacity){reserve(capacity == 0? 1:capacity*2);}for(size_t i = size; i>index;--i) // TODO:为什么不是i--?{elements[i] = elements[i-1];}elements[index] = value;++size;}void pop_back(){if(size > 0){--size; }}void clear(){size = 0;}T* begin(){return elements;}T* end(){return elements+size;}const T* begin() const{return elements;}const T* end() const{return elements+size;}void printElements() const {for(size_t i = 0; i<size; ++i){std::cout << elements[i] << " ";}std::cout << std::endl;}private:void reserve(size_t newCapacity){if(newCapacity > capacity){T* newElements = new T[newCapacity];std::copy(elements,elements+size,newElements);delete[] elements;elements = newElements;capacity = newCapacity;}}};
}
test.cpp
#include "vector.h"
#include "list.h"
#include "deque.h"void vectorTest()
{mystl::Vector<int> v1;v1.push_back(10);mystl::Vector<int> v2(v1);mystl::Vector<int> v3 = v2;for(int i = 0; i < 5; i++){v3.push_back(i);}int size = v3.getSize();int cap = v3.getCapacity();int t = v3[3];std::cout << t << std::endl;v3.insert(2,88);v3.pop_back();int* ptr = v3.begin();v3.printElements();v3.clear();
}int main()
{vectorTest();system("pause");return 0;
}
代码详解
变量
T *elements; // 指向动态数组的指针
size_t capacity; // 数组的容量, size_t = unsigned int
size_t size; // 数组中元素的个数
- elements: 指向动态数组的指针
- capacity:数组的容量, size_t = unsigned int
- size: 数组中元素的个数
构造函数
Vector():elements(nullptr), capacity(0), size(0){};
构造函数:初始化Vector对象,默认设置指针悬空,容量设置为0,当前元素的数量也为0
析构函数
~Vector(){delete[] elements; // elements是数组指针}
析构函数:销毁Vector对象,释放指针
拷贝构造
Vector(const Vector& other):capacity(other.capacity),size(other.size)
{// 找一块地方开辟地址空间elements = new T[capacity];std::copy(other.elements, other.elements+size, elements);
}
拷贝构造函数,cap、size都默认和副本相同
std::copy()
:
- 作用:从一个容器复制元素到另一个容器。
- std::copy需要三个参数:两个指定要复制的元素范围的迭代器(起始迭代器和结束迭代器),以及一个指向目标位置开始的迭代器。
指针也是一种天然的迭代器
operator=
// 拷贝复制+运算符重载Vector& operator=(const Vector& other) {{delete[] elements; // 获取副本的数据capacity = other.capacity;size = other.size;elements = new T[capacity];// 分配新内存,并复制所有元素std::copy(other.elements, other.elements+size, elements);}return *this; }
if(this != &other)
:通过判断两个指针是否相同,检查是不是自赋值的情况delete[] elements;
:删除这一块地址的数据、指针return *this;
: 返回当前对象的引用
push_back
// push_back函数void push_back(const T& value){if(size == capacity){reserve(capacity==0? 1:2*capacity);}elements[size++] = value;}
if(size == capacity)
:如果内存将要溢出,则开辟更大的空间reserve(capacity==0? 1:2*capacity);
:不能简单的将capacity容量翻倍, 需要考虑0的边界情况,如果是开始时刻,没有分配内存,则分配1块内存,否则内存空间加倍
operator[]
下标操作符重载,允许通过下标访问Vector中的元素
T& operator[](size_t index)
{// 如果指定的下标越界(大于或等于 size),则抛出 std::out_of_range 异常if(index >= size){throw std::out_of_range("Index out of range");}return elements[index];
}
当 int arr[] = { 99, 15, 100, 888, 252 }
时,arr是指向数组首地址的指针。可以采用 arr[i]
的形式访问数组元素。如果 p 是指向数组 arr 的指针,那么也可以使用 p[i] 来访问数组元素,它等价于 arr[i]
。因此,elements[index]
等同于vector v[index]
insert
void insert(size_t index, const T& value)
{if(index > size){throw std::out_of_range("Index out of range");}if(size == capacity){reserve(capacity == 0? 1:capacity*2);}// 后续元素后移for(size_t i = size; i>index;--i){elements[i] = elements[i-1];}elements[index] = value;++size;
}
- 在
Vector
的指定位置index
插入一个元素value
; - 如果
index
大于size
,则抛出std::out_of_range
异常; - 如果当前没有足够的容量来存储新元素,则通过
reserve
函数扩展数组的容量; - 将
index
之后的所有元素向后移动一个位置,为新元素腾出空间; - 将新元素放置在
index
位置; - 增加
Vector
的size
for(size_t i = size; i>index;--i)
{elements[i] = elements[i-1];
}
for循环执行顺序如图:
printElements
void printElements() const
{for(size_t i = 0; i<size; ++i){std::cout << elements[i] << " ";}std::cout << std::endl;
}
const 关键字在成员函数声明之后表示该函数不会修改类的任何成员变量
本实现版本 和 C++ STL标准库实现版本的区别:
内存分配策略不同、无范围检查和异常处理、只实现了一些基本的功能,例如插入、删除、访问元素等,而没有涵盖 std::vector
的所有功能和特性
相关文章:

【简易版tinySTL】 vector容器
文章目录 基本概念功能思路代码实现vector.htest.cpp 代码详解变量构造函数析构函数拷贝构造operatorpush_backoperator[]insertprintElements 本实现版本 和 C STL标准库实现版本的区别: 基本概念 vector数据结构和数组非常相似,也称为单端数组vector与…...

BRAVE:扩展视觉编码能力,推动视觉-语言模型发展
视觉-语言模型(VLMs)在理解和生成涉及视觉与文本的任务上取得了显著进展,它们在理解和生成结合视觉与文本信息的任务中扮演着重要角色。然而,这些模型的性能往往受限于其视觉编码器的能力。例如,现有的一些模型可能对某…...
使用 Verdaccio 建立私有npm库
网上有很多方法,但很多没标注nginx的版本所以踩了一些坑,下方这个文档是完善后的,对linux不是很熟练,所以不懂linux不会搭建的跟着做就可以了 搭建方法 首先需要一台云服务器 以139.196.226.123为例登录云服务器 下载node cd /usr/local/lib下载node 解压 下载 wget https://…...
个人职业规划(含前端职业+技术线路)
1. 了解自己的兴趣与长处 喜欢擅长的事 职业方向 2. 设定长期目标(5年) 目标内容 建立自己的品牌建立自己的社交网络 适量参加社交活动,认识更多志同道合的小伙伴寻求导师指导 建立自己的作品集 注意事项 每年元旦进行审视和调整永葆积极…...

LeetCode | 344.反转字符串
设置头尾两个指针,依靠中间变量temp交换头尾指针所指元素,头指针后移,尾指针前移,直到头尾指针重合或者头指针在尾指针后面一个元素 class Solution(object):def reverseString(self, s):""":type s: List[str]:r…...
一步一步用numpy实现神经网络各种层
1. 首先准备一下数据 if __name__ "__main__":data np.array([[2, 1, 0],[2, 2, 0],[5, 4, 1],[4, 5, 1],[2, 3, 0],[3, 2, 0],[6, 5, 1],[4, 1, 0],[6, 3, 1],[7, 4, 1]])x data[:, :-1]y data[:, -1]for epoch in range(1000):...2. 实现SoftmaxCrossEntropy层…...
vue学习(二)
9.vue中的数据代理 通过vm对象来代理data对象中的属性操作(读写),目的是为了更加方便操作data中的数据 基本原理:通过Object.defineProperty()把data对象所有属性添加到vm上,为每一个添加到vm上的属性,都增…...

Maven 介绍
Maven open in new window 官方文档是这样介绍的 Maven 的: Apache Maven is a software project management and comprehension tool. Based on the concept of a project object model (POM), Maven can manage a projects build, reporting and documentation fr…...

QT截图程序三-截取自定义多边形
上一篇文章QT截图程序,可多屏幕截图二,增加调整截图区域功能-CSDN博客描述了如何截取,具备调整边缘功能后已经方便使用了,但是与系统自带的程序相比,似乎没有什么特别,只能截取矩形区域。 如果可以按照自己…...

Unity的三种Update方法
1、FixedUpdate 物理作用——处理物理引擎相关的计算和刚体的移动 (1) 调用时机:在固定的时间间隔内,而不是每一帧被调用 (2) 作用:用于处理物理引擎的计算,例如刚体的移动和碰撞检测 (3) 特点:能更准确地处理物理…...

[Python学习篇] Python字典
字典是一种可变的、无序的键值对(key-value)集合。字典在许多编程(Java中的HashMap)任务中非常有用,因为它们允许快速查找、添加和删除元素。字典使用花括号 {} 表示。字典是可变类型。 语法: 变量 {key1…...

react项目中如何书写css
一:问题: 在 vue 项目中,我们书写css的方式很简单,就是在 .vue文件中写style标签,然后加上scope属性,就可以隔离当前组件的样式,但是在react中,是没有这个东西的,如果直…...
PostgreSQL源码分析——绑定变量
这里分析一下函数中应用绑定变量的问题,但实际应用场景中,不推荐这么使用。 prepare divplan2(int,int) as select div($1,$2); execute divplan2(4,2);语法解析 分别分析prepare语句以及execute语句。 gram.y中定义 /******************************…...

Zynq学习笔记--了解中断配置方式
目录 1. 简介 2. 工程与代码解析 2.1 Vivado 工程 2.2 Vitis 裸机代码 2.3 关键代码解析 3. 总结 1. 简介 Zynq 中的中断可以分为以下几种类型: 软件中断(Software Generated Interrupt, SGI):由软件触发,通常…...

吴恩达机器学习 第二课 week2 多分类问题
目录 01 学习目标 02 实现工具 03 概念与原理 04 应用示例 05 总结 01 学习目标 (1)理解二分类与多分类的原理区别 (2)掌握简单多分类问题的神经网络实现方法 (3)理解多分类问题算法中的激活函数与损失…...

112、路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。 叶子节点 是指没有子节点…...
Vue 封装组件之Input框
封装Input组件:MyInput.vue <template><div class"base-input-wraper"><el-inputv-bind"$attrs"v-on"$listeners"class"e-input":style"inputStyle":value"value":size"size"input&quo…...
一段代码让你了解Java中的抽象
我们先来看一道题! 计算几何对象的面积之和)编写一个方法,该方法用于计算数组中所有几何对象的面积之和。该方法的签名是: public static double sumArea(GeometricObject[] a) 编写一个测试程序,该程序创建一个包含四…...

Sping源码(九)—— Bean的初始化(非懒加载)— Bean的创建方式(factoryMethod)
序言 前面文章介绍了在Spring中多种创建Bean实例的方式,包括采用FactoryBean的方式创建对象、使用反射创建对象、自定义BeanFactoryPostProcessor。 这篇文章继续介绍Spring中创建Bean的形式之一——factoryMethod。方法用的不多,感兴趣可以当扩展了解。…...
绝对全网首发,利用Disruptor EventHandler实现在多线程下顺序执行任务
disruptor有两种任务处理器,一个是EventHandler ,另一个是WorkHandler. EventHandler可以彼此独立消费同一个队列中的任务,WorkHandler可以共同竞争消费同一个队列中的任务。也就是说,假设任务队列中有a、b、c、d三个事件,eventHa…...

【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...

HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
WebRTC从入门到实践 - 零基础教程
WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC? WebRTC(Web Real-Time Communication)是一个支持网页浏览器进行实时语音…...
Oracle11g安装包
Oracle 11g安装包 适用于windows系统,64位 下载路径 oracle 11g 安装包...
Python 训练营打卡 Day 47
注意力热力图可视化 在day 46代码的基础上,对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...