deque

3.1定義

std::deque（雙端隊列）是C++標準模板庫（STL）中的一種容器，表示雙端隊列數據結構。它提供了在兩端高效地進行插入和刪除操作的能力。與vector的連續線性空間類似，但有所不同，deque動態地以分段連續空間組合而成的，隨時可以增加一段新的空間并鏈接起來。因此deque的迭代器并不是普通的指針；

之前提到vector的動態內存增長需要涉及到更大內存的分配；內存數據的復制；原內存空間的釋放。deque避開了vector中的反復內存搬移，但是數據結構的設計和迭代器架構卻異常復雜。deque的代碼實現量遠比vector和list多得多。

3.2deque中控器

deque微觀上看起來是連續空間，但宏觀上看，deque內部并沒有完全在一塊連續空間，而是由一段一段的連續空間構成。而這一段一段的連續空間的管理就需要一個中控器。deque采用一塊連續的“map”映射區（并不是STL中的map）來管理這些空間。其中每個元素（即一個節點）都是指針，指向一塊較大的連續的線性空間，這一塊較大的連續線性空間才是deque儲存空間的主體。

map其實是一個二級指針，T**，它是一個指針，所指之物又是一個指針，指向一塊型別為T的空間。

3.3迭代器

deque迭代器屬于最高級的隨機訪問迭代器，但是相對于vector的普通指針迭代器，deque的迭代器實現相當復雜。

deque迭代器結構：

struct _deque_iterator
{typedef __deque_iterator<T,T&,T*,BufSize> iterator;static size_t buffer_size(){return __deque_buf_size(BufSize,sizeof(T));}//保持與容器的聯結//此迭代器所指緩沖區中的當前行(current)元素T* cur;//緩沖區的頭部元素T* first;//緩沖區的尾部元素T* last;//緩沖區管理中心map_pointer node;
};

deque迭代器的關鍵成員函數：

迭代器的++,—重載都要考慮臨界的情況。

3.4數據結構

deque除了維護一個指向map的指針外，也維護兩個迭代器，start和finish，分別指向第一個緩沖區的第一個元素和最后一個緩沖區的最后一個元素（的下一個位置）。此外還有map的大小，當map用完之后，還需要重新配置一塊更大的map。

deque數據結構代碼：

template <class T,class Alloc=alloc,size_t BufSiz=0>
class deque
{
public:typedef T value_type;typedef value_type* pointer;typedef size_t size_type;...
protected://元素的指針的指針typedef pointer* map_pointer;//第一個節點iterator start;//最后一個節點iterator finish;//指向是連續空間map_pointer map;//map內指針數量size_type map_size;
}

deque的map節點的分配會以最中間開始，保證前后兩端指向可擴充的空間大小相同。

stack

stack基于LIFO（Last-In, First-Out）原則，允許在容器的末尾添加元素，并從末尾移除元素。stack其實是一個容器適配器，它是基于其他底層容器實現的。可以是 std::deque, std::list 或 std::vector。默認情況下，std::deque 被用作 std::stack 的底層容器。

stack沒有迭代器，所有元素都是先進后出的規則。



可以看到用組合的形式，使用底層容器queue的功能。

queue

std::queue 是基于FIFO（First-In, First-Out）原則的容器，允許在容器的末尾添加元素，并在容器的前端移除元素。，queue是一個適配器容器，基于底層的容器實現。并且默認情況下，std::deque 被用作 std::queue 的底層容器。std::queue 提供了隊列的基本操作，例如 push、pop 和 front，分別用于在隊尾添加元素、移除隊首元素和獲取隊首元素的值。

queue沒有迭代器。

heap

heap又叫做堆，不屬于STL的容器組件，只是優先隊列中會用到。

可以了解一下堆的排序算法：

在這里插入圖片描述

建堆的時間復雜度為：o(n)

時間復雜度 ： o(nlogn)

下標為i的節點的父節點下表：（i-1)/2

下標為i的節點的左孩子下表：i*2+1

下標為i的節點的右孩子下表：i*2+2

void sortSolution::maxHeap(vector<int>& arr, int i, int heapSize) {int l = i * 2 + 1;int r = l + 1;int largest = i;if(l < heapSize && arr[l] > arr[largest]) {largest = l;}if(r < heapSize && arr[r] > arr[largest]) {largest = r;}if(largest != i) {swap(arr[i], arr[largest]);maxHeap(arr, largest, heapSize);}
}
void sortSolution::buildMaxHeap(vector<int>& arr) {for(int i = arr.size() / 2 - 1; i >= 0; --i) {maxHeap(arr, i, arr.size()); }
}
void sortSolution::heapSort(vector<int>& arr) {buildMaxHeap(arr);for(int i = arr.size() - 1; i > 0; --i) {swap(arr[0], arr[i]);maxHeap(arr, 0, i);}
}

priority_queue

priority_queue是一個具有權值觀念的queue，它允許加入新元素、移除舊元素、審視元素值等功能。其內部的函數是按照權值進行排序的。也屬于容器適配器。

默認情況下，std::priority_queue 是一個最大堆（Max Heap），即根節點的值大于或等于其子節點的值。