1)概述
deque 是顺序性容器,是一种双向开口的连续线性空间。可以在头尾分别做元素的的安插和删除操作;vector当然也可以在头尾两端做动作,但是其头部动作效率奇差。deque和vector最大的差异在于:deque允许在常数时间内对两端进行元素的插入或删除操作;deque没有所谓容量的概念,因为它是以分段的连续空间组合而成,随时可以增加一段空间拼接起来,不存在像vector那样“因空间不足而分配一块更大的空间然后复制元素”问题。
排序问题:deque提供random access iterator,但并不是原生指标。其实现的复杂度也很大,这也影响到相关算法的效率。所以如非必要,应该尽量使用vector而不是deque。对的确进行排序时,可以先将元素复制到一个vector,排序后再复制回deque。
存储结构:deque采用的是一种分段连续空间存储结构,采用一个map(不是stl中的map)来管理这些空间段。map是一段连续空间,其中每个元素都是指针。指向另外一段较大的连续线性空间,成为缓冲区。缓冲区才是deque的存储空间主体。缓冲区扩充相当繁琐!!!
【注意】deque,当使用插入删除操作的时候是一个更好的选择。其余时选择vector比较合适
2)使用
需加载的头文件: #include<deque>
using namespace std;
3)主要方法
构造:
deque<Elem> c 创建一个空的deque
deque<Elem> c1(c2) 复制一个deque。
deque<Elem> c(n) 创建一个deque,含有n个数据,数据均已缺省构造产生。
deque<Elem> c(n, elem) 创建一个含有n个elem拷贝的deque
deque<Elem> c(beg,end) 创建一个以[beg;end)区间的deque
c.~deque<Elem>() 销毁所有数据,释放内存
方法:
c.assign(beg,end) 将[beg; end)区间中的数据赋值给c。
c.assign(n,elem) 将n个elem的拷贝赋值给c。
c. at(idx) 传回索引idx所指的数据,如果idx越界,抛出out_of_range。
c.back() 传回最后一个数据,不检查这个数据是否存在。
c.begin() 传回迭代器中的第一个数据?????
c.clear() 移除容器中所有数据。
c.empty() 判断容器是否为空。
c.end() 指向迭代器中的最后一个数据地址。
c.erase(pos) 删除pos位置的数据,传回下一个数据的位置。
c.erase(beg,end) 删除[beg,end)区间的数据,传回下一个数据的位置。
c.front() 传回第一个数据。
get_allocator 使用构造函数返回一个拷贝。
c.insert(pos,elem) 在pos位置插入一个elem拷贝,传回新数据位置
c.insert(pos,n,elem) 在pos位置插入n个elem数据。无返回值
c.insert(pos,beg,end) 在pos位置插入在[beg,end)区间的数据。无返回值
c.max_size() 返回容器中最大数据的数量。
c.pop_back() 删除最后一个数据。
c.pop_front() 删除头部数据。
c.push_back(elem) 在尾部加入一个数据。
c.push_front(elem) 在头部插入一个数据。
c.rbegin() 传回一个逆向队列的第一个数据。
c.rend() 传回一个逆向队列的最后一个数据的下一个位置。
c.resize(num) 重新指定队列的长度。
c.size() 返回容器中实际数据的个数。
c.swap(c2) =swap(c1,c2) 将c1和c2元素互换。
4)例子
#include <deque>
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
deque<int> deq(20); //创建一个20个元素的双端队列
deque<int>::iterator pos; //迭代器
int i;
for (i = 0; i < 20; ++i)
deq[i] = i;
printf("输出deque中数据:\n");
for (i = 0; i < 20; ++i)
printf("%d ", deq[i]);
putchar('\n');//比cout 快
printf("\n在头尾加入新数据...\n");
deq.push_back(100); //在尾插入
deq.push_front(i); //在头插入
printf("\n输出deque中数据:\n");
for (pos = deq.begin(); pos != deq.end(); pos++)
printf("%d ", *pos);
putchar('\n');
//查找
const int FINDNUMBER = 19;
printf("\n查找%d\n", FINDNUMBER);
pos = find(deq.begin(), deq.end(), FINDNUMBER); //#include <algorithm>
if (pos != deq.end())
printf("find %d success\n", *pos);
else
printf("find failed\n");
printf("\n在头尾删除数据...\n");
deq.pop_back();
deq.pop_front();
printf("\n交换后输出deque2中数据:\n");
deque<int> deq2(20);
deq2.swap(deq);
for (pos = deq2.begin(); pos != deq2.end(); pos++)
printf("%d ", *pos);
putchar('\n');
printf("\n输出deque中最大数据的数量:\n");
printf("%d ", deq.max_size());
putchar('\n');
return 0;
}
puts(char *string)
5)比较deque和vector
当执行大数据量的调用push_back()的时候,记住要调用vector::reserve()。
当你分配很多内存单元的时候,记住使用deque回收内存要比vector消耗时间多。
如果你计划使用insert(),或者需要pop_front(),那就使用deque。
对于访问数据,vector::at()效率最高。
分享到:
相关推荐
第7章 deque双端队列容器 第8章 list双向链表容器 第9章 slist单向链表容器 第10章 bit_vector位向量容器 第11章 set集合容器 第12章 multiset多重集合容器 第13章 map映照容器 第14章 multimap多重映照容器 第15章 ...
第7章 deque双端队列容器 102 7.1 deque技术原理 102 7.2 deque应用基础 108 7.3 本章小结 115 第8章 list双向链表容器 116 8.1 list技术原理 116 8.2 list应用基础 124 8.3 本章小结 131 第9章 ...
第7章 deque双端队列容器 102 7.1 deque技术原理 102 7.2 deque应用基础 108 7.3 本章小结 115 第8章 list双向链表容器 116 8.1 list技术原理 116 8.2 list应用基础 124 8.3 本章小结 131 第9章 ...
第7章 deque双端队列容器 102 7.1 deque技术原理 102 7.2 deque应用基础 108 7.3 本章小结 115 第8章 list双向链表容器 116 8.1 list技术原理 116 8.2 list应用基础 124 8.3 本章小结 131 第9章 ...
#include <deque> //STL 双端队列容器 #include <exception> //异常处理类 #include #include <functional> //STL 定义运算函数(代替运算符) #include #include <list> //STL 线性列表容器 #include <map> ...
//STL 双端队列容器 #include <exception> //异常处理类 #include <fstream> #include <functional> //STL 定义运算函数(代替运算符) #include <limits> #include <list> //...
deque 是一种双端队列,可以在两端高效地进行插入和删除操作,因此非常适合实现队列的入队和出队操作。队列类提供了以下主要方法: - `enqueue(const T& element)`: 将元素入队,即将其添加到队尾。 - `isEmpty()`: ...
#include <deque> //STL 双端队列容器 #include <exception> //异常处理类 #include <fstream> //文件输入/输出 #include <functional> //STL 定义运算函数(代替运算符) #include <limits> //定义各种数据...
九、deque (Double Ended Queue) 双端队列 22 成员函数: 22 实例程序: 23 十、string 字符串 24 成员函数: 24 实例程序: 28 十一、常用算法调用 29 1. for_each 29 2. min_element / max_element 29 3. copy / ...
双端队列queue,容器适配器,由deque实现stack,容器适配器,由deque实现avl_tree,高度平衡二叉搜索树,通过旋转维持平衡skiplist,跳表,代替红黑树实现map和setmap/set,由skiplist实现hashtable,哈希表,开链法...