目錄

stack的介紹和使用

stack的使用

queue的介紹和使用

queue的使用

容器適配器

deque的介紹

deque的缺陷

priority_queue的介紹和使用

priority_queue的使用

仿函數

反向迭代器

---

stack的介紹和使用

在原來的數據結構中已經介紹過什么是棧了，再來回顧一下:

1. stack是一種容器適配器（關于什么是容器適配器之后下面會講到），專門用在具有后進先出操作的上下文環境中，其刪除只能從容器的一端進行元素的插入與刪除操作。
2. stack是作為容器適配器被實現的，容器適配器是對特定類封裝作為其底層的容器，并提供一組特定的成員函數來訪問其元素，將特定類作為其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出。
3. stack的底層容器可以是任何標準的容器類模板或者一些其他特定的容器類。
4. 標準容器vector、deque、list均符合這些需求，默認情況下，如果沒有為stack指定特定的底層容器，默認情況下使用deque（這個后面也會講）。

stack的使用

函數說明	接口說明
stack();	構造空的棧
bool empty() const;	檢測stack是否為空
size_t size() const;	返回stack中元素的個數
value_type& top();	返回棧頂元素的引用
void push(const value_type& val);	將元素val壓入stack中
void pop();	將stack中尾部的元素彈出

這些接口的使用都非常簡單，也不再過多說明。

---

queue的介紹和使用

1. 隊列也是一種容器適配器，專門用于在FIFO上下文(first in first out 先進先出)中操作，其中從容器一端插入元素，另一端刪除元素。
2. 隊列作為容器適配器實現，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數來訪問其元素。元素從隊尾入隊列，從隊頭出隊列。

3. 底層容器可以是標準容器類模板之一，也可以是其他專門設計的容器類。

4. 標準容器類deque和list滿足了這些要求。默認情況下，如果沒有為queue實例化指定容器類，則使用標準容器deque。

queue的使用

函數聲明	接口說明
queue();	構造空的隊列
bool empty() const;	檢測隊列是否為空
size_t size() const;	返回隊列中有效元素的個數
value_type& front();	返回隊頭元素的引用
value_type& back();	返回隊尾元素的引用
void push(const value_type& val);	在隊尾將元素val入隊列
void pop();	將隊頭元素出隊列

---

容器適配器

????????適配器是一種設計模式(設計模式是一套被反復使用的、多數人知曉的、經過分類編目的、代碼設計經驗的總結)，該種模式是將一個類的接口轉換成客戶希望的另外一個接口。

????????雖然stack和queue中也可以存放元素，但在STL中并沒有將其劃分在容器的行列，而是將其稱為容器適配器，這是因為stack和隊列只是對其他容器的接口進行了包裝，STL中stack和queue默認使用deque。

---

deque的介紹

????????deque(雙端隊列)：是一種雙開口的"連續"空間的數據結構，雙開口不僅可以在頭尾兩端進行插入和刪除操作，而且時間復雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高。

????????deque并不是真正連續的空間，而是由一段段連續的小空間拼接而成的，實際deque類似于一個動態的二維數組，其底層結構如下圖所示：

????????從網上找了一張圖片，雙端隊列底層是一段假象的連續空間，實際是分段連續的，為了維護其“整體連續”以及隨機訪問的假象，落在了deque的迭代器身上，因此deque的迭代器設計就比較復雜。

????????圖中的cur指向當前數據，first和last表示buffer開始和結束，node反向指向中控器，方便找下一個buffer。

deque的缺陷

????????與vector相比，deque的優勢是：頭插和頭刪時，不需要搬移元素，效率高，而且在擴容時，也不需要搬移大量的元素，因此其效率比vector高的。

????????與list比較，其底層是連續空間，空間利用率比較高，不需要存儲額外字段。

????????但是，deque有一個致命缺陷：不適合遍歷，因為在遍歷時，deque的迭代器要頻繁的去檢測其是否移動到某段小空間的邊界，導致效率低下；中間插入刪除效率不高。而序列式場景中，可能需要經常遍歷，因此在實際中，需要線性結構時，大多數情況下優先考慮vector和list，deque的應用并不多，而目前能看到的一個應用就是，STL用其作為stack和queue的底層數據結構。

?

結論：

1. 頭尾插入刪除非常適合，相比于vector和list，更適合做stack和queue的默認適配器。
2. 中間插入刪除多，使用list。
3. 隨機訪問多，使用vector。

---

priority_queue的介紹和使用

priority_queue是優先級隊列

1. 優先隊列是一種容器適配器，根據嚴格的弱排序標準，它的第一個元素總是它所包含的元素中最大的。
2. 類似于堆，在堆中可以隨時插入元素，并且只能檢索最大堆元素(優先隊列中位于頂部的元素)。
3. 優先隊列被實現為容器適配器，容器適配器即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數來訪問其元素。元素從特定容器的“尾部”彈出，其稱為優先隊列的頂部。
4. 底層容器可以是任何標準容器類模板，也可以是其他特定設計的容器類。容器應該可以通過隨機訪問迭代器訪問。
5. 標準容器類vector和deque滿足這些需求。默認情況下，如果沒有為特定的priority_queue類實例化指定容器類，則使用vector。?
6. 需要支持隨機訪問迭代器，以便始終在內部保持堆結構。容器適配器通過在需要時自動調用算法函數make_heap、push_heap和pop_heap來自動完成此操作。

priority_queue的使用

????????優先級隊列默認使用vector作為其底層存儲數據的容器，在vector上又使用了堆算法將vector中元素構造成堆的結構，因此priority_queue就是堆，所有需要用到堆的時候，都可以考慮使用priority_queue。注意：默認情況下priority_queue是大堆。

函數聲明	接口說明
priority_queue();	構造一個空的優先級隊列
bool empty() const;	檢測優先級隊列是否為空
const value_type& top() const;	返回優先級隊列中堆頂元素
void push(const value_type& x)	在優先級隊列中插入x
void pop()	刪除優先級隊列中的堆頂元素

template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type>>
class priority_queue; // 第一個模板參數是隊列中的元素類型，第二個是用什么容器，第三個決定是大堆還是小堆

---

仿函數

? ? ? ? 仿函數，有點地方也叫做函數對象，這其實就是一個類，這個類重載了一個operator()。

class less
{operator()(const int& l, const int& r){public:return l < r;}
};int main()
{less fun; // 這里的fun并不是一個函數，而是一個類對象，可以像函數一樣使用fun(1, 2); // 它的本質是在調用fun.opeartor()(1, 2)，所以這里返回值應該是1return 0;
}

// 所以這樣好用的不該拘泥于整型，可以改成模板
template<class T>
class less
{operator()(const T& l, const T& r) const{public:return l < r;}
};// 既然有小于，就有大于
template<class T>
class greater
{operator()(const T& l, const T& r) const{public:return l > r;}
};int main()
{less<int> fun1;fun1(1, 2);greater<int> func2;func2(2, 1);return 0;
}

int main()
{// 使用優先級隊列，顯示傳第三個模板參數就是這樣的，默然就是大堆，想要建小堆就改成greater<int>priority_queue<int, vector<int>, less<int>> pq;// 當然要注意的是，這里傳入的是類型，相比于sort函數，傳入的是對象，這就可以使用匿名對象vector<int> v(5, 5);sort(v.begin(), v.end(), less<int>()); // sort默認排的升序，想要降序就傳入greater<int>()return 0;
}

---

反向迭代器

????????前面講到了正向迭代器的使用，那也要說一下反向迭代器的實現，反向迭代器是一種反向遍歷容器的迭代器。也就是，從最后一個元素到第一個元素遍歷容器。反向迭代器將自增(和自減)的含義反過來了：對于反向迭代器，++運算將訪問前一個元素，而 - -運算則訪問下一個元素。

// 復用，迭代器適配器
template<class Iterator, class Ref, class Ptr>
struct __reverse_iterator
{iterator _cur; // 使用正向迭代器構造一個反向迭代器typedef __reverse_iterator<Iterator> RIterator;__reverse_iterator(Iterator it):_cur(it){}RIterator operator++() // 注意這里只有前置++和--，后置是差不多的{--_cur;return *this;}RIterator operator--(){++ _cur;return *this;}Ref operator*() // 返回引用類型{auto tmp = _cur;--tmp;return *tmp;// 這里這么寫的原因是，begin返回第一個位置的迭代器，end返回最后一個位置的迭代器// rbegin返回最后一個位置的迭代器，rend返回第一個位置前一個的迭代器// 寫的時候可以復用begin和end，rbegin返回end位置，rend返回begin位置// 這里的cur就是構造的反向迭代器，先--后就是正確的位置}Ptr opeartor->() // 返回指針{// return _cur.operator->();return &(operator*());}bool operator!=(const RIterator& it){return _cur != it._cur;}
};

????????這樣可以適配生成某些容器的反向迭代器，有些容器比較特殊，所以不支持，比如單鏈表forward_list，它只支持++并不支持- -；unordered_map和unordered_set也是不支持的，這就要到后面再說了。

? ? ? ? 從某些功能的角度分析，迭代器也可以分成幾類：

• forward_iterator，它只支持++，因為它是單向的。容器有：unordered_map，unordered_set，forward_list。
• bidirectional_iterator，它支持++和- -，它是雙向的。容器有：list，map，set。
• random_access_iterator，它不僅支持++和- -，還支持+和-，他是隨機的。容器有：deque，vector。

????????這里的迭代器從下到上是一種繼承關系，關于什么是繼承后面也會講。簡單理解一下，隨機迭代器也是雙向的，拿sort函數和reverse函數舉例，sort函數接口的參數類型就是隨機迭代器的，reverse函數接口就是雙向的，但是可以用隨機類型的容器調用reverse這個函數；相對的，雙向類型的容器就不能調用sort這個函數。vector可以調用reverse函數，list不能調用sort函數（algorithm庫中的）。