deque双向队列是一种双向开口的连续线性空间,可以高效的在头尾两端插入和删除元素,提供随机访问,deque在接口上和vector非常相似,下面列出deque的常用成员函数:
Table 6.9. Constructors and Destructor of Deques
Operation | Effect |
deque<Elem> c | Creates an empty deque without any elements |
deque<Elem> c1(c2) | Creates a copy of another deque of the same type (all elements are copied) |
deque<Elem> c(n) | Creates a deque with n elements that are created by the default constructor |
deque<Elem> c(n,elem) | Creates a deque initialized with n copies of element elem |
deque<Elem> c(beg,end) | Creates a deque initialized with the elements of the range [beg,end) |
c.~deque<Elem>() | Destroys all elements and frees the memory |
Table 6.10. Nonmodifying Operations of Deques
Operation | Effect |
c.size() | Returns the actual number of elements |
c.empty () | Returns whether the container is empty (equivalent to size()==0, but might be faster) |
c.max_size() | Returns the maximum number of elements possible |
c1 == c2 | Returns whether c1 is equal to c2 |
c1 != c2 | Returns whether c1 is not equal to c2 (equivalent to ! (c1==c2)) |
c1 < c2 | Returns whether c1 is less than c2 |
c1 > c2 | Returns whether c1 is greater than c2 (equivalent to c2<c1) |
c1 <= c2 | Returns whether c1 is less than or equal to c2 (equivalent to ! (c2<c1) ) |
c1 >= c2 | Returns whether c1 is greater than or equal to c2 (equivalent to ! (c1<c2) ) |
c.at(idx) | Returns the element with index idx (throws range error exception if idx is out of range) |
c[idx] | Returns the element with index idx (no range checking) |
c.front() | Returns the first element (no check whether a first element exists) |
c.back() | Returns the last element (no check whether a last element exists) |
c.begin() | Returns a random access iterator for the first element |
c.end() | Returns a random access iterator for the position after the last element |
c.rbegin() | Returns a reverse iterator for the first element of a reverse iteration |
c.rend() | Returns a reverse iterator for the position after the last element of a reverse iteration |
Table 6.11. Modifying Operations of Deques
Operation | Effect |
c1 = c2 | Assigns all elements of c2 to c1 |
c.assign (n,elem) | Assigns n copies of element elem |
c.assign (beg,end) | Assigns the elements of the range [beg,end) |
c1.swap(c2) | Swaps the data of c1 and c2 |
swap(c1,c2) | Same (as global function) |
c.insert (pos,elem) | Inserts at iterator position pos a copy of elem and returns the position of the new element |
c. insert (pos,n,elem) | Inserts at iterator position pos n copies of elem (returns nothing) |
c.insert (pos,beg,end) | Inserts at iterator position pos a copy of all elements of the range [beg,end) (returns nothing) |
c.push_back (elem) | Appends a copy of elem at the end |
c.pop_back() | Removes the last element (does not return it) |
c.push_front (elem) | Inserts a copy of elem at the beginning |
c.pop_front() | Removes the first element (does not return it) |
c.erase(pos) | Removes the element at iterator position pos and returns the position of the next element |
c.erase (beg,end) | Removes all elements of the range [beg,end) and returns the position of the next element |
c. resize (num) | Changes the number of elements to num (if size () grows, new elements are created by their default constructor) |
c.resize (num, elem) | Changes the number of elements to num (if size () grows, new elements are copies of elem) |
c.clear() | Removes all elements (makes the container empty) |
deque的实现比较复杂,内部会维护一个map(注意!不是STL中的map容器)即一小块连续的空间,该空间中每个元素都是指针,指向另一段(较大的)区域,这个区域称为缓冲区,缓冲区用来保存deque中的数据。因此deque在随机访问和遍历数据会比vector慢。具体的deque实现可以参考《STL源码剖析》,当然此书中使用的SGI STL与VS2008所使用的PJ STL的实现方法还是有区别的。下面给出了deque的结构图:
由于篇幅问题,deque的实现细节就不再深入了,下面给出deque的使用范例:
// cont/deque1. cpp #include <iostream>
#include <deque>
#include <string>
#include <algorithm>
using namespace std; int main()
{ //create empty deque of strings
deque<string> coll; //insert several elements
coll.assign (, string("string"));
coll.push_back ("last string");
coll.push_front ("first string"); //print elements separated by newlines
copy (coll.begin(), coll.end(),
ostream_iterator<string>(cout,"\n"));
cout << endl; //remove first and last element
coll.pop_front();
coll.pop_back(); //insert ''another'' into every element but the first
for (int i=; i<coll.size(); ++i) {
coll[i] = "another " + coll [i]; } //change size to four elements
coll.resize (, "resized string"); //print elements separated by newlines
copy (coll.begin(), coll.end(),
ostream_iterator<string>(cout,"\n")); }
The program has the following output:
first string
string
string
string
last string string
another string
another string
resized string