生活随笔
收集整理的這篇文章主要介紹了
STL系列之一 deque双向队列
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
原文地址：http://blog.csdn.net/morewindows/article/details/6946811
deque雙向隊(duì)列是一種雙向開口的連續(xù)線性空間，可以高效的在頭尾兩端插入和刪除元素，deque在接口上和vector非常相似，下面列出deque的常用成員函數(shù)：
deque的實(shí)現(xiàn)比較復(fù)雜，內(nèi)部會(huì)維護(hù)一個(gè)map（注意！不是STL中的map容器）即一小塊連續(xù)的空間，該空間中每個(gè)元素都是指針，指向另一段（較大的）區(qū)域，這個(gè)區(qū)域稱為緩沖區(qū)，緩沖區(qū)用來保存deque中的數(shù)據(jù)。因此deque在隨機(jī)訪問和遍歷數(shù)據(jù)會(huì)比vector慢。具體的deque實(shí)現(xiàn)可以參考《STL源碼剖析》，當(dāng)然此書中使用的SGI STL與VS2008所使用的PJ STL的實(shí)現(xiàn)方法還是有區(qū)別的。下面給出了deque的結(jié)構(gòu)圖：
?
由于篇幅問題，deque的實(shí)現(xiàn)細(xì)節(jié)就不再深入了，下面給出deque的使用范例：
[cpp]view plaincopy
?? ?? #include?<deque>?? #include?<cstdio>?? #include?<algorithm>?? using?namespace?std;?? int?main()?? {?? ????deque<int>?ideq(20);??? ????deque<int>::iterator?pos;?? ????int?i;?? ?? ?????? ????for?(i?=?0;?i?<?20;?++i)?? ????????ideq[i]?=?i;?? ?????? ?????? ????printf("輸出deque中數(shù)據(jù):\n");?? ????for?(i?=?0;?i?<?20;?++i)?? ????????printf("%d?",?ideq[i]);?? ????putchar('\n');?? ?? ?????? ????printf("\n在頭尾加入新數(shù)據(jù)...\n");?? ????ideq.push_back(100);?? ????ideq.push_front(i);?? ?? ?????? ????printf("\n輸出deque中數(shù)據(jù):\n");?? ????for?(pos?=?ideq.begin();?pos?!=?ideq.end();?pos++)?? ????????printf("%d?",?*pos);?? ????putchar('\n');?? ?? ?????? ????const?int?FINDNUMBER?=?19;?? ????printf("\n查找%d\n",?FINDNUMBER);?? ????pos?=?find(ideq.begin(),?ideq.end(),?FINDNUMBER);?? ????if?(pos?!=?ideq.end())?? ????????printf("find?%d?success\n",?*pos);?? ????else?? ????????printf("find?failed\n");?? ?? ?????? ????printf("\n在頭尾刪除數(shù)據(jù)...\n");?? ????ideq.pop_back();?? ????ideq.pop_front();?? ?? ?????? ????printf("\n輸出deque中數(shù)據(jù):\n");?? ????for?(pos?=?ideq.begin();?pos?!=?ideq.end();?pos++)?? ????????printf("%d?",?*pos);?? ????putchar('\n');?? ????return?0;?? }??
運(yùn)行結(jié)果如下：
另外要注意一點(diǎn)。對(duì)于deque和vector來說，盡量少用erase(pos)和erase(beg,end)。因?yàn)檫@在中間刪除數(shù)據(jù)后會(huì)導(dǎo)致后面的數(shù)據(jù)向前移動(dòng)，從而使效率低下。
?
超強(qiáng)干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生
總結(jié)
以上是生活随笔為你收集整理的STL系列之一 deque双向队列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
