deque的基本情況：
簡單的來說deque是一個雙頭隊列。且兩邊的尺寸可以動態(tài)收縮或者擴(kuò)張。
其底層實現(xiàn)相當(dāng)復(fù)雜，而且效率并不高。大多數(shù)時候都不會使用。
deque誕生的原因是vector和list的優(yōu)缺點不可分割。
正好復(fù)習(xí)一下vector和list的優(yōu)缺點。
vector的優(yōu)點：支持隨機訪問；尾插，尾刪很方便；高速緩存命中率高。
vector的缺點：不支持頭插或者中間插入；擴(kuò)容具備一定的性能消耗，以及空間浪費。
list的優(yōu)點：任意位置插入刪除數(shù)據(jù)只需要O(1)復(fù)雜度；按需申請釋放空間，沒有損耗。
list的缺點：不支持隨機訪問，高速緩存命中率低。
對比兩者的優(yōu)缺點，發(fā)現(xiàn)他們的缺點正是為了他們的優(yōu)點誕生的，兩者不可分割。deque就是針對兩者的缺點設(shè)計出來的，所以性能被犧牲了。
deque的底層大概是這樣的結(jié)構(gòu)：
如何滿足隨機訪問？
要訪問的下標(biāo)，減去第一個數(shù)組具有的元素個數(shù)，然后/10，就能知道在第幾個空間了。%10就能知道在第幾個位置。
deque的優(yōu)點：
1.頭插和尾插效率不錯
2.支持隨機訪問
3.高速緩存命中率高
4.擴(kuò)容代價小
deque的缺點
1.中部插入刪除效率不行，(要么需要挪動數(shù)據(jù)，要么支持每個開辟的空間大小不一定相同，這樣的話，中控數(shù)組還要記錄每個空間有多少個元素，因為要支持隨機訪問)
2.雖然支持隨機訪問，但效率相對于vector而言還有差距。頻繁隨機訪問時要小心。
以排序為例(測試在release下)：
用deque存數(shù)據(jù)，進(jìn)行排序，和vector存數(shù)據(jù)(和deque中的內(nèi)容一樣)，進(jìn)行排序。10000以內(nèi)沒什么區(qū)別，之后的每個數(shù)量級，deque花費的時間都是vector的2倍左右。
如果將deque的數(shù)據(jù)拷貝進(jìn)vector，進(jìn)行排序，排序完再將數(shù)據(jù)拷貝給deque（用assign拷貝回deque），和直接對vector中的數(shù)據(jù)排序所花費的時間，進(jìn)行比較，deque花費的時間大概是vector的1.4倍左右。文章來源：http://www.zghlxwxcb.cn/news/detail-473510.html
所以deque適合在大量頭尾存儲刪除數(shù)據(jù)的時候使用，比如stack和queue，棧和隊列使用deque比使用vector/list更合適。文章來源地址http://www.zghlxwxcb.cn/news/detail-473510.html
到了這里，關(guān)于deque(簡單介紹一下)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
