【C++STL】Vector扩容机制

创作不易，本篇文章如果帮助到了你，还请点赞 关注支持一下♡>𖥦<)!!
主页专栏有更多知识，如有疑问欢迎大家指正讨论，共同进步！
🔥c++系列专栏：C/C++零基础到精通 🔥

给大家跳段街舞感谢支持！ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ

c语言内容💖：

专栏：c语言之路重点知识整合

【c语言】全部知识点总结

Vector

Vector是 C++中常用的 STL 容器，能够方便地进行元素的添加、删除和访问操作

动态数组，里面有一个指针指向一片连续的内存空间，与数组的差别在于对空间利用的灵活性。

vector 中删除数据时，vector 的容量不变；扩容时可能导致迭代器失效

Vector 内函数：

#include <vector>
using namespace std;
class Vector
{
Protected:
    Iterator start;					//表示目前使用空间的头
    Iterator finish;				//表示目前使用空间的尾
    Iterator end_of_storage;		//表示目前可用空间的尾
Public:
    Iterator begin();				//获取头元素迭代器
    Iterator end();					//获取尾元素迭代器
    Reference front();				//返回首元素的值
    Reference back();				//返回尾元素的值
    Size_type size();				//返回使用空间的大小
    Size_type capacity();			//返回容量的大小
    void push_back(const T& x);		//将元素插入到最尾端
    void pop_back();				//将最尾端的元素取出
    Iterator erase(iterator position);//清除某位置上的元素，返回下一节点迭代器
    void insert(位置，数值);		    //在某个位置插入多少个元素
    void clear();			    	//清除所有元素
};

Vector 扩容机制

Vector 在存储元素时，会预先分配一定的存储空间。当不断向 Vector 中添加元素，导致已分配的空间不足时，就需要进行扩容 来增加存储空间，以满足新元素的添加需求

为什么需要扩容机制

通过扩容机制，Vector 能够灵活地适应元素数量的变化，提供稳定和可靠的数据存储

扩容策略

1. 固定倍数扩容
   • 每次扩容为原来容量的两倍。假设初始容量为n，当空间不足时，将容量扩展为2n
   • 优点：简单高效
   • 缺点：可能会造成空间浪费
2. 渐进式扩容
   • 每次扩容增加一个固定的增量，比如每次增加n个元素的空间
   • 优点：可以控制空间增长，减少不必要的浪费
   • 缺点：扩容次数可能较多

扩容时需要重新分配更大的内存空间，并将原有的元素复制到新的空间中

什么时候扩容

vector 类本身起始只有三个指针，_start、_finish、_end_of_storage分别指向了数据开始的地方，数据结束的地方，和数组的结尾

当 _start 指针和 _end_of_storage 指向了同一个地方，说明数组的空间已经用完了，这个时候就需要扩容