河北住房建设厅官方网站,东莞整站优化公司火速公司,苏州工业园区教育局官网,怎么做二级网站域名deque概述 deque属于顺序容器#xff0c;称为双端队列容器 底层数据结构是动态二维数组#xff0c;从整体上看#xff0c;deque的内存不连续 初始数组第一维数量为2#xff0c;必要时进行2倍扩容 每次第一维扩容后#xff0c;原来数组第二维元素从新数组下标为OldSize/2的…
deque概述 deque属于顺序容器称为双端队列容器 底层数据结构是动态二维数组从整体上看deque的内存不连续 初始数组第一维数量为2必要时进行2倍扩容 每次第一维扩容后原来数组第二维元素从新数组下标为OldSize/2的第一维开始存储 这样的存储方式使得前后都预留相同空间方便支持deque首尾元素添加 数组第二维长度固定 deque相关操作
// deque相较于vector增加的相关操作有push_front()和pop_front()dequeint deq;// 1、添加
deq.push_back(10);
// 1向末尾添加元素10时间复杂度为O(1)
deq.push_front(20);
// 2向首部添加元素20时间复杂度为O(1)
deq.insert(it, 30);
// 3向迭代器it处添加元素30需要挪动元素和更新迭代器时间复杂度为O(n)// 2、删除
deq.pop_back();
// 1删除末尾元素时间复杂度为O(1)
deq.pop_front();
// 2删除首部元素时间复杂度为O(1)
deq.erase(it);
// 3删除迭代器it处元素需要挪动元素和更新迭代器时间复杂度为O(n)// 3、查询
// 1使用迭代器遍历
辨析vector和deque 1、底层数据结构不同 vector底层是动态一维数组 deque底层是动态二维数组 2、添加删除元素的时间复杂度不同 首部添加删除操作频繁选择deque 3、内存使用效率不同 vector需要连续内存空间内存使用效率低 deque分块存储数据不要求内存空间连续内存使用效率高 4、在中间位置添加删除的效率不同 vector效率更高deque效率更低 因为vector使用连续内存空间方便挪动元素 而deque的内存空间不连续不便挪动元素 list概述 list属于顺序容器称为链表容器 底层数据结构是双向循环链表 list相关操作
// list相较于vector增加的相关操作有push_front()和pop_front()listint mylist;// 1、添加
mylist.push_back(10);
// 1向末尾添加元素10时间复杂度为O(1)
mylist.push_front(20);
// 2向首部添加元素20时间复杂度为O(1)
mylist.insert(it, 30);
// 3向迭代器it处添加元素30需要更新迭代器时间复杂度为O(1)
// 链表进行insert前需要进行query查询
// 对于链表来说query查询效率低// 2、删除
mylist.pop_back();
// 1删除末尾元素时间复杂度为O(1)
mylist.pop_front();
// 2删除首部元素时间复杂度为O(1)
mylist.erase(it);
// 3删除迭代器it处元素需要更新迭代器时间复杂度为O(1)// 3、查询
// 1使用迭代器遍历
辨析vector和list 1、底层数据结构不同 vector底层是动态一维数组 list底层是双向循环链表 2、时间复杂度不同 vector增加删除O(n)、查询O(n)、随机访问O(1) list增加删除O(1)、查询O(n) 增加删除操作频繁选择list 随机访问操作频繁选择vector
