当前位置： 首页 > article >正文

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

article 2025/3/10 9:47:05

文章目录

  • 前言
  • 一、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返回的新迭代器

http://www.kler.cn/a/578400.html

相关文章：

  • CEF 入门
  • 第6届传智杯复赛第一场
  • leetcode day27 455+376
  • EasyRTC嵌入式视频通话SDK的跨平台适配，构建web浏览器、Linux、ARM、安卓等终端的低延迟音视频通信
  • 20250307确认荣品PRO-RK3566开发板在Android13下的以太网络共享功能
  • 蓝桥杯 字符串拼接【省模拟赛】
  • 信息系统运行管理员教程9--大型网站运维
  • fastapi房产销售系统
  • langChainv0.3学习笔记（初级篇）
  • 入门到入土，Java学习day15（常用API下）
  • 【BAT紧急调整战略：解码深度求索的生态圈打法】
  • el-table（elementui）表格合计行使用以及滚动条默认样式修改
  • Pycharm 取消拼写错误检查（Typo：in word xxx）
  • QGIS制作流向图的完整指南
  • 基于深度文档理解的开源 RAG 引擎RAGFlow的介绍和安装
  • 根据指定 Excel 模板将 Excel 明细数据生成新的 Excel 文档
  • 大模型工程师学习日记(十六):Bert-base-chinese模型基于微博数据集进行增量微调训练
  • 【C语言】自定义类型：结构体，联合，枚举(上)
  • 北京大学DeepSeek内部研讨系列第4讲：DeepSeek原理与落地应用》｜57页（文末附链接下载）
  • 进程（上）【Linux操作系统】