网站建设开发岗位职责,网站托管做的好的公司,小程序模板设计,书城网站建设规划书vector
erase返回迭代器指向删除元素后的元素insert返回迭代器指插入的元素reserve只给容器底层开指定大小内存空间#xff0c;并不添加新元素
deque
底层数据结构
动态开辟的二维数组#xff0c;一维数组从2开始#xff0c;以2倍方式扩容#xff0c;每次扩容和#x…vector
erase返回迭代器指向删除元素后的元素insert返回迭代器指插入的元素reserve只给容器底层开指定大小内存空间并不添加新元素
deque
底层数据结构
动态开辟的二维数组一维数组从2开始以2倍方式扩容每次扩容和原来第二维数组从新的第一维数组下标oldsize/2开始存放上下都预留空行方便deque在首尾添加删除元素 deque适用于首尾进行操作的场景,和vector比多了push_front和pop_front()
deque底层内存是否是连续的
不是分段连续的每个第二维是连续的
vector、deque、list对比 vector特点动态数组内存是连续的2倍的方式进行扩容 deque特点动态开辟的二维数组空间第二维是固定长度的数组空间扩容的时候第一维的数组进行2倍扩容 容器的纵向考察容器掌握的深度 容器的横向考察各个相似容器之间的对比 vector和deque的区别
vector底层是动态开辟的一维数组deque则是动态开辟的二维数组
前中后插入删除元素时间复杂度中间O(n)和末尾O(1), 首部插入deque O(1),vector则是O(n)
对于内存使用效率vector需要内存空间必须完全连续deque只需分段连续
中间进行insert或erasevector效率更好一点因为deque分段连续在边界位置移动需要多余的操作
vector和list区别
vector底层数据结构是数组list为双向循环链表
数组增加删除O(n),查询O(n),随机访问O(1)
链表考虑搜索时间增加删除O(1),查询O(n),随机访问O(n)
容器适配器 其实源代码上更接近代理模式 queue和stack底层默认使用dequepriority_queue则使用vector为什么
vector初始内存使用效率不如dequedeque一开始就有比较大的第二维连续空间vector则需要多次的二倍扩容操作。
对于queue需要支持尾插头删用deque时间复杂度低O(1)
vector需要大片的连续内存而deque只需要分段的内存当存储大量数据时显然deque对于内存的利用率更好一些。
这就是queue和stack底层默认使用deque的理由
priority_queue堆底层用vector因为堆是树形结构底层用vector数组存储更方便随机访问树的节点下标直接算。如根节点i左子节点为 2 i 1 2i1 2i1,右子节点为 2 i 2 2i2 2i2 priority_queue默认是大根堆比较函数对象为less
