deque

• 雙端隊列可以在頭部和尾部進行插入刪除操作
• 與vector相比，頭插效率高，不需要搬移元素
  與list相比，空間利用率高

deque邏輯上空間是連續(xù)的，物理上并不是，是由一段段小空間拼接而成的

雙端隊列的迭代器比較復(fù)雜

• cur：指向空間中被遍歷的那個元素
• first：指向空間開始
• last：指向空間末尾
• node：指向map中保存該段空間的地址
  當(dāng)cur走到first或者last位置，說明已經(jīng)將該空間中的元素遍歷結(jié)束，需要找下一塊空間（node++或者–）

容器適配器

C語言中，棧封裝數(shù)組，隊列封裝鏈表，
C++中，棧和隊列使用deque實現(xiàn)
原因：vector中的擴容成本高，list中有大量節(jié)點，造成很多內(nèi)存碎片

容器適配器是將一個接口轉(zhuǎn)換成另外一種接口，這樣解釋確實過于簡單，

• 先要知道，deque中定義了許多的接口如頭插頭刪，尾插尾刪，判空等操作，
• 這些操作不管是棧中特性函數(shù)，還是隊列中的特性函數(shù)，deque中都有
• 若實現(xiàn)stack，stl把deque作為stack的底層，抽出deque中的部分方法，
• 比如尾插尾刪，判空，返回隊尾元素，進行包裝從而實現(xiàn)棧；尾插尾刪函數(shù)變成出棧入棧函數(shù)，返回隊尾元素函數(shù)變成返回棧頂元素函數(shù)

迭代器適配器：list反向迭代器的實現(xiàn)，封裝了正向迭代器(抽出正向迭代器中的方法重新進行封裝)

仿函數(shù)

仿函數(shù)又稱函數(shù)對象（可以像函數(shù)一樣調(diào)用的對象稱為函數(shù)對象）
實現(xiàn)：在類中將函數(shù)調(diào)用運算符() 重載，該類的對象就可以像函數(shù)一樣使用

重載()后，通過less類定義的對象，去調(diào)用成員函數(shù)

優(yōu)先級隊列(仿函數(shù)與容器適配器的應(yīng)用)

封裝vector實現(xiàn)

• 優(yōu)先級隊列本質(zhì)是堆
• 堆是完全二叉樹+條件（父節(jié)點比孩子節(jié)點大或者?。?br> 完全二叉樹適合用數(shù)組存儲
  所以優(yōu)先級隊列的底層是用vector來存儲元素

適配器詳述

• 103行，vector是一個類模板，用int將該模板實例化，所以vector< int >是一個實際類型，將這個類型名用container代替，并用新類型名定義一個變量
• 優(yōu)先級隊列的pop函數(shù)是使用vector中的pop作為核心邏輯，并添加新邏輯而實現(xiàn)的
• 添加新的函數(shù)，向上調(diào)整和向下調(diào)整函數(shù)
• 組成了新容器的接口，把這種容器稱為容器適配器

所以stack和queue嚴(yán)格說并不是容器，而是容器適配器

仿函數(shù)詳述

仿函數(shù)又稱函數(shù)對象（可以像函數(shù)一樣調(diào)用的對象稱為函數(shù)對象）
實現(xiàn)：在類中將函數(shù)調(diào)用運算符重載，該類的對象就可以像函數(shù)一樣使用
函數(shù)調(diào)用運算符就是 ( )

通俗來說就是把函數(shù)封裝到類里面，要使用該函數(shù)時，只需要定義一個這個類的對象，通過對象調(diào)用運算符重載函數(shù)，使用該功能

代碼84~100行是實現(xiàn)兩個不同比較方式的仿函數(shù)，同容器適配器一樣，在類模板參數(shù)列表中重命名，112行定義類對象，117行是對象調(diào)用（）運算符重載函數(shù)，將括號中的兩個參數(shù)傳給類中的成員函數(shù)

sort中仿函數(shù)的應(yīng)用

sort是一個函數(shù)模板

• sort的三個參數(shù)，前兩個參數(shù)是待排序的區(qū)間，第三個參數(shù)是排序方式
• 而sort是一個函數(shù)，參數(shù)是普通變量
• 仿函數(shù)是一個類型，第三個參數(shù)不能傳類型，
  所以仿函數(shù)要想作為sort函數(shù)的參數(shù)，需要這樣寫
• 后面加()表面這個類產(chǎn)生了一個匿名對象

而arr是指針變量，迭代器的本質(zhì)又是指針，所以可以推出arr就是一個迭代器對象文章來源地址http://www.zghlxwxcb.cn/news/detail-602600.html

到了這里，關(guān)于STL：雙端隊列&容器適配器&仿函數(shù)&優(yōu)先級隊列的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！