东莞 网站建设,设计资源网站大推荐,谷歌网站网址,专业的营销型网站培训中心C 浅谈之 STL Vector
HELLO#xff0c;各位博友好#xff0c;我是阿呆 #x1f648;#x1f648;#x1f648;
这里是 C 浅谈系列#xff0c;收录在专栏 C 语言中 #x1f61c;#x1f61c;#x1f61c;
本系列阿呆将记录一些 C 语言重要的语法特性 #x1f3c3; 浅谈之 STL Vector
HELLO各位博友好我是阿呆
这里是 C 浅谈系列收录在专栏 C 语言中
本系列阿呆将记录一些 C 语言重要的语法特性
OK兄弟们废话不多直接开冲 一 概述
简单介绍
vector 与 array 相似区别在于array是静态空间vector 可动态扩容
vectortypeName vt(n_elem); //vector 可用变量初始化, 会自动扩容
arraytypeName, n_elem arr; //array n_elem 由常量指定, 不会扩容迭代器
vector 支持随机存取其迭代器就是普通指针
templateclass T, class Alloc alloc
class vector {
public:typedef T value_type;typedef value_type* iterator; //vector的迭代器是普通指针......
}数据结构
vecotr 所维护线性连续空间 startfinish 标识连续空间被使用范围end_of_storage 指向连续空间末尾
templateclass T, class Alloc alloc
class vector {
......
protected:iterator start; //已使用空间的头iterator finish; //已使用空间的尾iterator end_of_storage; //可用空间的尾
......
}vectorint iv(2,9);
iv.push_back(1);
iv.push_back(2);
iv.push_back(3);
iv.push_back(4);经如上操作vector 内存及各成员如下图状态 的唯一差别在于空间运用的灵活性array是静态空间一旦配置就不能改变vector是动态空间随着元素的加入他的内部机制会自动扩充空间以容纳新的元素。vector的实现技术关键在于对其大小的控制以及重新配置时的数据移动效率 ✌✌✌ 二 核心
动态扩容
当 vector 大小和容量相等sizecapacity时再添加元素就会扩容 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 返回迭代器失效
③ 删除操作 erasepop_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
释放未使用内存C11先调 clear 清空元素整个容器都是未使用了shrink_to_fit 将未使用内存释放
vector 用 memset 清零
memset 将某块内存内容全部设为指定值 常为新申请内存初始化
后果 破坏 vector 内部结构可能导致内存泄露 三 结语
身处于这个浮躁的社会却有耐心看到这里你一定是个很厉害的人吧
各位博友觉得文章有帮助的话别忘了点赞 关注哦你们的鼓励就是我最大的动力
博主还会不断更新更优质的内容加油吧技术人
