当前位置: 代码迷 >> 综合 >> STL容器——deque
  详细解决方案

STL容器——deque

热度:97   发布时间:2023-12-05 18:12:28.0

deque:是一种序列容器,具有分段数组(存储数据)和索引数组(存储每段数组的首地址)。

一:deque的特点

1.可以在两端进行push和pop操作,且效率高;支持内部插入删除,效率较低;

2.支持高效的随机访问;

3.动态分配空间,当存储空间已满,会创建新的分段数组,且分段数组的首地址存入索引数组。

二:deque的定义与初始化

deque<int> d1;//定义int型队列deque<int> d2(10);//size为10,默认值为0deque<int> d3(10, 10);//size为10,元素值为10deque<int> d4 = { 1,2,3,4 };deque<int> d5{ 1,2,3,4 };deque<int> d6(d4);deque<int> d7 = d4;deque<int> d8(d4.begin(), d4.end());

三:基本操作

//元素访问
d4[0];d4.front();d4.back();d4.at(1);//插入d4.push_back(1);d4.push_front(1);d4.insert(d4.end(), 1);d4.insert(d4.end(), 5, 1);d4.insert(d4.end(), d4.begin(), d5.end());//删除
d4.pop_back();d4.pop_front();d4.erase(d4.begin() + 1);d4.erase(d4.begin(), d4.begin() + 1);d4.size();d4.assign(2, 3);d4.clear();

四:迭代器

包括: begin、end、rbegin、rend、cbegin、cend、crbegin、crend

d4.begin(); 返回迭代器, 指向第一元素
d4.end(); 返回迭代器, 指向最末元素的下一个位置
d4.cbegin(); 返回迭代器, 指向第一元素, 类型为const
d4.cend(); 返回迭代器, 指向最末元素的下一个位置, 类型为const
d4.rbegin(); 返回反向迭代器, 指向反向迭代的第一元素
d4.rend(); 返回反向迭代器, 指向反向迭代的最末元素的下一个位置
d4.crbegin(); 返回反向迭代器, 指向反向迭代的第一元素, 类型为const
d4.crend(); 返回反向迭代器, 指向反向迭代的最末元素的下一个位置, 类型为const

五:总结

1.时间复杂度:访问时间复杂度时O(1);插入时间复杂度:push_front为O(1),push_back为O(1),insert为O(n);删除时间复杂度:pop_front为O(1),pop_back为O(1),erase为O(n)。

2.deque兼容vector和list的优点,支持高效的随机访问和两端插入删除,但是占用内存多。

  相关解决方案