deque:雙端佇列容器(隊頭隊尾都可入,出)
底層資料結構情況
動態開辟的二維陣列,一維陣列從2開始,以2倍方式進行擴容,每次擴容后,原來第二維陣列
從新的第一維陣列的下標oldsize/2 開始存盤
如下列圖序
滿了擴容,擴容第1維,2倍擴
deque
增加:
deq.push_back(20)；從尾部添加,可能引起擴容 O(1)
deq.push_font(20); 從頭部添加, O(1)
deq.insert(iterator,20);從迭代器指向的位置加入元素 O(N)
洗掉:
deq.pop_back();//從尾部洗掉元素 O(1);
deq.pop_front();//從頭部洗掉元素O(1);
deq.erase(it);//從指向的位置洗掉元素O(n)
查詢:
用 迭代器iterator遍歷,如果涉及中間insert和erase，一定要考慮迭代器失效的問題
list：鏈表容器
底層資料結構:雙向回圈鏈表
list
增加:
mylist.push_back(20)；從尾部添加,可能引起擴容 O(1)
mylist.push_font(20); 從頭部添加, O(1)
mylist.insert(iterator,20);從迭代器指向的位置加入元素 O(1),在insert前一般要經過查詢操作，查詢操作是比較慢的,要一個一個比對
洗掉:
mylist.pop_back();//從尾部洗掉元素 O(1);
mylist.pop_front();//從頭部洗掉元素O(1);
mylist.erase(it);//從指向的位置洗掉元素O(1); 在erase前一般要經過查詢操作，查詢操作是比較慢的,要一個一個比對
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/539917.html
標籤：其他
上一篇：<一>C++ STL
下一篇：Python3.7.3環境搭建