【C++】vector(下)：vector类的模拟实现（含迭代器失效问题）

文章目录

  • 前言
  • 一、vector类的常用接口的模拟实现
    • 1.头文件（my vector.h）整体框架
    • 2.模拟实现vector类对象的常见构造
    • 3.模拟实现vector iterator
    • 4.模拟实现vector类对象的容量操作
    • 5.模拟实现vector类对象的访问
    • 6.模拟实现vector类对象的修改操作
  • 二、vector 迭代器失效问题

前言

vector类的常用接口的模拟实现 以及 vector 迭代器失效问题。配套博客: 【C++】vector(上)：vector的常用接口介绍

一、vector类的常用接口的模拟实现

1.头文件（my vector.h）整体框架

#include <algorithm>
#include <assert.h>
namespace zh
{
    template<class T>
    class vector
    {
    public:
        // Vector的迭代器可以直接用指针封装
        typedef T* iterator;
        typedef const T* const_iterator;

        // construct and destroy //
        vector();
        vector(int n, const T& value = T());

        template<class InputIterator>
        vector(InputIterator first, InputIterator last);

        vector(const vector<T>& v);

        vector<T>& operator= (vector<T> v); // 赋值运算符重载
        ~vector(); // 析构函数

        // iterator //
        iterator begin();
        iterator end();
        const_iterator begin() const;
        const_iterator end() const;

        // capacity //
        size_t size() const;
        size_t capacity() const;
        void reserve(size_t n);
        void resize(size_t n, const T& value = T());

        // access //
        T& operator[](size_t pos);
        const T& operator[](size_t pos)const;

        // modify //
        void push_back(const T& x);
        void pop_back();
        iterator insert(iterator pos, const T& x);
        iterator erase(iterator pos);
        void swap(vector<T>& v);
    private:
        iterator _start = nullptr; // 指向有效数据的开始
        iterator _finish = nullptr; // 指向有效数据的尾部
        iterator _end_storage = nullptr; // 指向存储容量的尾部
    };
}

2.模拟实现vector类对象的常见构造

template<class T>
class vector
{
public:
    vector() // 默认构造函数
    {}

    vector(int n, const T& value = T()) // 构造并初始化n个val
    {
        _start = new T[n];
        _finish = _end_storage = _start + n;
        while (n--)
        {
            _start[n] = value;
        }
    }

    template<class InputIterator>
    vector(InputIterator first, InputIterator last) // 使用迭代器进行初始化构造
    {
        auto it = first;
        while (it != last)
        {
            push_back(*it++);
        }
    }

    vector(const vector<T>& v) // 拷贝构造
    {
        if (v._start != nullptr)
        {
            _start = new T[v.capacity()];
            _finish = _start + v.size();
            _end_storage = _start + v.capacity();
            auto it1 = begin();
            auto it2 = v.begin();
            while (it2 != v.end())
            {
                *it1++ = *it2++;
            }
        }
    }

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

    ~vector() // 析构函数
    {
        if (_start != nullptr)
        {
            delete[] _start;
            _start = _finish = _end_storage = nullptr;
        }
    }
private:
    iterator _start = nullptr; // 指向有效数据的开始
    iterator _finish = nullptr; // 指向有效数据的尾部
    iterator _end_storage = nullptr; // 指向存储容量的尾部
};

3.模拟实现vector iterator

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;
    }
private:
    iterator _start = nullptr; // 指向有效数据的开始
    iterator _finish = nullptr; // 指向有效数据的尾部
    iterator _end_storage = nullptr; // 指向存储容量的尾部
};

4.模拟实现vector类对象的容量操作

template<class T>
class vector
{
public:
    size_t size() const
    {
        return _finish - _start;
    }

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

    void reserve(size_t n)
    {
        if (n > capacity())
        {
            iterator tmp = new T[n];
            auto it = _start;
            int i = 0;
            while (it != _finish)
            {
                tmp[i++] = *it;
                it++;
            }
            delete[] _start;
            _start = tmp;
            _finish = tmp + i;
            _end_storage = tmp + n;
        }
    }

    void resize(size_t n, const T& value = T())
    {
        if (n <= size())
        {
            _finish -= size() - n;
        }
        else
        {
            if (n > capacity())
            {
                size_t newcap = 2 * capacity();
                if (n > newcap)
                    newcap = n;
                reserve(newcap);
            }
            size_t i = size();
            _finish += n - size();
            while (i < size())
            {
                _start[i++] = value;
            }
        }
    }
private:
    iterator _start = nullptr; // 指向有效数据的开始
    iterator _finish = nullptr; // 指向有效数据的尾部
    iterator _end_storage = nullptr; // 指向存储容量的尾部
};

5.模拟实现vector类对象的访问

template<class T>
class vector
{
public:
    T& operator[](size_t pos)
    {
        assert(pos < size());
        return _start[pos];
    }

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

private:
    iterator _start = nullptr; // 指向有效数据的开始
    iterator _finish = nullptr; // 指向有效数据的尾部
    iterator _end_storage = nullptr; // 指向存储容量的尾部
};

6.模拟实现vector类对象的修改操作

template<class T>
class vector
{
public:
    void push_back(const T& x) // 在末尾插入一个元素
    {
        if (size() == capacity())
        {
            size_t n = capacity() == 0 ? 4 : 2 * capacity();
            reserve(n);
        }
        _start[size()] = x;
        _finish++;
    }

    void pop_back() // 删除末尾元素
    {
        assert(size() > 0);
        _finish--;
    }

    iterator insert(iterator pos, const T& x) // 在迭代器 pos 位置插入元素 x
    {
        assert(pos >= _start && pos <= _finish);
        if (size() == capacity())
        {
            size_t newcap = capacity() == 0 ? 4 : 2 * capacity();
            size_t n = pos - _start;
            reserve(newcap);
            pos = _start + n;
        }
        auto it = _finish;
        while (pos < it)
        {
            *it = *(it - 1);
            it--;
        }
        *pos = x;
        _finish++;
        return pos;
    }

    iterator erase(iterator pos) // 删除迭代器 pos 指向的元素
    {
        assert(pos >= _start && pos < _finish);
        auto it = pos;
        while (it < _finish - 1)
        {
            *it = *(it + 1);
            it++;
        }
        _finish--;
        return pos;
    }

    void swap(vector<T>& v) // 交换两个vector对象的内容
    {
        std::swap(_start, v._start);
        std::swap(_finish, v._finish);
        std::swap(_end_storage, v._end_storage);
    }
private:
    iterator _start = nullptr; // 指向有效数据的开始
    iterator _finish = nullptr; // 指向有效数据的尾部
    iterator _end_storage = nullptr; // 指向存储容量的尾部
};

二、vector 迭代器失效问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就可以使用原生态指针T* 。因此迭代器失效，实际是指 vector 进行某些修改操作后，原有的迭代器（或指针、引用）指向的内存地址可能变得无效，继续使用这些迭代器会导致未定义行为（如程序崩溃、数据错误）。 比如：迭代器底层对应指针所指向的空间被销毁了（扩容等行为导致底层空间改变），而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。

对于vector可能会导致其迭代器失效的操作有：

  1. 会引起其底层空间改变的操作（插入、赋值 和 修改容量），都有可能会导致迭代器失效，比如：resize、push_back、insert、assign 和 reserve等。
#include <iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v{ 1,2,3,4,5,6 }; // 由调试结果（下图）可知:size == capacity = 6
	auto it = v.begin();
	
	// 头插一个元素，因为size == capacity，所以该操作会引起扩容
	v.insert(v.begin(), 0);
	
	// resize的作用是增加有效元素个数,操作期间可能会引起扩容
	// v.resize(50, 8);
	// reserve的作用是扩充容量但不改变有效元素个数，操作期间可能会引起扩容
	// v.reserve(50);
	// 插入元素期间，可能会引起扩容，而导致原空间被释放
	// v.push_back(8);
	// 给vector重新赋值，可能会引起扩容
	// v.assign(50, 8);

	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	} 
	cout << endl;
	return 0;
}

在这里插入图片描述
在这里插入图片描述
出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的空间，而引起代码运行时崩溃。

解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新赋值即可。
如下：

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v{ 1,2,3,4,5,6 };
	auto it = v.begin();
	
	// insert的返回值：若插入单个元素，返回值指向新插入的该元素;
	//                若插入多个元素或区间，则指向第一个新插入的元素。
	it = v.insert(v.begin(), 0);
	// 即使插入导致内存重新分配，返回的迭代器仍有效（直接指向新内存位置）。

	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	} 
	cout << endl;
	return 0;
}

在这里插入图片描述

  1. 指定位置元素的删除操作（erase）

示例一（erase删除元素后，被删除位置之后的迭代器失效（元素前移））：

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	vector<int> v = { 10, 20, 30, 40 };
	auto it = v.begin(); // 指向10
	auto it1 = v.begin() + 1;  // 指向20
	auto it2 = v.begin() + 2;  // 指向30

	v.erase(it1);  // 删除20，vector变为{10,30,40}

	cout << *it2; // 删除元素后，被删除位置之后的迭代器失效（元素前移）
	return 0;
}

在这里插入图片描述

示例二（删除元素后，被删除位置的迭代器也失效（元素前移））：

int main()
{
	vector<int> v = { 10, 20, 30, 40 };
	auto it = v.begin(); // 指向10
	auto it1 = v.begin() + 1;  // 指向20
	auto it2 = v.begin() + 2;  // 指向30

	v.erase(it1);  // 删除20，vector变为{10,30,40}

	cout << *it1; // 删除元素后，被删除位置的迭代器也失效（元素前移）
	return 0;
}

在这里插入图片描述
解决方式：在以上操作完成之后，如果想要继续通过迭代器it1操作vector中的元素，只需给it1重新赋值即可，如下：

int main()
{
	vector<int> v = { 10, 20, 30, 40 };
	auto it = v.begin(); // 指向10
	auto it1 = v.begin() + 1;  // 指向20
	auto it2 = v.begin() + 2;  // 指向30
    
    // erase的返回值是指向被删除元素之后第一个有效元素的迭代器
    // 删除元素后，被删元素及其之后的所有迭代器都会失效，但返回值是新的有效迭代器
	it1 = v.erase(it1);  // 删除20，vector变为{10,30,40}

	cout << *it1;
	return 0;
}

在这里插入图片描述

示例三（删除元素后，被删除位置之前的迭代器能正常使用）：

int main()
{
	vector<int> v = { 10, 20, 30, 40 };
	auto it = v.begin(); // 指向10
	auto it1 = v.begin() + 1;  // 指向20
	auto it2 = v.begin() + 2;  // 指向30

	v.erase(it1);  // 删除20，vector变为{10,30,40}

	cout << *it; // 删除元素后，被删除位置之前的迭代器能正常使用
	return 0;
}

在这里插入图片描述

一、导致迭代器失效的典型场景总结

  1. 插入元素(push_back, insert和resize等)

    • 当插入导致vector容量不足时，会重新分配内存，所有迭代器、指针、引用都会失效。
    • 即使容量足够，插入位置及其之后的迭代器也会失效（元素被后移）。

  2. 扩充容量(reserve等) 和 重新赋值(assign等)

    • 任何导致内存重新分配的操作都会使所有迭代器失效。

  3. 删除元素(erase, pop_back等)

    • 被删除元素及其之后的所有迭代器、指针、引用会失效（元素前移）
    • 被删除元素之前的迭代器、指针、引用仍然保持有效

二、如何减少迭代器失效？

  1. 插入/删除后更新迭代器
    • erase和insert会返回新的有效迭代器：
vector<int> v{ 1,2,3,4,5,6 }; 	
auto it = v.begin(); 	
it = v.insert(v.begin(), 0); // 使用返回的新迭代器 	
it = v.erase(it); // 使用返回的新迭代器
  1. 预留足够容量
    • 使用reserve()预先分配足够内存，减少重新分配次数：
std::vector<int> v;    
v.reserve(100);  // 预分配足够内存空间
  1. 避免保存旧迭代器
    • 修改操作后，不要继续使用旧的迭代器、指针或引用。

总结表格

操作类型失效范围解决方案
插入导致扩容所有迭代器重新获取所有迭代器
插入未扩容插入位置及其之后的迭代器更新插入位置后的迭代器
用reserve扩容 和 用assign重新赋值所有迭代器重新获取所有迭代器
删除元素被删位置及其之后的迭代器使用erase返回的新迭代器

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/983962.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

抽奖系统测试报告

抽奖系统测试报告

项目链接: 管理员登录页面 项目功能: 管理员登录: 登录方式分为两种: 手机号密码登录: 正确输入密码和手机号登录 短信验证码登录: 输入手机号,等待验证码,输入验证码登录 管理员注册: 登录页面点击注册按钮即可注册管理员身份 人员管理模块: 人员管理模块分为注册…
阅读更多...
理解梯度下降、链式法则、梯度消失/爆炸

理解梯度下降、链式法则、梯度消失/爆炸

第一章&#xff1a;人工智能之不同数据类型及其特点梳理 第二章&#xff1a;自然语言处理(NLP)&#xff1a;文本向量化从文字到数字的原理 第三章&#xff1a;循环神经网络RNN&#xff1a;理解 RNN的工作机制与应用场景(附代码) 第四章&#xff1a;循环神经网络RNN、LSTM以及GR…
阅读更多...
从零开始用react + tailwindcss + express + mongodb实现一个聊天程序(十一) 实现服务端和客户端socketio 连接

从零开始用react + tailwindcss + express + mongodb实现一个聊天程序(十一) 实现服务端和客户端socketio 连接

1.后端部分 socketIO文档参考Socket.IO 首先在lib下新建socket.js文件 参考服务器API | Socket.IO import {Server} from socket.io; import http from http import express from "express"const app express() const server http.createServer(app) const io …
阅读更多...
Spring Boot使用JDBC /JPA访问达梦数据库

Spring Boot使用JDBC /JPA访问达梦数据库

Spring Boot 是一个广泛使用的 Java 框架&#xff0c;用于快速构建基于 Spring 的应用程序。对于达梦数据库&#xff08;DMDB&#xff09;的支持&#xff0c;Spring Boot 本身并没有直接内置对达梦数据库的集成&#xff0c;但你可以通过一些配置和依赖来支持达梦数据库。 以下…
阅读更多...
蓝桥杯嵌入式学习日记（三）——按键的长按、短按与双击（三行按键法）【STM32】【HAL库】

蓝桥杯嵌入式学习日记（三）——按键的长按、短按与双击（三行按键法）【STM32】【HAL库】

目录 一、查阅相关资料二、程序的编写1、创建工程2、三行按键法3、短按与长按4、双击 一、查阅相关资料 想要进行一块板子的开发&#xff0c;需要先查阅资料了解器件连接。   从CT117E-M4产品手册中不难发现&#xff0c;按键分别有PB0、PB1、PB2、PA0分别对应B1、B2、B3、B4…
阅读更多...
【网络安全 | 漏洞挖掘】通过JWT的IDOR实现账户接管

【网络安全 | 漏洞挖掘】通过JWT的IDOR实现账户接管

未经许可，不得转载。 文章目录 正文正文 在审查目标平台“redirect.com”的Web应用时，我发现它使用了JSON Web Token（JWT）进行身份验证，因此决定尝试进行账户接管（ATO）攻击。 首先，我创建了一个新账户并测试了其功能。在此过程中，我尝试在“firstName”字段输入XSS（…
阅读更多...
从0到1入门RabbitMQ

从0到1入门RabbitMQ

一、同步调用 优势&#xff1a;时效性强&#xff0c;等待到结果后才返回 缺点&#xff1a; 拓展性差性能下降级联失败问题 二、异步调用 优势&#xff1a; 耦合度低&#xff0c;拓展性强异步调用&#xff0c;无需等待&#xff0c;性能好故障隔离&#xff0c;下游服务故障不影响…
阅读更多...
CST直角反射器 --- 距离多普勒（RD图）, 毫米波汽车雷达ADAS

CST直角反射器 --- 距离多普勒（RD图）, 毫米波汽车雷达ADAS

之前几期介绍了雷达是如何从频域换去时域&#xff0c;然后时域计算距离。 这期我们加上一个维度&#xff0c;既看距离&#xff0c;又看速度。速度的计算当然就是多普勒原理&#xff0c;所以距离速度的二维图又叫range-doppler图。 启用雷达ADAS Range-Doppler模板&#xff1a…
阅读更多...
手写一个Tomcat

手写一个Tomcat

Tomcat 是一个广泛使用的开源 Java Servlet 容器&#xff0c;用于运行 Java Web 应用程序。虽然 Tomcat 本身功能强大且复杂&#xff0c;但通过手写一个简易版的 Tomcat&#xff0c;我们可以更好地理解其核心工作原理。本文将带你一步步实现一个简易版的 Tomcat&#xff0c;并深…
阅读更多...
【从零开始学习计算机科学】计算机组成原理（六）异常事件处理

【从零开始学习计算机科学】计算机组成原理（六）异常事件处理

【从零开始学习计算机科学】计算机组成原理&#xff08;六&#xff09;异常事件处理 异常事件处理异常处理的数据通路异常事件入口地址 异常事件处理 异常和中断事件改变处理机正常指令的执行顺序。异常指令执行过程中&#xff0c;由于操作非法和指令非法引起的事件。陷阱指陷…
阅读更多...
3.3.2 Proteus第一个仿真图

3.3.2 Proteus第一个仿真图

文章目录 文章介绍0 效果图1 新建“点灯”项目2 添加元器件3 元器件布局接线4 补充 文章介绍 本文介绍&#xff1a;使用Proteus仿真软件画第一个仿真图 0 效果图 1 新建“点灯”项目 修改项目名称和路径&#xff0c;之后一直点“下一步”直到完成 2 添加元器件 点击元…
阅读更多...
高效运行 QwQ-32B + 错误修复

高效运行 QwQ-32B + 错误修复

文章目录 QwQ-32B 错误修复⚙️ 官方推荐设置&#x1f44d; 推荐的 llama.cpp 设置&#x1f4d6; 教程&#xff1a;运行和修复的 QwQ-32B1、对于 llama.cpp 及使用 llama.cpp 的引擎&#xff1a;2、下载模型 测试3、测试/评估4、尝试不使用我们的修复方案&#xff1a; &#x…
阅读更多...
R 语言科研绘图 --- 直方图-汇总

R 语言科研绘图 --- 直方图-汇总

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…
阅读更多...
1.5.1 掌握Scala内建控制结构 - 条件表达式

1.5.1 掌握Scala内建控制结构 - 条件表达式

本文介绍了 Scala 中条件表达式的使用及其在实际任务中的应用。条件表达式的语法为 if (条件) 值1 else 值2&#xff0c;其结果类型取决于值1和值2的类型。如果类型相同&#xff0c;结果类型与它们相同&#xff1b;如果不同&#xff0c;则结果类型为 Any。通过两个任务展示了条…
阅读更多...
Linux rootfs：如何开机就自动添加某个用户？

Linux rootfs：如何开机就自动添加某个用户？

前言 项目开发需求&#xff0c;需要开机后就自动创建某个用户密码 厂家提供的sdk&#xff0c;只有adduser命令&#xff0c; 该命令添加用户时&#xff0c;会有终端交互&#xff0c; 需要手动输入2次密码&#xff0c; 所以无法通过简单脚本方式创建。 要实现自动填充密码&…
阅读更多...
计算机三级网络技术知识点汇总【7】

计算机三级网络技术知识点汇总【7】

第七章 路由器配置及使用 1. 路由器的基础知识 1.1 路由器的基本概念 路由器是工作在网络层的设备&#xff0c;负责将数据分组从源端主机经最佳路径传送到目的端主机&#xff0c;实现在网络层的互联。路由器工作在 TCP/IP 网络模型的网络层&#xff0c;对应于 OSI 网络参考模…
阅读更多...
Compounding Geometric Operations for Knowledge Graph Completion（论文笔记）

Compounding Geometric Operations for Knowledge Graph Completion（论文笔记）

CCF等级&#xff1a;A 发布时间&#xff1a;2023年7月 25年3月10日交 一、简介 使用知识图谱嵌入模型&#xff0c;将三元组&#xff08;h,r,t&#xff09;中关系 r 转化为平移、旋转、缩放矩阵对头节点以及尾节点进行运算&#xff0c;判定三元组的真实性。 二、原理 1.整…
阅读更多...
mac系统安装

mac系统安装

目录 准备工作 一、安装虚拟机 二、解锁系统 三、安装系统 四、部署系统 五、安装VMware Tools(选做) 为什么要安装VMware Tools，这是啥玩意？ 六、配置共享文件夹(选做) 为什么要共享文件夹？ 注意事项： 七、安装完成 准备工作 一、安装说明： 本教程分为7个部…
阅读更多...
DNASimCLR：一种基于对比学习的基因序列数据分类的深度学习方法

DNASimCLR：一种基于对比学习的基因序列数据分类的深度学习方法

摘要 DNASimCLR利用卷积神经网络和基于对比学习的SimCLR框架&#xff0c;从不同的微生物基因序列中提取复杂的特征。在包含宏基因组和病毒基因序列的两个经典的大规模未标记数据集上进行了预训练。后续的分类任务通过使用先前获得的模型对预训练的模型进行微调来完成。我们的实…
阅读更多...
Ae 效果详解：VR 旋转球面

Ae 效果详解：VR 旋转球面

Ae菜单&#xff1a;效果/沉浸式视频/VR 旋转球面 Immersive Video/VR Rotate Sphere VR 旋转球面 VR Rotate Sphere效果用于对 VR 视频进行三轴旋转&#xff0c;以调整视频的视角方向。可用于校正拍摄时的角度偏差&#xff0c;或者根据创意需求模拟摄像机旋转。 本效果适用于所…
阅读更多...
最新文章

Copyright @ 2022~2023