<三>deque容器和list容器

deque:雙端隊列容器(隊頭隊尾都可入,出)
底層數據結構情況
動態開闢的二維數組,一維數組從2開始,以2倍方式進行擴容,每次擴容後,原來第二維數組
從新的第一維數組的下標oldsize/2 開始存儲
如下列圖序

滿了擴容,擴容第1維,2倍擴

deque deq;
增加:
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;
增加:
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前一般要經過查詢操作，查詢操作是比較慢的,要一個一個比對