九乡新闻网英魂之刃林初心视频:STL容器之deque
来源：百度文库 编辑：九乡新闻网 时间：2024/04/29 09:13:36
“vector是单向开口的连续线性空间，deque则是一种双向开口的连续空间。所谓双向开口，意思是可以在头尾两端分别做元素的插入和删除操作。vector当然也可以在头尾两端进行操作（从技术观点），但是其头部操作效率奇差，无法被接受。”
“deque和vector的最大差异，一在于deque允许于常数时间内对起头端进行元素的插入和移除操作，二在于deque没有所谓容量（capacity）概念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。换句话说，像vector那样因为空间不足而重新分配一块更大空间然后复制元素，再释放就空间这样的事情在deque是不会发生的。”
“虽然deque也提供了Ramdon Acces Iterator，但它的迭代器并不是普通指针，其复杂度和vector也不是一个数量级上的，这当然也会影响到运算的各个层面。因此，除非必要，我们应尽可能选择使用vector而非deque。对deque进行的排序操作，为了最高效率，可将deque先完整复制到一个vector，将vector（利用STL Sort算法），再复制回deque。”
--以上摘自 侯捷 《STL源码剖析》 p143
deque，意为double ended queue（双端队列），常读作deck。其用法和大家熟知的vector类似，接口基本和vector雷同。至于二者的不同之处和孰优孰劣，上面摘录的侯大师书里说的也很明白。容器本身没有绝对的好坏，关键看应用环境和需要。
成员函数表如下：
函数
描述
assign(beg,end)
assign(n,elem)
将[beg; end) 区间中的数据赋值
将n个elem 的拷贝赋值
at(idx)
传回索引 idx 所指的数据，如果 idx 越界，抛出 out_of_range
back()
传回最后一个数据，不检查这个数据是否存在
begin()
传回迭代器重的可一个数据
clear()
移除容器中所有数据
deque c1(c2)
deque c(n)
deque c(n, elem)
deque c(beg,end)
~deque()
复制一个deque
创建一个deque,含有n个数据,数据均已缺省构造产生
创建一个含有n个elem 拷贝的 deque
创建一个以[beg;end)区间的 deque
销毁所有数据，释放内存
empty()
判断容器是否为空
end()
指向迭代器中的最后一个数据地址
erase(pos)
erase(beg,end)
删除pos位置的数据，传回下一个数据的位置
删除[beg,end)区间的数据,传回下一个数据的位置
front()
传回地一个数据
get_allocator
使用构造函数返回一个拷贝
insert(pos,elem)
insert(pos,n,elem)
insert(pos,beg,end)
在pos位置插入一个elem拷贝,传回新数据位置
在pos位置插入n 个elem数据,无返回值
在pos位置插入在[beg,end)区间的数据,无返回值
max_size()
返回容器中最大数据的数量
pop_back()
删除最后一个数据
pop_front()
删除头部数据
push_back(elem)
在尾部加入一个数据
push_front(elem)
在头部插入一个数据
rbegin()
传回一个逆向队列的第一个数据
rend()
传回一个逆向队列的最后一个数据的下一个位置
resize(num)
重新指定队列的长度
size()
返回容器中实际数据的个数
c1.swap(c2)
swap(c1,c2)
将 c1 和 c2 元素互换
同上操作
operator []
返回容器中指定位置的一个引用
延伸阅读：
（1）今天找到一个不得不用deque的理由 （无论是否赞同作者的观点，至少对理解deque是有益的）
（2）深入研究 C++中的 STL Deque 容器
“deque和vector的最大差异，一在于deque允许于常数时间内对起头端进行元素的插入和移除操作，二在于deque没有所谓容量（capacity）概念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。换句话说，像vector那样因为空间不足而重新分配一块更大空间然后复制元素，再释放就空间这样的事情在deque是不会发生的。”
“虽然deque也提供了Ramdon Acces Iterator，但它的迭代器并不是普通指针，其复杂度和vector也不是一个数量级上的，这当然也会影响到运算的各个层面。因此，除非必要，我们应尽可能选择使用vector而非deque。对deque进行的排序操作，为了最高效率，可将deque先完整复制到一个vector，将vector（利用STL Sort算法），再复制回deque。”
--以上摘自 侯捷 《STL源码剖析》 p143
deque，意为double ended queue（双端队列），常读作deck。其用法和大家熟知的vector类似，接口基本和vector雷同。至于二者的不同之处和孰优孰劣，上面摘录的侯大师书里说的也很明白。容器本身没有绝对的好坏，关键看应用环境和需要。
成员函数表如下：
函数
描述
assign(beg,end)
assign(n,elem)
将[beg; end) 区间中的数据赋值
将n个elem 的拷贝赋值
at(idx)
传回索引 idx 所指的数据，如果 idx 越界，抛出 out_of_range
back()
传回最后一个数据，不检查这个数据是否存在
begin()
传回迭代器重的可一个数据
clear()
移除容器中所有数据
deque c1(c2)
deque c(n)
deque c(n, elem)
deque c(beg,end)
~deque()
复制一个deque
创建一个deque,含有n个数据,数据均已缺省构造产生
创建一个含有n个elem 拷贝的 deque
创建一个以[beg;end)区间的 deque
销毁所有数据，释放内存
empty()
判断容器是否为空
end()
指向迭代器中的最后一个数据地址
erase(pos)
erase(beg,end)
删除pos位置的数据，传回下一个数据的位置
删除[beg,end)区间的数据,传回下一个数据的位置
front()
传回地一个数据
get_allocator
使用构造函数返回一个拷贝
insert(pos,elem)
insert(pos,n,elem)
insert(pos,beg,end)
在pos位置插入一个elem拷贝,传回新数据位置
在pos位置插入n 个elem数据,无返回值
在pos位置插入在[beg,end)区间的数据,无返回值
max_size()
返回容器中最大数据的数量
pop_back()
删除最后一个数据
pop_front()
删除头部数据
push_back(elem)
在尾部加入一个数据
push_front(elem)
在头部插入一个数据
rbegin()
传回一个逆向队列的第一个数据
rend()
传回一个逆向队列的最后一个数据的下一个位置
resize(num)
重新指定队列的长度
size()
返回容器中实际数据的个数
c1.swap(c2)
swap(c1,c2)
将 c1 和 c2 元素互换
同上操作
operator []
返回容器中指定位置的一个引用
延伸阅读：
（1）今天找到一个不得不用deque的理由 （无论是否赞同作者的观点，至少对理解deque是有益的）
（2）深入研究 C++中的 STL Deque 容器
STL容器之deque
stl容器区别: vector list deque set map-底层实现
C++ STL基本容器string,vector,list,deque,map的比较
C++ STL 容器技术之 vector向量容器
STL vector 容器介绍
STL容器 erase的使用陷阱
STL vector 容器介绍 - masterlee的专栏 - CSDN博客
STL中的list、vector和deque三者之间的区别!
c++ STL 之list 用法精讲
(数据结构复习)链队列和动态数组队列以及STL中的deque双端队列和Queue普通队列,堆排序队列priority_queue
STL set
STL概述
STL map
STL Overview
VC知识库BLOG-周星星 之 Blog-STL之父访谈录 [转载]
C++容器:顺序容器，关联容器
Deque双端队列界面
容器育苗
STL vector用法
STL学习总结
【转】详细解说STL hash_map
20.2.2 容器控件
人生的容器
人生的容器