STL解析——vector的使用及模拟实现

article/2025/7/18 21:46:01

目录

1.使用篇

1.1默认成员函数

1.2其他常用接口

2.模拟实现

2.1源码逻辑参考

2.2基本函数实现

2.3增

2.4删

2.5迭代器失效

2.6拷贝构造级其他接口

2.7赋值运算符重载(现代写法)

2.8深层次拷贝优化

3.整体代码

在C++中vector算正式STL容器，功能可以类比于数据结构中的顺序表，用法可以看作简化版的string。

1.使用篇

vector中的接口相比string会少很多，设计逻辑会更为合理，下面对常用接口进行讲解。

1.1默认成员函数

vector中显示的默认成员函数包括构造，析构和赋值运算符重载。

构造函数

(1)将vector对象初始化成一个空对象。

(2)将对象初始化为n个val值。

(3)将对象初始化为某一迭代器区间内的值.

(4)将对象x拷贝给对象。

代码示例如下：

#include<iostream>
#include<vector>using namespace std;void test01()
{vector<int> v1;vector<int> v2(10, 1);vector<int> v3(v2.begin(), v2.end());
}int main()
{test01();return 0;
}

通过调试观察如下：

析构

销毁每个容器元素，并释放所有申请的空间

 赋值运算符重载

将另一同模板对象赋值给目前对象 

1.2其他常用接口

在讲其他接口前，需要注意的是vector并没有重载流插入运算符，因此想给vector进行流插入时需要遍历vector元素，给每个可进行流插入的元素进行输入，这时便常用resize进行大小初始化，防止越界访问报错。

 功能是将对象的大小初始化为n，并值为val。代码示例如下：

#include<iostream>
#include<vector>using namespace std;void test02()
{vector<int> v1;v1.resize(10);
}int main()
{test02();return 0;
}

调试结果如下:

这样resize后便能进行流插入： 

下面介绍与resize看着类似的reserve,reserve功能是提前预留看见，适用于知道大体空间大小的情况下插入数据 

但预留空间里面还是个空容器， 只能进行插入操作。下面便介绍插入接口

在数据结构中顺序表最典型的插入操作便是尾插，vector中则是push_back()

即在尾部新增一个元素val，若空间不足会自动进行空间的扩容。

后面一些接口会在模拟实现中逐步讲解。

2.模拟实现

对于vector的模拟实现主要是对vector增，删，查，改功能的实现，vector作为正式STL容易，这里模拟实现参考stl3.0版本源码实现逻辑，进而深入理解vector容器。

2.1源码逻辑参考

在STL3.0源代码中可以看到，与C顺序表不同的是vector容器实现逻辑是通过三个迭代器，而这个版本的迭代器代表是指针，因此下面的模拟实现也会通过给出三个迭代器指针来实现。

2.2基本函数实现

这里的基本函数实现主要包括：vector的创建，实现增删查改功能之前的基本函数(构造，析构，扩容等)

对于vector的创建：首先为了对容器储存类型的不确定性进行处理，这里要使用C++的模板功能。成员变量主要是开始位置迭代器(_start)，最后一个元素位置迭代器(_finish)，空间最后一个位置迭代器(_end_of_storage)。其次为了不与库中的vector命名冲突，模拟实现的vector放在命名空间my_vector下。代码如下：

namespace my_vector
{template<class T>class vector{public://定义迭代器typedef T* iteractor;//功能private://成员变量iteractor _start;iteractor _finish;iteractor _end_of_storage;};
}

完成定义后，再进行类中最基本的拷贝构造进行完成：最简单的实现方式就是将3个迭代器都置为nullptr。代码如下：

namespace my_vector
{template<class T>class vector{public://定义迭代器typedef T* iteractor;vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}//功能private://成员变量iteractor _start;iteractor _finish;iteractor _end_of_storage;};

其次要注意这里的类定义声明和定义不能分离在不同文件，主要原因是对于使用了模板的类或函数不能在不同文件进行声明和定义。

下面实现几个基本函数来帮助完成尾插操作：为了完成插入操作，我们需要优先考虑vector的空间问题，因此要有扩容(reserve)，其次在扩容中要访问原来的元素个数来方便拷贝(size)，顺便进行空间大小的访问(capacity)，然后才能进行尾插。

因此优先完成size：对于元素个数，只需要返回末迭代器减开始位置迭代器的值即可(指针-指针表示范围内的元素个数)

对于reserve，参数需要一个表示扩容空间大小的n。其次在实现时只有条件n > capacity时才进行扩容。随后进行扩容时，需开辟一个n大小的空间，且若原来不为空时，要将原空间元素拷贝到新空间，并对原空间进行释放。再将3个迭代器都进行更新：

size_t size()const
{return _finish - _start;
}size_t capacity()const
{return _end_of_storage - _start;
}void reserve(size_t n)
{if(n > capacity()){size_t old_size = size();iterator tmp = new T[n];if(_start){memcopy(tmp, _start, old_size*sizeof(T));delete[] _start;}_start = tmp;_finish = _start + old_size;_end_of_storage = _start + n;
}

要注意这里_finish在更新时，因为涉及扩容拷贝，_start的指针位置是改变了的，若次数+的是size那么则无法更新成功，简而言之就是在start更新后，finish更新前这段代码区内size()其实是失效的这里解决方案一般是在函数开始时用old_size记录原size大小，在后面需要调用size的地方使用old_size。

在尾插前要实现的函数基本就这些，在尾插后为方便观察要实现下变量相关的迭代器和[ ]运算符重载，因逻辑比较简单，这里直接展示代码：

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 i)
{assert(i < size());return _start[i];
}const T& operator[](size_t i) const
{assert(i < size());return _start[i];
}

2.3增

尾插：尾插实现逻辑与数据结构顺序表类似，判断是否扩容 -->在尾数据处插入数据x并使末指针++。然后这里为了和STL中一致，返回值设置为原对象的引用。代码如下：

void push_back(const T& x)
{//扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;
}

插入：插入这个地方模仿的是库中的insert接口，即在任意位置插入数据，这里先来看看库中给出接口

这里主要实现第一个类型接口：参数给出需要插入数据的位置和数据。插入步骤主要分为判断是否越界和是否需要扩容，挪动数据以及插入数据。具体代码如下：

iterator insert(const_iterator pos, const T& x)
{//判断assert(pos <= _finish);assert(pos >= _start);size_t len = pos - _start;if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : 2 * capacity());//更新pospos = _start + len;}//挪动数据iterator end = ++_finish;while (end != pos){*end = *(end - 1);--end;}
}

至于这里的迭代器返回值主要涉及迭代器失效问题，与下面删除的erase功能一起分析。

2.4删

库中给出的删除接口主要有尾删(pop_back)和任意位置删除(erase)。

尾删：尾删操作步骤主要可分为判断是否越界，删除数据两个步骤。代码如下：

	void pop_back(){//判断是否为空assert(_start != _finish);//删除数据--_finish;}

删除：删除操作(erase)步骤主要可分判断是否越界以及挪动数据。代码如下

iterator erase(iterator pos)
{assert(pos <= _finish);assert(pos >= _start);iterator it = pos + 1;while (it != _finish){*(it - 1) = *(it);++it;}--_finish;return pos;
}

这里依旧返回原位置迭代器，下面解释返回迭代器的原因。

2.5迭代器失效

先来看看下面的场景(在指定元素前插入数据)：

vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
print(v);auto it = find(v.begin(), v.end(), 3);
if(it != v.end())
{v.insert(it, 0);*it = 9;
}
print(v);

问：在insert后是it迭代器能赋值成功吗？

可以看到这里给it改值为9失败了。具体原因是在这里插入时进行了扩容，虽然函数内对pos进行了更新，但因为传值调用所有it是未更新的，因此导致迭代器失效。

下面再来看另一个失效场景(删除偶数) 

std::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
print(v);auto it = v.begin();
while (it != v.end())
{if (*it % 2 == 0){v.erase(it);}else{++it;}
}
print(v);

可以看到这里代码直接崩溃了，这里的原因是VS2022 Debug环境下对迭代器失效进行了仔细检查。

这里的解决方法就要提到之前的iterator返回值了，下面来看看删除偶数场景下的解决方案：

可以看到这里用it接受返回值后就可以成功运行了。

2.6拷贝构造级其他接口

拷贝构造这里主要可分为预留空间以及尾插操作。其他接口的话主要是实习clear以及resize接口：

vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr)
{reserve(v.capacity());for (auto e : v){push_back(e);}
}void resize(size_t n, T val = T())
{if (n > capacity()){reserve(n);for (size_t i = size(); i <= n; i++){push_back(val);}_finish = _start + n;}else{_finish = _start + n;}
}void clear()
{_finish = _start;
}

2.7赋值运算符重载(现代写法)

赋值运算符重载的现代写法主要是通过先通过tmp拷贝，在swap交换来实现，因此需要先实习vector中的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<T>& operator=(const vector<T>& v)
{vector<T> tmp = v;swap(tmp);return *this;
}

2.8深层次拷贝优化

深层级拷贝优化主要涉及vector容器内元素再开空间的问题，因为上面的reserve只进行了简单的memcpy，随后delete[]过程中会将元素申请的空间释放，解决方案就是利用赋值运算符重载中的深拷贝来进一步解决：

void reserve(size_t n)
{if (n > capacity()){size_t old_size = size();iterator tmp = new T[n];if (_start){for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + old_size;_end_of_storage = _start + n;}
}

3.整体代码

#include<assert.h>
#include<iostream>
#include<initializer_list>using namespace std;namespace my_vector
{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;}//vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}vector(initializer_list<T> il):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(il.size());for (auto& e : il){push_back(e);}}template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}//vector(int n, int val = 0)//{//	resize(n, val);//}vector(size_t n, T val = T()){resize(n, val);}vector(int n, T val = T()){resize(n, val);}//vector() = default;vector(const vector<T>& v):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){reserve(v.capacity());for (auto e : v){push_back(e);}}~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}void swap(vector<int>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}vector<T>& operator=(const vector<T>& v){vector<T> tmp = v;swap(tmp);return *this;}void reserve(size_t n){if (n > capacity()){size_t old_size = size();iterator tmp = new T[n];if (_start){for (size_t i = 0; i < old_size; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + old_size;_end_of_storage = _start + n;}}void resize(size_t n, T val = T()){if (n > capacity()){reserve(n);for (size_t i = size(); i <= n; i++){push_back(val);}_finish = _start + n;}else{_finish = _start + n;}}void push_back(const T& x){//扩容if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;++_finish;}iterator insert(const_iterator pos, const T& x){//判断assert(pos <= _finish);assert(pos >= _start);size_t len = pos - _start;if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : 2 * capacity());//更新pospos = _start + len;}//挪动数据iterator end = ++_finish;while (end != pos){*end = *(end - 1);--end;}*end = x;return end;}void pop_back(){//判断是否为空assert(_start != _finish);//删除数据--_finish;}iterator erase(iterator pos){assert(pos <= _finish);assert(pos >= _start);iterator it = pos + 1;while (it != _finish){*(it - 1) = *(it);++it;}--_finish;return pos;}void clear(){_finish = _start;}bool empty(){return _start == _finish;}T& operator[](size_t i){assert(i < size());return _start[i];}const T& operator[](size_t i) const{assert(i < size());return _start[i];}size_t size()const{return _finish - _start;}size_t capacity()const{return _end_of_storage - _start;}private://成员变量iterator _start;iterator _finish;iterator _end_of_storage;};
}

http://www.hkcw.cn/article/fgEZmwnosj.shtml

相关文章

day2实训

day2实训

实训任务1 FTPASS wireshark打开 实训任务2 数据包中的线索 解码的图片 实训任务3 被嗅探的流量 过滤http&#xff0c;追踪post的http流 实训任务6 小明的保险箱 winhex打开
阅读更多...
Window10+ 安装 go环境

Window10+ 安装 go环境

一、 下载 golang 源码&#xff1a; 去官网下载&#xff1a; https://go.dev/dl/ &#xff0c;当前时间&#xff08;2025-05&#xff09;最新版本如下: 二、 首先在指定的磁盘下创建几个文件夹 比如在 E盘创建 software 文件夹 E:\SoftWare,然后在创建如下几个文件夹 E:\S…
阅读更多...
8.5 Q1|广州医科大学CHARLS发文 甘油三酯葡萄糖指数累积变化与 0-3期心血管-肾脏-代谢综合征人群中风发生率的相关性

8.5 Q1|广州医科大学CHARLS发文 甘油三酯葡萄糖指数累积变化与 0-3期心血管-肾脏-代谢综合征人群中风发生率的相关性

1.第一段-文章基本信息 文章题目&#xff1a;Association between cumulative changes of the triglyceride glucose index and incidence of stroke in a population with cardiovascular-kidney-metabolic syndrome stage 0-3: a nationwide prospective cohort study 中文标…
阅读更多...
重读《人件》Peopleware -（13）Ⅱ 办公环境 Ⅵ 电话

重读《人件》Peopleware -（13）Ⅱ 办公环境 Ⅵ 电话

当你开始收集有关工作时间质量的数据时&#xff0c;你的注意力自然会集中在主要的干扰源之一——打进来的电话。一天内接15个电话并不罕见。虽然这看似平常&#xff0c;但由于重新沉浸所需的时间&#xff0c;它可能会耗尽你几乎一整天的时间。当一天结束时&#xff0c;你会纳闷…
阅读更多...
ARXML解析与可视化工具

ARXML解析与可视化工具

随着汽车电子行业的快速发展，AUTOSAR标准在车辆软件架构中发挥着越来越重要的作用。然而，传统的ARXML文件处理工具往往存在高昂的许可费用、封闭的数据格式和复杂的使用门槛等问题。本文介绍一种基于TXT格式输出的ARXML解析方案，为开发团队提供了一个高效的替代解决方案。 …
阅读更多...
C#中数据绑定的简单例子

C#中数据绑定的简单例子

数据绑定允许将控件的属性和数据链接起来——控件属性值发生改变&#xff0c;会导致数据跟着自动改变。 数据绑定还可以是双向的——控件属性值发生改变&#xff0c;会导致数据跟着自动改变&#xff1b;数据发生改变&#xff0c;也会导致控件属性值跟着自动改变。 1、数据绑定…
阅读更多...
训练和测试的规范写法

训练和测试的规范写法

单通道图片的规范写法 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.pyplot as plt import numpy as np# 设置中文字体支持 plt.rcParams[&quo…
阅读更多...
【Web应用】若依框架：基础篇12 项目结构

【Web应用】若依框架：基础篇12 项目结构

文章目录 ⭐前言⭐一、课程讲解&#x1f31f;1、寻找合适的对象✨1) ⭐二、怎样选择设计模式&#xff1f;&#x1f31f;1、寻找合适的对象✨1) ⭐三、怎样使用设计模式&#xff1f;&#x1f31f;1、寻找合适的对象✨1) ⭐总结 标题详情作者JosieBook头衔CSDN博客专家资格、阿里…
阅读更多...
系统设计——状态机模型设计经验

系统设计——状态机模型设计经验

摘要 本文主要介绍了状态机模型的设计经验&#xff0c;包括其定义、适用场景、建模示例、事件驱动设计以及配置数据化等内容。状态机模型通过事件驱动控制状态变化&#xff0c;适用于流程驱动系统、生命周期管理等场景&#xff0c;不适用于状态变化简单或不确定的场景。文中还…
阅读更多...
WSP 对CSV文件中E+如何恢复可用方案

WSP 对CSV文件中E+如何恢复可用方案

背景 在日常工作中会遇到从系统软件中导出的csv文件&#xff0c;其中长的字符会被自动科学计数&#xff0c;转成E&#xff0c;导致数据失去原来的信息。 样例 从系统中导出的用户表&#xff0c;其中【mobile】和【serial_no】两列的数据被转化为E&#xff0c;失去原始的信息…
阅读更多...
突破知识传统依赖：模型内在推理能力评估的基准测试集 KOR-Bench

突破知识传统依赖：模型内在推理能力评估的基准测试集 KOR-Bench

项目主页&#xff1a;https://kor-bench.github.io/ GitHub: https://github.com/multimodal-art-projection/KOR-BENCH 论文&#xff1a;https://arxiv.org/abs/2410.06526 随着人工智能技术的迅猛发展&#xff0c;大模型评估已成为AI领域的关键议题。在前序文章中&#xf…
阅读更多...
ReactHook有哪些

ReactHook有哪些

React 中常用的 Hooks 列表及用法 React Hooks 是 React 16.8 版本引入的一项重要特性&#xff0c;它极大地简化和优化了函数组件的开发过程。以下是 React 中常用的 Hooks 列表及其详细用法&#xff1a; 1. useState useState 是用于在函数组件中添加状态的 Hook。通过调用…
阅读更多...
移动端上拉 下拉 初始状态解决方案

移动端上拉 下拉 初始状态解决方案

引入第三方组件嵌套 手机端 将页面分为两部分&#xff1a; top顶部标题 例如search输入mescrollvue 组件嵌套 里面使用for 循环 初始状态下有三个状态的回调函数 分别是down up init 三个 分别对应下拉 上拉 初始状态触发
阅读更多...
DMNDDB INSTALL新云文档数据库安装部署

DMNDDB INSTALL新云文档数据库安装部署

DMNDDB INSTALL新云文档数据库安装部署 1 环境说明2 优化root用户限制3 准备安装包3.1 部署安装包3.2 安装目录介绍3.2.1 默认目录安装路径bin3.2.2 默认目录安装路径conf3.2.3 默认目录安装路径doc3.2.4 默认目录安装路径 thirdparty3.2.5 默认目录安装路径 tools 4 一键安装4…
阅读更多...
深入剖析 DMA：原理、结构与工作流程详解

深入剖析 DMA：原理、结构与工作流程详解

文章目录 DMADMA简介存储器映像DMA框图DMA基本结构DMA请求数据宽度与对齐数据转运DMA变量与常量实验外设寄存器访问DMA 配置与编程思路DMA 代码实现与测试DMA模块主要代码 DMA DMA简介 DMA 简介 功能与权限&#xff1a;英文全称 direct memory access&#xff0c;可直接访问…
阅读更多...
从公开到私密：重新思考 Web3 的数据安全

从公开到私密：重新思考 Web3 的数据安全

去中心化存储是 Web3 的基石之一&#xff0c;使用户和应用能够在无需依赖中心化服务商的情况下存储数据。但自由也带来了一个重大挑战&#xff1a;数据安全。在一个无许可的世界中&#xff0c;如何确保用户文档、游戏资产或 AI 数据集等敏感内容是私密的、可控访问的&#xff0…
阅读更多...
xilinx位置约束

xilinx位置约束

xilinx位置约束 1.set_property LOC XXX XXX 参考&#xff1a;https://blog.csdn.net/Calvin790704/article/details/132980316 参考&#xff1a;https://blog.csdn.net/u011329967/article/details/124466598 pcie bank参考&#xff1a;Xilinx PCIE core管脚分配错误的解决方案…
阅读更多...
亚马逊商品评论爬取与情感分析：Python+BeautifulSoup实战（含防封策略）

亚马逊商品评论爬取与情感分析：Python+BeautifulSoup实战（含防封策略）

一、数据爬取模块&#xff08;Python示例&#xff09; import requests from bs4 import BeautifulSoup import pandas as pd import timeheaders {User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36,Accept-Language: en-US }def scrape_amazon_re…
阅读更多...
uniapp使用Canvas生成电子名片

uniapp使用Canvas生成电子名片

uniapp使用Canvas生成电子名片 工作中有生成电子名片的一个需求&#xff0c;刚刚好弄了发一下分享分享 文章目录 uniapp使用Canvas生成电子名片前言一、上代码&#xff1f;总结 前言 先看效果 一、上代码&#xff1f; 不对不对应该是上才艺&#xff0c;哈哈哈 <template…
阅读更多...
量化qmt跟单聚宽小市值策略开发成功

量化qmt跟单聚宽小市值策略开发成功

现在分享下一位朋友实盘对接的账户交易信息&#xff0c;给大家看下资金曲线收益&#xff0c;还有聚宽回测曲线&#xff0c;对比图。 哈哈哈&#xff0c;5月份10w小资金&#xff0c;获利2.9点&#xff0c;非常高&#xff0c;刚刚开始&#xff0c;还是可以的。
阅读更多...
推荐文章

Copyright @ 2022~2023