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

C++学习之STL学习：vector的模拟实现

news 2025/6/28 14:31:15

        上节课我们已经接触并学习了vector的使用。接下来我们将通过模拟实现的方式深入学习vector的底层，更好的了解学习vector

vector模拟实现前置准备

vector.h：将类、函数的声明与定义放在一起   

test.cpp：函数的测试

为什么vectror.h要将类和函数的声明与定义放在一起而不是再创建一个.cpp文件呢？

        因为本篇中vector的模拟实现要用到模板，而模板的声明与定义不能放在两个文件里，否则就会编译链接错误（原因后面深入模板学习进行讲解）

        首先抓类的成员变量，然后看构造的初始化，再看核心的成员函数（项目中有很多细节的成员函数）

命名空间的设置

        为了解决与库中vector 使用冲突的问题，我们需要一个命名空间将其封装起来 

namespace Boogiepop
{}

vector的构造

vector 的模拟实现中，我们需要用到模板

template<class T>

     而用到模板的情况下，声明与定义是不能分离的

        成员变量

private:iterator _start;//第一个元素的指针iterator _finish;//最后一个元素的指针iterator _end_of_storage;//分配的内存的最后一个元素的指针

        构造

namespace Boogiepop
{//声明与定义不能分别定义在两个文件template<class T>class vector{public:typedef T* iterator;vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}private:iterator _start;//第一个元素的指针iterator _finish;//最后一个元素的指针iterator _end_of_storage;//分配的内存的最后一个元素的指针};
}

        拷贝构造

//拷贝构造函数
vector(const vector<T>&v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{reserve(v.capacity());for (auto e : v){push_back(e);}
}

        析构

//析构函数
~vector()
{if (_start!= nullptr){delete[]_start;_start = nullptr;_finish = nullptr;_end_of_storage = nullptr;}
}

        强制编辑器构造 

//强制编辑器生成构造
vector()=defalut;

        多个值初始化

花括号对多个数值初始化

//列表初始化构造
vector(initializer_list<T> il)
{reserve(il.size());for (auto& e : il){push_back(e);}
}

        函数模板初始化 

//函数模板初始化
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{reserve(last - first);for (InputIterator it = first; it!= last; ++it){push_back(*it);}
}

vector的成员函数

        尾插数据

        尾插数据的时候需要考虑内存分配的空间已经满了。因此我们需要判断是否已经满了并进行扩容

        在此之前我们需要一个更方便的表达方式，类似于string

//返回一个向量有效元素的个数
size_t size() const
{return _finish - _start;
}
//返回一个向量分配内存中元素的个数
size_t capacity() const
{return _end_of_storage - _start;
}

扩容函数

//扩容
void reserve(size_t n)
{size_t old_size = size();if (n>capacity()){T*tmp=new T[n];//拷贝旧空间数据if (_start!= nullptr){memcpy(tmp,_start,sizeof(T)*size());delete[]_start;}_start = tmp;_finish = _start + old_size;_end_of_storage = _start + n;}
}

因此最后尾插数据是这样的

//尾插数据
void push_back(const T& val)
{if (_finish == _end_of_storage)//空间满了，需要扩容{resverse(capacity() == 0? 4 : 2 * capacity());}*_finish = val;++_finish;
}

[]遍历

//[]运算符重载
T&operator[](size_t i)
{assert(i<size());return _start[i];
}

迭代器

typedef T* iterator;
typedef const T* const_iterator;
//迭代器
iterator begin()
{return _start;
}
iterator end()
{return _finish;
}
//const迭代器
//const不是自身不能修改，而是指向的内容不能修改
const_iterator begin() const
{return _start;
}
const_iterator end() const
{return _finish;
}

测试：

​void test1()
{Boogiepop::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//范围for本质上就是迭代器for (auto e : v){std::cout<<e<<" ";}std::cout<<std::endl;
}​

尾部删除

判定为空函数

//判断为空
bool empty() const
{return _finish == _start;
}

完整版

//判断为空
bool empty() const
{return _finish == _start;
}
//尾部删除
void pop_back()
{/*assert(_finish > _start);*/assert(!empty());--finish;
}

insert插入

//插入
void insert(iterator pos, const T& val)
{assert(pos>=_start && pos<=_finish);if (_finish == _end_of_storage){size_t len =pos-start();reserve(capacity() == 0 ? 4 : 2 * capacity());}//移动后面的元素iterator end = _finish - 1;while (end >= pos){*(end + 1)=*end;--end;}*pos = val;++_finish;
}

        以上代码有问题，会出现迭代器失效的问题

        插入就会导致扩容，而扩容会导致迭代器失效问题

         

        如下图所示 ，异地扩容的时候，旧有的空间被销毁，导致指向旧空间的指针指向的内容消失，变成了野指针，因此导致了迭代器失效

        因此要更新pos的位置

//插入
void insert(iterator pos, const T& val)
{assert(pos>=_start && pos<=_finish);if (_finish == _end_of_storage){size_t len =pos-start();reserve(capacity() == 0 ? 4 : 2 * capacity());//更新pos，pos失效了pos = _start + len;}//移动后面的元素iterator end = _finish - 1;while (end >= pos){*(end + 1)=*end;--end;}*pos = val;++_finish;
}

 再举一个例子

void test4()
{Boogiepop::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);print(v);int x;std::cin >> x;auto it = std::find(v.begin(), v.end(), x);if(it!= v.end()){//迭代器失效v.insert(it,x*10);//C++扩容没有具体固定vector的扩容规则//我们认为扩容后it就失效了，所以不能使用it//it不能继续使用，已经失效了*it = 10;//要更新迭代器位置}print(v);
}

结果为：

 

删除

//删除
void erase(iterator pos)
{assert(pos>=_start && pos<=_finish);iterator it = pos + 1;while (it !=_finish){*(it - 1) = *(it);++it;}--_finish;
}

test.c

void test6()
{std::vector<int> v;//Boogiepop::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);v.push_back(7);v.push_back(8);print(v);//删除所有的偶数auto it = v.begin();while (it != v.end()){if (*it % 2 == 0){//erase迭代器也会失效//要重新赋新值才可以it=v.erase(it);}else{++it;}}print(v);
}

 resize

//修改大小
void resize(size_t n,T val=T ())
{//匿名对象的使用场景if (n>size()){reserve(n);while (_finish!=_start+n){*_finish = val;++_finish;}}else{_finish = _start + n;}
}

迭代器失效 

底层就是野指针

C++迭代器失效详解

一、底层原理

迭代器是容器元素的抽象指针，其底层实现与容器内存结构紧密相关：

  1. 连续内存容器（vector/string/deque）

    • 迭代器本质是原始指针（或封装指针的类）

    • 内存重新分配时，原内存块被释放，迭代器成为悬垂指针

vector<int> v{1,2,3};
int* p = &v[0];  // 原始指针实现
v.push_back(4);  // 可能导致内存重分配
// p 可能指向已释放内存

        2.节点式容器（list/set/map）

        迭代器是节点指针的封装

        删除节点时，该节点内存被释放，迭代器指向无效内存

list<int> l{1,2,3};
auto it = l.begin();
l.erase(it);  // 节点内存被释放
// it 指向已删除节点
二、失效原因分类
容器类型导致失效的操作失效范围
vector/string• 插入导致扩容
• 中间插入/删除		所有迭代器失效
deque• 首尾插入(可能分块)
• 中间插入/删除		部分或全部迭代器失效
list• 删除当前元素仅被删元素的迭代器失效
关联容器
(set/map)		• 删除当前元素
• rehash(unordered)		被删元素迭代器失效
三、典型失效场景分析

  1. vector插入导致扩容

    vector<int> v = {1,2,3};
auto it = v.begin();
v.push_back(4);  // 容量不足，触发重新分配内存
*it = 10;       // 未定义行为！it已失效

    2.删除时的迭代器递增错误

    vector<int> v{1,2,3,4};
for(auto it=v.begin(); it!=v.end(); ++it) {if(*it % 2 == 0)v.erase(it);  // 错误！erase后it失效，再++导致崩溃
}

    3.unordered_map的rehash

    unordered_map<int, string> m;
auto it = m.begin();
for(int i=0; i<1000; ++i) m[i] = to_string(i);  // 可能触发rehash
it->second = "test";    // 可能访问失效内存
    四、避免失效的解决方案

更新迭代器法（推荐）

// vector删除示例
for(auto it=v.begin(); it!=v.end(); /* 空 */) {if(condition) it = v.erase(it);  // erase返回下一个有效迭代器else ++it;
}// 插入操作
it = v.insert(it, new_value);  // insert返回新元素位置
it += 2;  // 安全移动

索引法（仅随机访问容器） 

vector<int> v{1,2,3,4};
for(size_t i=0; i<v.size(); ) {if(v[i] % 2 == 0) {v.erase(v.begin() + i);// 索引自动更新，无需调整} else {++i;}
}

 算法组合法（高效安全）

vector<int> v{1,2,3,4};
// 移除-擦除惯用法
v.erase(remove_if(v.begin(), v.end(), [](int x){ return x%2==0; }), v.end());

临时存储法（复杂删除场景）

list<int> l{1,2,3,4};
vector<list<int>::iterator> toErase;// 先标记要删除的元素
for(auto it=l.begin(); it!=l.end(); ++it)if(*it % 2 == 0) toErase.push_back(it);// 批量删除
for(auto& e : toErase) l.erase(e);
五、特殊容器注意事项

  1. deque：

    • 首尾插入通常不使迭代器失效（除非分块变化）

    • 中间插入使所有迭代器失效

      deque<int> d{1,2,3};
auto it = d.begin() + 1;
d.push_front(0);  // it可能失效！

      关联容器：

    • 插入永不使迭代器失效

    • 删除仅使被删元素的迭代器失效

      set<int> s{1,2,3};
auto it = s.find(2);
s.erase(1);    // 不影响it
s.insert(4);   // 不影响it
cout << *it;   // 安全输出2

      unordered容器：

    • rehash 使所有迭代器失效

    • 可通过reserve()预分配桶避免

      unordered_map<int, string> m;
m.reserve(1000);  // 预分配空间
auto it = m.begin();
for(int i=0; i<500; ++i)m[i] = "test";  // 不会触发rehash
it->second = "safe";  // 安全
      六、最佳实践总结

    • 遍历时修改：优先使用it = container.op(it)模式

    • 大规模修改：使用STL算法（remove/copy_if等）

    • 性能敏感场景：

      • vector预分配空间（reserve()）

      • unordered容器预分配桶（reserve()）

    • 长期保存迭代器：

      • 避免在可能修改容器的代码段保存

vector.h

#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
namespace Boogiepop
{//声明与定义不能分别定义在两个文件template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//迭代器iterator begin(){return _start;}iterator end(){return _finish;}//const迭代器//const不是自身不能修改，而是指向的内容不能修改const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}//构造函数vector():_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){}//拷贝构造函数vector(const vector<T>&v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){reserve(v.capacity());for (auto e : v){push_back(e);}}//强制编辑器生成构造vector()=defalut;//列表初始化构造vector(initializer_list<T> il){reserve(il.size());for (auto& e : il){push_back(e);}}//函数模板初始化template<class InputIterator>vector(InputIterator first, InputIterator last){reserve(last - first);for (InputIterator it = first; it!= last; ++it){push_back(*it);}}vector(size_t n, const T& val){resize(n, val);}//析构函数~vector(){if (_start!= nullptr){delete[]_start;_start = nullptr;_finish = nullptr;_end_of_storage = nullptr;}}//返回一个向量有效元素的个数size_t size() const{return _finish - _start;}//返回一个向量分配内存中元素的个数size_t capacity() const{return _end_of_storage - _start;}//扩容void reserve(size_t n){size_t old_size = size();if (n>capacity()){T*tmp=new T[n];//拷贝旧空间数据if (_start!= nullptr){memcpy(tmp,_start,sizeof(T)*size());delete[]_start;}_start = tmp;_finish = _start + old_size;_end_of_storage = _start + n;}}//尾插数据void push_back(const T& val){if (_finish == _end_of_storage)//空间满了，需要扩容{reserve(capacity() == 0? 4 : 2 * capacity());}*_finish = val;++_finish;}//[]运算符重载T&operator[](size_t i){assert(i<size());return _start[i];}		//判断为空bool empty() const{return _finish == _start;}//尾部删除void pop_back(){/*assert(_finish > _start);*/assert(!empty());--_finish;}//插入void insert(iterator pos, const T& val){assert(pos>=_start && pos<=_finish);if (_finish == _end_of_storage){size_t len =pos-_start;reserve(capacity() == 0 ? 4 : 2 * capacity());//更新pos，pos失效了pos = _start + len;}//移动后面的元素iterator end = _finish - 1;while (end >= pos){*(end + 1)=*end;--end;}*pos = val;++_finish;}//删除void erase(iterator pos){assert(pos>=_start && pos<=_finish);iterator it = pos + 1;while (it !=_finish){*(it - 1) = *(it);++it;}--_finish;}//修改大小void resize(size_t n,T val=T ()){//匿名对象的使用场景if (n>size()){reserve(n);while (_finish!=_start+n){*_finish = val;++_finish;}}else{_finish = _start + n;}}private:iterator _start;//第一个元素的指针iterator _finish;//最后一个元素的指针iterator _end_of_storage;//分配的内存的最后一个元素的指针};
}

test.cpp

#define _CRT_SECURE_NO_WARNINGS
#include"vector.h"
//泛型函数模板
template<typename container>
//打印vector
void print(const container& v)
{//范围for本质上就是迭代器for (auto e : v){std::cout << e << " ";}std::cout << std::endl;
}
void test1()
{Boogiepop::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (size_t i=0; i<v.size();  i++){std::cout<<v[i]<<" ";}std::cout<<std::endl;//范围for本质上就是迭代器for (auto e : v){std::cout<<e<<" ";}std::cout<<std::endl;print(v);
}
void test2()
{Boogiepop::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);print(v);v.pop_back();v.pop_back();print(v);
}
void test3()
{Boogiepop::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);print(v);v.insert(v.begin()+3, - 2);print(v);
}
void test4()
{Boogiepop::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);print(v);int x;std::cin >> x;auto it = std::find(v.begin(), v.end(), x);if(it!= v.end()){//迭代器失效v.insert(it,x*10);//C++扩容没有具体固定vector的扩容规则//我们认为扩容后it就失效了，所以不能使用it//it不能继续使用，已经失效了*it = 10;//要更新迭代器位置}print(v);
}
void test5()
{Boogiepop::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);v.push_back(7);v.push_back(8);print(v);v.erase(v.begin()+2);v.erase(v.begin()+3);print(v);int x;std::cin >> x;auto it = std::find(v.begin(), v.end(), x);if (it != v.end()){//这里的it迭代器不会失效v.erase(it);*it = 10;}print(v);
}
void test6()
{std::vector<int> v;//Boogiepop::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);v.push_back(7);v.push_back(8);print(v);//删除所有的偶数auto it = v.begin();while (it != v.end()){if (*it % 2 == 0){//erase迭代器也会失效//要重新赋新值才可以it=v.erase(it);}else{++it;}}print(v);
}
void test7()
{Boogiepop::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);v.push_back(7);v.push_back(8);print(v);v.resize(10);print(v);v.resize(13,10);print(v);//v.resize(20, 19);
}
void test8()
{Boogiepop::vector<int> v = {1,2,3,4,5,6,7,8,9,10};
}
int main()
{//test1();//test2();//test3();//test4();//test5();//test6();//test7();//test8();return 0;
}

        今天的内容就到这里了求一个点赞谢谢。

封面图自取：

http://www.lryc.cn/news/576134.html

相关文章：

  • Java多线程与JUC
  • window显示驱动开发—DirectX 图形内核子系统(三)
  • RocketMQ 消息长轮询
  • 集群聊天服务器----CMake的使用
  • ServletConfig ServletContext
  • git add 报错UnicodeDecodeError: ‘gbk‘ codec can‘t decode byte 0xaf in position 42
  • 【Elasticsearch】Linux环境下安装Elasticsearch
  • spring ai入门实例
  • LangChain4j（20）——调用百度地图MCP服务
  • Python Async 编程快速入门 | 超简明异步协程指南
  • java代码规范
  • 自动化保护 AWS ECS Fargate 服务：使用 Prisma Cloud 实现容器安全
  • 阶段二开始-第一章—8天Python从入门到精通【itheima】-116节（封装)
  • 鸿蒙HarmonyOS 5小游戏实践：记忆翻牌（附：源代码）
  • DHT11 STM32 HAL驱动库 整数
  • .NetCore+Vue快速生产框架开发详细方案
  • Chrome浏览器访问https提示“您的连接不是私密连接”问题解决方案
  • 已对接Shopee、Lazada、亚马逊等知名海外电商平台！商派DigiOS-OMS业务中台助力品牌扩展全球业务
  • 《Opto-Electronic Advances》热点论文速览（2025）
  • linux中python虚拟环境和版本的选择
  • 【Linux手册】进程终止：进程退出和信号的响应机制
  • VB.NET,C#字典对象来保存用户数据,支持大小写
  • Selenium 多窗口截图（窗口切换）二次封装方法详解 —— Python 实践
  • 【Python】实现对LGBT+ rights worldwide (2025)数据集的可视化展示
  • MySQL在C中常用的API接口
  • TiDB AUTO_RANDOM 超大主键前端精度丢失排查：JavaScript Number 限制与解决方案
  • 玩转Linux CAN/CAN FD—SocketCAN的使用
  • opensuse安装rabbitmq
  • 【编译原理】期末复习知识总结
  • 【大数据】大数据产品基础篇