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

STL之vector

目录

  • vector模拟实现
    • 一. vector的基本框架
    • 二. 常用方法及实现
      • 1.初始化和清理
        • a. 默认构造函数
        • b. 析构函数
      • 2. 迭代器
        • a. begin
        • b. end
      • 3.数据访问
        • a. size
        • b. capacity
        • c. operator[]
        • d. front
        • c. back
      • 4.增删查改操作
        • a. reserve
        • b. resize
        • c. insert
        • d. push_back
        • e. erase
        • f. pop_back
      • 5.构造函数
        • a.迭代器区间构造
        • b. swap
        • c. 拷贝构造
        • d. operator=
        • c.n个val的构造
    • 三.小结
      • 1.代码结构
      • 2.迭代器失效
        • a.插入时
        • b.删除时
      • 3.迭代器操作

vector模拟实现

一. vector的基本框架

template<typename T>
class vector
{
public:typedef T* iterator;private:iterator _start;iterator _finish;iterator _end_of_storage;
}

使用库中的string类需要包含头文件#inlcude<vector>,并且使用std::命名空间
在这里插入图片描述

_start:指向起始元素的地址; _finish:指向最后一个元素的下一个地址; _end_of_storage:指向所申请空间结尾的下一个位置地址

其底层是将数据顺序存储的,即使用一段连续的空间。

二. 常用方法及实现

实现的顺序来依次进行介绍

1.初始化和清理

a. 默认构造函数

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

b. 析构函数

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

2. 迭代器

vector是顺序存储的结构,因此可以用T*(原生指针)当做其迭代器

typedef T* iterator;
typedef const T* const_iterator;

a. begin

iterator begin()
{return _start;
}
const_iterator begin() const
{return _start;
}

b. end

iterator end()
{return _finish;
}
const_iterator end() const
{return _finish;
}

3.数据访问

a. size

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

b. capacity

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

指针相减,得到的是其中该类型元素的个数

c. operator[]

const T& operator[](size_t pos) const
{assert(pos < size());return *(_start + pos);
}
T& operator[](size_t pos)
{assert(pos < size());return *(_start + pos);
}

d. front

T& front()
{assert(size() > 0);return *_start;
}
const T& front() const
{assert(size() > 0);return *_start;
}

c. back

const T& back() const
{assert(size() > 0);return *(_finish - 1);
}

4.增删查改操作

a. reserve

void reserve(size_t n)
{if (n > capacity()){T* temp = new T[n];//将原空间的数据拷贝到新空间中size_t sz = size();for (size_t i = 0; i < sz; ++i){temp[i] = *(_start + i);}delete[] _start;_start = temp;_finish = _start + sz;_end_of_storage = _start + n;}
}

申请n个元素的空间,如果n<原有空间,则不做操作

b. resize

void resize(size_t n, const T& val = T())
{if (n < size()){//保留前n个元素_finish = _start + n;}else{//申请n个元素空间reserve(n);//新增的元素赋valiterator cur = _finish;_finish = _start + n; while (cur != _finish){*cur = val;++cur;} }
}

调整元素个数为n个,如果n<size,只保留前n个元素;如果n>size,新增的元素为val。

其中如果没有传val参数,则使用缺省值T():T类型的匿名对象(内置类型,如:int() = 0)

c. insert

iterator insert(iterator pos, const T& val)
{assert(pos >= _start);assert(pos <= _finish);//如果空间满了就扩容if (_finish == _end_of_storage){//扩容后,可能使用新的空间,pos指向改变size_t s = pos - _start;reserve(capacity() == 0 ? 4 : 2 * capacity());pos = _start + s;}//将pos位到最后元素都向后移动1位iterator cur = _finish - 1;while (cur >= pos){*(cur+1) = *cur;--cur;}*pos = val;++_finish;return pos;
}

扩容操作可能使用新空间,所以要更新迭代器

d. push_back

void push_back(const T& val)
{insert(_finish, val);
}

尾插,在最后一个元素的下一个位置(_finish)存放val

e. erase

iterator erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);//将pos后的元素都向前移动1位iterator cur = pos + 1;while (cur < _finish){*(cur - 1) = *cur;++cur;}--_finish;return pos;
}

删除pos指向的元素,并返回删除位置的下一个位置的迭代器

f. pop_back

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

删除最后一个元素

5.构造函数

a.迭代器区间构造

template<class InputIterator>
vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{while (first != last){push_back(*first);++first;}
}

通过传入的迭代器区间,来根据其区间的值来创建vector对象

b. swap

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

交换两个同类型vector对象的内容,通过作用域限定符::来调用库函数中的swap函数,完成对内置类型的成员变量的交换。

c. 拷贝构造

传统写法:

vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{//提前申请空,减少扩容reserve(v.size());for (const auto& e : v){push_back(e);}
}

现代写法:

通过一个局部对象,和swap来完成

vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{//调用迭代器区间来构造temp对象vector<T> temp(v.cbegin(),v.cend());swap(temp);
}

通过初始化列表,对成员变量进行初始化,然后和经迭代器区间构造函数得到的temp对象进行交换内容,完成拷贝构造。该函数调用结束,局部对象temp会自动调用析构函数,并销毁。

d. operator=

//赋值运算符重载,非构造函数
vector<T>& operator= (vector<T> v)
{swap(v);return *this;
}

传参时,会调用拷贝构造函数完成对局部对象v的初始化,然后交换*this和v的内容,完成对自身对象的赋值。

c.n个val的构造

vector(size_t n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{reserve(n);for (size_t i = 0; i < n; ++i){push_back(val);}
}/*定义时,n应该是非负数的,所以使用size_t,但传参时,通常传入的数字是int类型的,
例如:vector<int> v(5,0);(构造含5个0的v对象),此时参数类型是:(int,int)
无法做到和上面(size,int)的精准匹配,编译器会选择根据
//template<class InputIterator>
//vector(InputIterator first, InputIterator last)
生成调用(int,int)的区间构造构造函数,从而发生错误
所以加入下面的函数
*/
vector(int n, const T& val = T()):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{reserve(n);for (int i = 0; i < n; ++i){push_back(val);}
}

构造的vector对象含n个val元素。其中如果没有传val参数,则使用缺省值T():T类型的匿名对象(内置类型,如:int() = 0)

三.小结

1.代码结构

vector代码代码,可以放在自己的命名空间中,避免冲突

#include <iostream>
#include <assert.h>namespace yyjs
{   template<typename T>class vector{public:typedef T* iterator;typedef const T* const_iterator;...};}

上述的成员函数都是放在class vector类体中,并public修饰

2.迭代器失效

a.插入时

扩容操作可能使用新空间,所以要更新迭代器,如果只是进行扩容,迭代器pos所指向的可能就是野指针,因此会产生迭代器失效因此的程序崩溃

在这里插入图片描述

b.删除时

在这里插入图片描述

在删除vi对象中一个奇数后,迭代器依旧指向被删除元素的位置,然后++,向下一个位置移动

由于erase()操作需要将元素向前挪动,所以之前的迭代器实际上是失效的,因此导致 5 5 5被错过

在这里插入图片描述

3.迭代器操作

由于vector是顺序存储的,所以直接使用其元素指针做其迭代器:typedef T* iterator;

因此,对于iterator的操作,如*(解引用)、++、>等,实际上使用的底层库函数已经实现的对指针(内置类型)的操作符

相关文章:

STL之vector

目录 vector模拟实现一. vector的基本框架二. 常用方法及实现1.初始化和清理a. 默认构造函数b. 析构函数 2. 迭代器a. beginb. end 3.数据访问a. sizeb. capacityc. operator[]d. frontc. back 4.增删查改操作a. reserveb. resizec. insertd. push_backe. erasef. pop_back 5.构…...

2020年CSP-J认证 CCF非专业级别软件能力认证第一轮真题-单项选择题解析

2020 CCF认证第一轮&#xff08;CSP-J&#xff09;真题 一、单项选择题 (共15题&#xff0c;每2分&#xff0c;共30分;每题有且有一个正确选项&#xff09; 1、在内存储器中每个存储单元都被赋予一个唯一的序号,称为 A、下标 B、序号 C、地址 D、编号 答案&#xff1a;C…...

vscode Delete `␍⏎·····`

在公司拉取代码报错 Delete ␍⏎&#xff0c;首先问题的关键是换行导致&#xff0c;相信你看别的博客也知道为什么了&#xff0c;但是我使用别的博客的解决办法&#xff0c;没搞定&#xff0c;无论是配置 auto 还是命令行执行&#xff0c;都不行 下面介绍我的解决办法 我使用…...

读书笔记-《ON JAVA 中文版》-摘要16[第十六章 代码校验]

文章目录 第十六章 代码校验1. 测试1.1 单元测试1.2 JUnit1.3 测试覆盖率的幻觉 2. 前置条件2.1 断言&#xff08;Assertions&#xff09;2.2 Java 断言语法2.3 Guava 断言2.4 使用断言进行契约式设计2.4.1 检查指令2.4.2 前置条件2.4.3 后置条件2.4.4 不变性2.4.5 放松 DbC 检…...

SQL Server:打造高效数据管理系统的利器

使用SQL Server进行数据管理 简介 SQL Server是由Microsoft开发的一款关系型数据库管理系统&#xff0c;它可以用于存储和管理大量结构化数据。本篇博客将介绍如何使用SQL Server进行数据管理。 数据库连接 在开始使用SQL Server之前&#xff0c;需要先建立与数据库的连接。…...

代码随想录二刷day20 | 二叉树之 654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树

day20 654.最大二叉树617.合并二叉树700.二叉搜索树中的搜索98.验证二叉搜索树 654.最大二叉树 题目链接 解题思路&#xff1a; 本题属于构造二叉树&#xff0c;需要使用前序遍历&#xff0c;因为先构造中间节点&#xff0c;然后递归构造左子树和右子树。 确定递归函数的参数…...

python基础知识(十三):numpy库的基本用法

目录 1. numpy的介绍2. numpy库产生矩阵2.1 numpy将列表转换成矩阵2.2 numpy创建矩阵 3. numpy的基础运算4. numpy的基础运算25. 索引 1. numpy的介绍 numpy库是numpy是python中基于数组对象的科学计算库。 2. numpy库产生矩阵 2.1 numpy将列表转换成矩阵 import numpy as …...

【SA8295P 源码分析】16 - TouchScreen Panel (TP)线程函数 tp_recv_thread() 源码分析

【【SA8295P 源码分析】16 - TouchScreen Panel (TP)线程函数 tp_recv_thread 源码分析 一、TP 线程函数:tp_recv_thread()二、处理&上报 坐标数据 cypress_read_touch_data()系列文章汇总见:《【SA8295P 源码分析】00 - 系列文章链接汇总》 本文链接:《【SA8295P 源码…...

Python3数据分析与挖掘建模(13)复合分析-因子关分析与小结

1.因子分析 1.1 探索性因子分析 探索性因子分析&#xff08;Exploratory Factor Analysis&#xff0c;EFA&#xff09;是一种统计方法&#xff0c;用于分析观测变量之间的潜在结构和关联性。它旨在确定多个观测变量是否可以归结为较少数量的潜在因子&#xff0c;从而帮助简化…...

【stable diffusion】图片批量自动打标签、标签批量修改(BLIP、wd14)用于训练SD或者LORA模型

参考&#xff1a; B站教学视频【&#xff1a;AI绘画】新手向&#xff01;Lora训练&#xff01;训练集准备、tag心得、批量编辑、正则化准备】官方教程&#xff1a;https://github.com/darkstorm2150/sd-scripts/blob/main/docs/train_README-en.md#automatic-captioning 一、…...

TCP可靠数据传输

TCP的可靠数据传输 1.TCP保证可靠数据传输的方法 TCP主要提供了检验和、序号/确认号、超时重传、最大报文段长度、流量控制等方法实现了可靠数据传输。 检验和 通过检验和的方式&#xff0c;接收端可以检测出来数据是否有差错和异常&#xff0c;假如有差错就会直接丢失该TC…...

Python 私有变量和私有方法介绍

Python 私有变量和私有方法介绍 关于 Python 私有变量和私有方法&#xff0c;通常情况下&#xff0c;开发者可以在方法或属性名称前加上单下划线&#xff08;_&#xff09;&#xff0c;以表示该方法或属性仅供内部使用&#xff0c;但这只是一种约定&#xff0c;并没有强制执行禁…...

Kotlin Lambda表达式和匿名函数的组合简直太强了

Kotlin Lambda表达式和匿名函数的组合简直太强了 简介 首先&#xff0c;在 Kotlin 中&#xff0c;函数是“第一公民”&#xff08;First Class Citizen&#xff09;。因此&#xff0c;它们可以被分配为变量的值&#xff0c;作为其他函数的参数传递或者函数的返回值。同样&…...

uniapp 小程序 获取手机号---通过前段获取

<template><!-- 获取手机号&#xff0c;登录内容 --><view><!-- 首先需要先登录获取code码&#xff0c;然后才可以获取用户唯一标识openid以及会话密钥及用于解密获取手机的加密信息 --><view click"login">登录</view><view…...

面板安全能力持续增强,新增日志审计功能,1Panel开源面板v1.3.0发布

2023年6月12日&#xff0c;现代化、开源的Linux服务器运维管理面板1Panel正式发布v1.3.0版本。 在这一版本中&#xff0c;1Panel进一步增强了安全方面的能力&#xff0c;包括新增SSH配置管理、域名绑定和IP授权支持&#xff0c;以及启用网站防盗链功能。此外&#xff0c;该版本…...

k8s学习-CKS考试必过宝典

目录 CKS考纲集群安装&#xff1a;10%集群强化&#xff1a;15%系统强化&#xff1a;15%微服务漏洞最小化&#xff1a;20%供应链安全&#xff1a;20%监控、日志记录和运行时安全&#xff1a;20% 报名模拟考试考试注意事项考前考中考后 参考 CKS考纲 集群安装&#xff1a;10% 使…...

jmeter如何将上一个请求的结果作为下一个请求的参数

目录 1、简介 2、用途 3、下载、简单应用 4、如何将上一个请求的结果作为下一个请求的参数 1、简介 在JMeter中&#xff0c;可以通过使用变量来将上一个请求的结果作为下一个请求的参数传递。 ApacheJMeter是Apache组织开发的基于Java的压力测试工具。用于对软件做压力测…...

JAVA如何学习爬虫呢?

学习Java爬虫需要掌握以下几个方面&#xff1a; Java基础知识&#xff1a;包括Java语法、面向对象编程、集合框架等。 网络编程&#xff1a;了解HTTP协议、Socket编程等。 HTML、CSS、JavaScript基础&#xff1a;了解网页的基本结构和样式&#xff0c;以及JavaScript的基本语…...

距离保护原理

距离保护是反映故障点至保护安装处的距离&#xff0c;并根据距离的远近确定动作时间的一种保护。故障点距保护安装处越近&#xff0c;保护的动作时间就越短&#xff0c;反之就越长&#xff0c;从而保证动作的选择性。测量故障点至保护安装处的距离&#xff0c;实际上就是用阻抗…...

从微观世界的RST包文视角助力企业网络应用故障排查和优化

1. 前言 随着互联网的普及和发展&#xff0c;各行业的业务和应用越来越依赖于网络。然而&#xff0c;网络环境的不稳定性和复杂性使得出现各种异常现象的概率变得更高了。这些异常现象会导致业务无法正常运行&#xff0c;给用户带来困扰&#xff0c;甚至影响企业的形象和利益。…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...