基本概念
deque（double-ended queue）雙端佇列（雙端陣列）
功能
- 可分別在頭端、尾端進行插入洗掉操作
deque和vector的區別
- 相同之處
1.支持隨機訪問，迭代器均屬于random-access iterator；
2.基于中間位置的元素的移除和插入，速度都比較慢，因為要進行大量元素的移動和復制操作；
3.vector所支持的介面在deque上都能使用，且具有相同的效果， - 不同之處
1.兩端都能夠進行快速的插入和移除操作；
2.訪問deque時，內部結構會多一個間接程序，因此元素的訪問以及迭代器的動作會相比vector較慢；
3.迭代器需要在不同的區塊間進行跳轉，因此迭代器必須是smart_pointer,不能是尋常pointer；
4.Deque不支持對容量大小的控制，需要特別注意的是，除了首尾兩端，在任何地點安插或者洗掉元素都會導致pointer、reference和iterator的失效；
5.Deque重新分配記憶體優于vector，因為其內部結構顯示，deque重新分配記憶體的時候，不需要復制所有的元素；
6.Deque會釋放不需要的記憶體塊，Deque的大小是可縮減的，但是要不要這么做，如何做，取決于編譯器，
總結：顯然，deque具有vector的特性，且比vector更強大，但C++之中，更強大的功能往往意味這更大的時空開銷，如何在功能和開銷上作取舍，取決于具體應用場景
deque實作原理
記憶體結構
deque使用多段連續記憶體空間（每段記憶體空空間大小一致）來存盤資料元素，插入元素時可根據需要重新增加一段記憶體空間，
為了維護多段記憶體空間，使其在使用上如同一段連續的記憶體空間，deque設計了一個中控器map（陣列），中控器記錄著每一段記憶體空間的地址，其結構如下：
資料訪問
deque除了維護了一個中控器map；其還維護著start和finish兩個迭代器，分別指向deque的首尾；此外，還必須記錄map的大小，一旦map的空間不夠，則配置一個更大的map；還記錄了指定的記憶體段的大下，
有了以上這些資料資訊，就可以實作對多段記憶體空間的隨機訪問了，
插入操作
1、頭尾插入
- 如果備用空間足夠，就直接push進去
- 如果備用空間不足，就要考慮配置一個新的緩沖區
- 配置新緩沖區的時候， 如果map空間足夠，就直接配置一塊新的緩沖區，鏈接到map中
- 如果map空間不足，就需要考慮重新配置一塊map
2、中間插入（理解時就把deque多段記憶體看成一段連續記憶體空間）
中間插入時其實基本原理和vector一致，都需要進行元素位置的移動；只不過因為deque是雙端的，所以會根據插入元素位置前后的元素個數來決定是移動前面的元素還是移動后面的元素，
- 判斷插入位置前面元素少還是后面元素少
- 前面元素少，則把插入位置前元素進行拷貝移動
- 后面元素少，則把插入位置后元素進行拷貝移動
更多參考
deque建構式
函式原型
deque(); //默認建構式
deque(beg, end); //創建deque物件，并使用[beg,end)（前開后閉）的元素進行初始化
deque(n, elem); //創建deque物件，使用n個elem元素進行初始化
deque(const deque &deq); //拷貝建構式
deque賦值操作
//多載運算子=
deque& operator=(const deque &deq); //多載等號運算子
//assign賦值
void assign(beg, end); //將區間[beg,end)的值拷貝賦值給deque
void assign(n, elem); //將n個elem賦值給deque
deque大小
函式原型
//判斷是否為空
bool empty();
//size
size(); //回傳容器中元素的個數
resize(int num); // 重新制定容器中元素個數，若容器變長，則以默認值填充
// 如果容器變短，則超出容器長的元素被洗掉、
resize(int num, elem); // 重新制定容器中元素個數，若容器變長，則以指定值填充
// 如果容器變短，則超出容器長的元素被洗掉
deque插入和洗掉
函數原型
//頭尾操作
void push_back(elem);
void push_front(elem);
void pop_back();
void pop_front();
//insert
insert(const_iterator pos, elem); //在位置pos插入元素elem9（pos位置開始元素后移）,回傳插入資料的迭代器
insert(const_iterator pos, n, elem); //在位置pos插入n個elem，回傳插入第一元素的迭代器
insert(const_iterator pos, beg, end); //在位置pso插入區間[beg,end)的元素，回傳插入第一元素的迭代器
//erase
erase(const_iterator pos); //洗掉pos位置的元素，回傳下一個元素的位置
erase(const_iterator beg, const_iterator end); //洗掉區間[beg,end)的資料，回傳下一元素的位置
//clear
clear(); //清空容器的所有資料
deque資料存取
函式原型
//多載運算子[]
operator[]; //存取索引idx所指的資料
//at
at(int idx); //c存盤索引idx所指的資料
//前后
front(); //回傳容器的第一個元素
back(); //回傳容器的最后一個元素
deque排序操作
使用sort函式對deque進行排序
用法:
#include <algorithm>
sort(iterator beg, iterator end); //對[beg,end)區間元素進行排序
適用于所有支持隨機訪問的容器，vector,deque…
STL常用容器
常用容器
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/258999.html
標籤：區塊鏈
上一篇：TeX排版系統安裝使用