当前位置: 首页 > news >正文

【简易版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 通常会将容量翻倍,以避免频繁的内存分配操作,从而减少系统开销。

涉及以下步骤:

  1. 分配一个更大的内存块,通常是当前大小的两倍(这个增长因子取决于实现)。
  2. 将当前所有元素移到新分配的内存中。
  3. 销毁旧元素,并释放旧内存块。
  4. 插入新元素。

image-20240521155911371

  • 在上图中, 有一个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 位置;
  • 增加 Vectorsize
for(size_t i = size; i>index;--i)
{elements[i] = elements[i-1];
}

for循环执行顺序如图:

image-20240521162919322

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标准库实现版本的区别&#xff1a; 基本概念 vector数据结构和数组非常相似&#xff0c;也称为单端数组vector与…...

BRAVE:扩展视觉编码能力,推动视觉-语言模型发展

视觉-语言模型&#xff08;VLMs&#xff09;在理解和生成涉及视觉与文本的任务上取得了显著进展&#xff0c;它们在理解和生成结合视觉与文本信息的任务中扮演着重要角色。然而&#xff0c;这些模型的性能往往受限于其视觉编码器的能力。例如&#xff0c;现有的一些模型可能对某…...

使用 Verdaccio 建立私有npm库

网上有很多方法,但很多没标注nginx的版本所以踩了一些坑,下方这个文档是完善后的,对linux不是很熟练,所以不懂linux不会搭建的跟着做就可以了 搭建方法 首先需要一台云服务器 以139.196.226.123为例登录云服务器 下载node cd /usr/local/lib下载node 解压 下载 wget https://…...

个人职业规划(含前端职业+技术线路)

1. 了解自己的兴趣与长处 喜欢擅长的事 职业方向 2. 设定长期目标&#xff08;5年&#xff09; 目标内容 建立自己的品牌建立自己的社交网络 适量参加社交活动&#xff0c;认识更多志同道合的小伙伴寻求导师指导 建立自己的作品集 注意事项 每年元旦进行审视和调整永葆积极…...

LeetCode | 344.反转字符串

设置头尾两个指针&#xff0c;依靠中间变量temp交换头尾指针所指元素&#xff0c;头指针后移&#xff0c;尾指针前移&#xff0c;直到头尾指针重合或者头指针在尾指针后面一个元素 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对象中的属性操作&#xff08;读写&#xff09;&#xff0c;目的是为了更加方便操作data中的数据 基本原理&#xff1a;通过Object.defineProperty()把data对象所有属性添加到vm上&#xff0c;为每一个添加到vm上的属性&#xff0c;都增…...

Maven 介绍

Maven open in new window 官方文档是这样介绍的 Maven 的&#xff1a; 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截图程序&#xff0c;可多屏幕截图二&#xff0c;增加调整截图区域功能-CSDN博客描述了如何截取&#xff0c;具备调整边缘功能后已经方便使用了&#xff0c;但是与系统自带的程序相比&#xff0c;似乎没有什么特别&#xff0c;只能截取矩形区域。 如果可以按照自己…...

Unity的三种Update方法

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

[Python学习篇] Python字典

字典是一种可变的、无序的键值对&#xff08;key-value&#xff09;集合。字典在许多编程&#xff08;Java中的HashMap&#xff09;任务中非常有用&#xff0c;因为它们允许快速查找、添加和删除元素。字典使用花括号 {} 表示。字典是可变类型。 语法&#xff1a; 变量 {key1…...

react项目中如何书写css

一&#xff1a;问题&#xff1a; 在 vue 项目中&#xff0c;我们书写css的方式很简单&#xff0c;就是在 .vue文件中写style标签&#xff0c;然后加上scope属性&#xff0c;就可以隔离当前组件的样式&#xff0c;但是在react中&#xff0c;是没有这个东西的&#xff0c;如果直…...

PostgreSQL源码分析——绑定变量

这里分析一下函数中应用绑定变量的问题&#xff0c;但实际应用场景中&#xff0c;不推荐这么使用。 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 中的中断可以分为以下几种类型&#xff1a; 软件中断&#xff08;Software Generated Interrupt, SGI&#xff09;&#xff1a;由软件触发&#xff0c;通常…...

吴恩达机器学习 第二课 week2 多分类问题

目录 01 学习目标 02 实现工具 03 概念与原理 04 应用示例 05 总结 01 学习目标 &#xff08;1&#xff09;理解二分类与多分类的原理区别 &#xff08;2&#xff09;掌握简单多分类问题的神经网络实现方法 &#xff08;3&#xff09;理解多分类问题算法中的激活函数与损失…...

112、路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径&#xff0c;这条路径上所有节点值相加等于目标和 targetSum 。如果存在&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 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中的抽象

我们先来看一道题&#xff01; 计算几何对象的面积之和&#xff09;编写一个方法&#xff0c;该方法用于计算数组中所有几何对象的面积之和。该方法的签名是&#xff1a; public static double sumArea(GeometricObject[] a) 编写一个测试程序&#xff0c;该程序创建一个包含四…...

Sping源码(九)—— Bean的初始化(非懒加载)— Bean的创建方式(factoryMethod)

序言 前面文章介绍了在Spring中多种创建Bean实例的方式&#xff0c;包括采用FactoryBean的方式创建对象、使用反射创建对象、自定义BeanFactoryPostProcessor。 这篇文章继续介绍Spring中创建Bean的形式之一——factoryMethod。方法用的不多&#xff0c;感兴趣可以当扩展了解。…...

绝对全网首发,利用Disruptor EventHandler实现在多线程下顺序执行任务

disruptor有两种任务处理器&#xff0c;一个是EventHandler ,另一个是WorkHandler. EventHandler可以彼此独立消费同一个队列中的任务&#xff0c;WorkHandler可以共同竞争消费同一个队列中的任务。也就是说&#xff0c;假设任务队列中有a、b、c、d三个事件&#xff0c;eventHa…...

【JVM】- 内存结构

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

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

HBuilderX安装(uni-app和小程序开发)

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

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 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…...