首页 > 代码库 > STL之deque双向队列
STL之deque双向队列
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 (3, 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=1; i<coll.size(); ++i) { coll[i] = "another " + coll [i]; } //change size to four elements coll.resize (4, "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
STL之deque双向队列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。