C++ 浅谈之 STL Vector

C++ 浅谈之 STL Vector

HELLO，各位博友好，我是阿呆 🙈🙈🙈

这里是 C++ 浅谈系列，收录在专栏 C++ 语言中 😜😜😜

本系列阿呆将记录一些 C++ 语言重要的语法特性 🏃🏃🏃

OK，兄弟们，废话不多直接开冲 🌞🌞🌞

一 🏠 概述

简单介绍

vector 与 array 相似，区别在于：array是静态空间，vector 可动态扩容

vector<typeName> vt(n_elem);    //vector 可用变量初始化, 会自动扩容
array<typeName, n_elem> arr;    //array n_elem 由常量指定, 不会扩容

迭代器

vector 支持随机存取，其迭代器就是普通指针 👊👊👊

template<class T, class Alloc = alloc>
class vector {
public:typedef T value_type;typedef value_type* iterator;   //vector的迭代器是普通指针......
}

数据结构

vecotr 所维护线性连续空间， start，finish 标识连续空间被使用范围，end_of_storage 指向连续空间末尾 👦👦👦

template<class T, class Alloc = alloc>
class vector {
......
protected:iterator start;             //已使用空间的头iterator finish;            //已使用空间的尾iterator end_of_storage;    //可用空间的尾
......
}

vector<int> iv(2,9);
iv.push_back(1);
iv.push_back(2);
iv.push_back(3);
iv.push_back(4);

经如上操作，vector 内存及各成员如下图状态 👇👇👇

的唯一差别在于空间运用的灵活性：array是静态空间，一旦配置就不能改变；vector是动态空间，随着元素的加入，他的内部机制会自动扩充空间以容纳新的元素。vector的实现技术，关键在于对其大小的控制以及重新配置时的数据移动效率 ✌✌✌

二 🏠 核心

动态扩容

当 vector 大小和容量相等（size==capacity）时，再添加元素，就会扩容

1、弃用现用内存空间，申请更大内存空间

2、将原内存空间数据，按原次序移动到新内存空间

3、旧内存空间释放

4、指向新内存空间

SGI-STL 扩容机制，伪代码如下 👇👇👇

// SGI-STL扩容机制
void reserve(size_type n) {// 当n大于当前vector的容量时才会扩容，小于等于当前容量则忽略本次操作if (capacity() < n) {const size_type old_size = size();// 使用空间配置器开辟n个新空间，并将旧空间元素拷贝到新空间iterator tmp = allocate_and_copy(n, start, finish);// 释放旧空间// a. 先调用析构函数, 将[start, finish)区间总所有的对象析构完整destroy(start, finish);// b. 将空间规划给空间配置器deallocate();// 3. 接收新空间并更新其成员start = tmp;finish = tmp + old_size;end_of_storage = start + n;}
}

小优化 ：reserve 预分配空间，避免频繁动态扩容 👨‍🚀👨‍🚀👨‍🚀

Vector 迭代器失效场景

① 当插入一个元素后，end 返回迭代器失效

② 当插入一个元素后，造成动态扩容，first 和 end 返回迭代器失效

③ 删除操作 （erase，pop_back） ，指向删除点和后面元素的迭代器失效 🐌🐌🐌

迭代器失效原因

① vector ，维护连续内存，删除一个元素后，其它数据地址可能会发生变化（erase 会返回下一个有效迭代器）

② map、set、multiset、map、multimap，红黑树或平衡二叉树储存数据，删除了一个元素后，树调整，但其它数据的内存地址无变化，各节点指向关系改变（erase 仅被删元素迭代器失效）

③ list 链表型结构，不连续内存，仅被删元素迭代器失效 🐳 🐳 🐳

不适合插入和删除

元素 3 位置插入 0 ，需将 3 4 5 整体向后搬移一个位置，最差情况下时间复杂度为 O(N)

vector不适宜做任意位置插入与删除操作，因为插入和删除时需要搬移大量元素：

如何快速释放内存

reserve 只在传入大小比原有内存大时才触发，而 resize 或 clear 仅对容器元素进行析构，容器本身空间不会释放

① swap

vector().swap(v) 用空 vector 与当前 vector 交换（空 vector 是临时变量，出作用域会自动调用析构） 🐋🐋🐋

② shrink_to_fit

释放未使用内存（C++11），先调 clear 清空元素（整个容器都是未使用了），shrink_to_fit 将未使用内存释放

vector 用 memset 清零

memset ：将某块内存内容全部设为指定值， 常为新申请内存初始化，

后果 ：破坏 vector 内部结构，可能导致内存泄露 🎅🎅🎅

三 🏠 结语

身处于这个浮躁的社会，却有耐心看到这里，你一定是个很厉害的人吧 👍👍👍

各位博友觉得文章有帮助的话，别忘了点赞 + 关注哦，你们的鼓励就是我最大的动力

博主还会不断更新更优质的内容，加油吧！技术人！ 💪💪💪