文章目錄

一、適配器

? ? ? ? ? ?1.適配器的概念：

? ? ? ? ? ? ??封裝一個已有對象，轉換其接口

? ? ? ? ? ?2.容器適配器：

? ? ? ? ? ? ? ?封裝一個已有容器對象，轉換其容器對象的接口

? ? ? ? ? ?3.容器適配器中沒有迭代器

? ? ? ? ? ? （1）行為約束，保證棧后進先出和隊列先進先出行為

? ? ? ? ? ? （2）安全保證，避免破壞內部結構，如：priority_queue的堆序性

? ? ? ? ? ?4.適配器模式：

? ? ? ? ? ? ? 封裝舊對象 + 接口轉換層

? ? ? ? ? ? ? 適配器模式體現封裝和代碼的復用

二、stcak模擬實現

? ? ? ? ? ?1.stcak棧頂出入數據，后進先出

? ? ? ? ? ?2.stack的底層可以是數組結構也可以是鏈式結構

? ? ? ? ? ? ? 而stack的接口只需要保證擁有push，pop，top...等操作以及保證后進先出

? ? ? ? ? ? ? 棧頂出入數據

? ? ? ? ? ? （1）棧的底層可以是數組也可以是鏈表，跟vector和list的底層一樣

? ? ? ? ? ? （2）棧的接口push，pop，top...等操作的行為，vector和list中也擁有

? ? ? ? ? ? （3）（1） + （2）表明棧的實現可以封裝一個·vector/list容器的對象

? ? ? ? ? ? ? ? ? ? ?在棧的接口中轉換vector/list的接口，實現代碼的復用

? ? ? ? ? ? （4）實現棧的邏輯 == 封裝一個已有的容器對象 + 轉換其容器對象的接口

? ? ? ? ? ? ? ? ? ? ?所以棧為容器適配器

? ? ? ? ?3.stack模擬實現

? ? ? ? ?4.根據出棧的時機不同，出棧的順序也會不一樣? ? ? ? ? ?

三、queue模擬實現

? ? ? ? ? ?1.隊尾入數據，隊頭出數據，先進先出

? ? ? ? ? ?2.?queue的底層可以為鏈式結構

? ? ? ? ? ? ???而queue的接口只需要保證擁有push，pop，top...等操作以及保證先進先出

? ? ? ? ? ? ? ?隊尾入數據，隊頭出數據

? ? ? ? ? ? （1）隊列的底層可以是鏈表，跟list的底層一樣

? ? ? ? ? ? （2）隊列的接口push，pop，top...等操作的行為，list中也擁有

? ? ? ? ? ? （3）（1） + （2）表明隊列的實現可以封裝一個list容器的對象

? ? ? ? ? ? ? ? ? ? ?在隊列的接口中轉換list的接口，實現代碼的復用

? ? ? ? ? ? （4）實現隊列的邏輯 == 封裝一個已有的容器對象 + 轉換其容器對象的接口

? ? ? ? ? ? ? ? ? ? ?所以對列為容器適配器

? ? ? ? ? ? （5）queue之所以不支持數組結構也就是vector原因是數組結構頭部刪除需要挪動數據

? ? ? ? ? 3.queue模擬實現

? ? ? ? ?4. 無論出隊列的時機如何，出隊列的順序都是一致的

?四、vector和list的優缺點

? ? ? ? ? ? ?1.vector

? ? ? ? ? ? ? ? 優點：

? ? ? ? ? ? ? （1）支持[]下標訪問，速度效率快

? ? ? ? ? ? ? （2）cpu高速緩存命中率高

? ? ? ? ? ? ? （3）內存利用效率高，不存在為存儲指針開辟內存

? ? ? ? ? ? ? （4）尾插尾刪效率高，插入只需要在尾部增添數據，刪除只需要--_size

? ? ? ? ? ? ? ???缺點：

? ? ? ? ? ? ? （1）頭部中間位置插入刪除效率低，因為要挪動數據

? ? ? ? ? ? ? （2）空間不足需要擴容，而c++的擴容又都是異地擴容

? ? ? ? ? ? ? ? ? ? ?（開辟一塊新空間，拷貝舊空間的數據，釋放舊空間）

? ? ? ? ? ? ? ? ? ? ? ? 擴容代價高

? ? ? ? ? ? ?? （3）存在空間的浪費，比如：當前空間為100，有效數據個數為100

? ? ? ? ? ? ? ? ? ? ? ??此時插入一個新數據，需要擴容至200，之后便不再使用該vector

? ? ? ? ? ? ? ? ? ? ? ? 那么就會浪費99個數據的空間

? ? ? ? ? ? ? 2.list

? ? ? ? ? ? ? ? ?優點：

? ? ? ? ? ? ? ?（1）任意位置的插入刪除效率高，不需要挪動數據，只需要更改結點中的指針的指向

? ? ? ? ? ? ? ?（2）不存在擴容和浪費空間，存儲多少個數據那么舊申請多少個結點

? ? ? ? ? ? ? ? ??缺點：

? ? ? ? ? ? ? ? （1）不支持[]下標訪問，如果需要一下子跳躍很多數據，效率低

? ? ? ? ? ? ? ? （2）cpu高速緩存命中率低

? ? ? ? ? ? ? ? （3）內存利用效率低，因為結點中存儲上一個結點和下一個結點的指針

? ? ? ? ? ? ? ?3.vector的優點就是list的缺點，list的優點就是vector的缺點

? ? ? ? ? ? ? ? ??vector和list屬于互補的關系

? ? ? ? ? ? ? ?4.cpu高速緩存命中率

? ? ? ? ? ? ? ? （1）數據是存儲在內存當中的，內存的速度跟不上cpu的速度

? ? ? ? ? ? ? ? （2）當cpu需要處理數據時，正因為內存的速度跟不上cpu的速度

? ? ? ? ? ? ? ? ? ? ? ? ?所以cpu不會直接去內存中獲取數據，而是向緩存中獲取數據

? ? ? ? ? ? ? ?（3）如果cpu向緩存中獲取數據成功，那么就稱作cpu高速緩存命中成功

? ? ? ? ? ? ? ? ? ? ? ? 如果cpu向緩存中獲取數據失敗，那么就稱作cpu高速緩存命中失敗

? ? ? ? ? ? ? ? （4）如果cpu向緩存中獲取數據失敗，那么緩存就會向內存中獲取該數據

? ? ? ? ? ? ? ??? ? ? ? ?然后cpu再向緩存中獲取數據

? ? ? ? ? ? ? ? （5）緩存向內存獲取數據，并不是只將該數據拷貝到緩存

? ? ? ? ? ? ? ? ? ? ? ? ? 而是將該數據及該數據附近位置的數據全部拷貝到緩存

? ? ? ? ? ? ? ? 5.vector cpu高速緩存命中率高正是因為底層是數組結構，數組物理地址空間是連續的

? ? ? ? ? ? ? ? ? ?如果首次cpu高速緩存命中失敗，緩存向內存中拷貝該數據時，就會將數組附近都拷貝

? ? ? ? ? ? ? ? ? ?到緩存當中，那么接下來cpu訪問的數組的數據時，大部分都會直接命中

? ? ? ? ? ? ? ? ? ?list cpu高速緩存命中率低正是因為底層是鏈式結構，物理地址空間是不連續的

? ? ? ? ? ? ? ? ? ?如果首次cpu高速緩存命中失敗，緩存向內存拷貝該數據時，會將該數據物理空間地址

? ? ? ? ? ? ? ? ? ?連續的一部分拷貝到緩存，可是鏈表的物理空間地址是不連續的，所以拷貝到緩存中

? ? ? ? ? ? ? ? ? ?是否有下一個結點的數據是不可知的，那么當繼續訪問鏈表的數據，就又會產生命中

? ? ? ? ? ? ? ? ? ?失敗緩存再次區內存中拷貝該數據及其物理空間地址附近的數據

五、deque

? ? ? ? ? ? ? ? 1.deque的使用

? ? ? ? ? ? ? ? ? ?通過觀察deque的接口可以發現，deque支持頭部尾部的插入刪除

? ? ? ? ? ? ? ? ? ?也支持[]下標訪問，特別像是vector和list的融合體?

? ? ? ? ? ? ? ? 2.vector的優點就是list的缺點，list的優點就是vector的缺點

? ? ? ? ? ? ? ? ? ?那么有沒有一種數據結構，使得頭部尾部的插入刪除效率高，支持[]下標訪問，

? ? ? ? ? ? ? ? ? ?cpu高速緩存命中率高

? ? ? ? ? ? ? ? ? ?那么就是deque

? ? ? ? ? ? ? ? 3.deque正是結合了vector和list的優點而產生的

? ? ? ? ? ? ? ? 4.deque的底層結構

? ? ? ? ? ? ? ? ? ? （1）deque的成員變量為一個數組指針

? ? ? ? ? ? ? ? ? ? （2）該成員變量指向一個中控數組

? ? ? ? ? ? ? ? ? ? （3）中控數組又是一個存儲指針的數組，存儲著每一個buffer數組的指針?

? ? ? ? ? ? ? ? ? ? （4）當存儲數據的空間不足時，只需要新增一個buffer數組，不需要擴容和拷貝數據

? ? ? ? ? ? ? ?? ? ? ? ? ? ? 只有當中控數組滿了時，才需要對中控數組進行擴容，當然中控數組中存儲的

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?是指針，擴容拷貝的代價不會太大，并且中控數組擴容的次數還會比較少

? ? ? ? ? ? ? ? ? ? （5）因為每一個buffer數組都比較小，所以不會出現浪費太多空間的場景

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?假設一個buffer大小為n，插入了x個數據，那么也只會浪費n - x個空間

? ? ? ? ? ? ? ? 5.deque的迭代器? ? ? ? ? ? ? ?（1）cur是指向當前迭代器所在的buffer數組中的元素的指針 T*

? ? ? ? ? ? ? ?（2）first是指向當前迭代器所在的buffer數組中起始位置的指針 T*

? ? ? ? ? ? ? ?（3）last是指向當前迭代器所在的buffer數組中最后一個數據的下一個位置的指針 T*? ?

? ? ? ? ? ? ? ?（4）node是指向當前迭代器所在的buffer數組在中控數組中位置的指針 T**

? ? ? ? ? ? ? ? ? ? ? ? 中控數組中存儲的是buffer數組的起始地址，也就是T*

? ? ? ? ? ? ? ? ? ? ? ? 那么指向中控數組中位置的指針就是T**

? ? ? ? ? ? ? ? ? ? ? ? 首先指向中控數組中的位置，那么就是一個指針需要一個*

? ? ? ? ? ? ? ? ? ? ? ? 而中控數組中的數據類型又是T*，所以主席昂中控數組中位置的指針為T**

? ? ? ? ? ? ? ? ?6.deque的遍歷? ? ? ? ? ? ? ? ?? ? ? ? ? ? （1）start表示第一個有效數據的迭代器? ? ? ? ? ? ? ? ? ==? ?begin（）

? ? ? ? ? ? （2）finish表示最后一個有效數據下一個位置的迭代器? ==? ?end（）

? ? ? ? ? ? （3）判斷兩個迭代器是否相等(!=)

? ? ? ? ? ? ? ? ? ? ?只需要比較cur就可以

? ? ? ? ? ? ? ? ? ? ?因為不同buffer中的cur不相等，相同buffer中不同位置的數據的cur不相等

? ? ? ? ? ? ? ? ? ? ?而迭代器相等是指相同buffer中的相同位置

? ? ? ? ? ? ? ? ? ? 所以!=子需要比較cur

? ? ? ? ? ? （4）*解引用

? ? ? ? ? ? ? ? ? ? ?*解引用只需要解引用cur就可以了

? ? ? ? ? ? ? ? ? ? ? 因為cur是指向當前迭代器所在的buffer數組中的元素的指針 T*

? ? ? ? ? ? （5）++迭代器

? ? ? ? ? ? ? ? ? ? ? 本質上就是++cur，但是當cur == last表明當前buffer數組已經遍歷完畢

? ? ? ? ? ? ? ? ? ? ? 需要跳轉到下一個buffer數組，而要跳轉到下一個buffer數組只需要++node

? ? ? ? ? ? ? ? ? ? ? 因為node是指向當前迭代器所在的buffer數組在中控數組中位置的指針

? ? ? ? ? ? ? ? ? ? ? 指向中控數組中位置的指針，++就是中控數組的下一個位置的指針

? ? ? ? ? ? ? ? ? ? ? 此時*node就為新的buffer數組的起始位置的指針

? ? ? ? ? ? ? ? ? ? ? 緊接著以此更新first，cur，last就可以得到新的buffer數組中第一個有效元素

? ? ? ? ? ? ? ? ? ? ? 的迭代器

? ? ? ? ? ?7.deque的尾插尾刪

? ? ? ? ? ? （1）deque的尾插尾刪是借組finish迭代器實現的

? ? ? ? ? ? ? ? ? ?（最后一個有效數據的下一個位置的迭代器）

? ? ? ? ? ? （2）如果finish中的cur != last，那么就在finish迭代器中cur位置插入

? ? ? ? ? ? ? ? ? ? ?然后更新finish

? ? ? ? ? ? ? ? ? ? ?如果finish中的cur == last，那么就增加新的buffer，將新的buffer的地址交給

? ? ? ? ? ? ? ? ? ? ?中控數組，如果中控數組滿了，那么就有涉及到中控數組擴容的問題，假設

? ? ? ? ? ? ? ? ? ? ?中控數組沒有滿，那么將新的buffer的地址交給中控數組，在新的buffer數組中

? ? ? ? ? ? ? ? ? ? ?插入數據，更新finish

? ? ? ? ? ?（3）尾刪直接更新finish中的cur，--cur就可以，更新finish

? ? ? ? ? ? ? ? ? ? 如果--cur == first，那么就表明該buffer數組就空了，釋放掉該buffer數組，

? ? ? ? ? ? ? ? ? ? 更新finish以及中控數組? ? ? ? ? ??

? ? ? ? ? ?

? ?8.deque的頭插頭刪

? ? （1）deque的頭插頭刪是借助start迭代器來實現的

? ? ? ? ? ??（第一個有效數據位置的迭代器）

? ? （2）如果cur != first，那么直接在--cur的位置插入數據，更新start就可以了

? ? ? ? ? ? ?如果cur == first，那么表示該buffer數組頭部位置已經滿了無法在該buffer數組進行頭插

? ? ? ? ? ? ?那么就需要新增一個buffer數組，將buffer數組的起始地址交給中控數組，如果中控數組

? ? ? ? ? ? ?滿了那么就需要對中控數組進行擴容，此時假設中控數組沒有滿，那么緊接著在新增的

? ? ? ? ? ? ? buffer數組的最后一個位置進行插入，更新start迭代器

? ?（3）頭刪直接對start迭代器進行++cur，然后更新start迭代器

? ? ? ? ? ??如果++cur == first，表示此時該buffer數組為空，那么就需要釋放該buffer數組，在中控

? ? ? ? ? ? 數組中刪除該buffer數組的地址，然后更新start迭代器

? ? ? ? ?9.+=運算符重載，[]運算符重載

? ? ? ? ? （1）+=運算符重載依靠迭代器實現，[]運算符重載依靠+=實現? ??

? ? ? ? （2）n = n + (cur - first)

? ? ? ? ? ? ? ? ?是擔心第一個buffer頭部不是滿的，所以cur - first == 起始位置到第一個有效數據之間

? ? ? ? ? ? ? ? ?相差多少數據，以此來糾正n?

? ? ? ?（3）int x = n / 8 == 得到+=i之后buffer會跳轉到從現在buffer開始的第幾個buffer

? ? ? ?（4）int y = n % 8?== 得到+=i之后的buffer中下標為y位置的數據

? ? ? ?（5）node += x就可以直接得到最終的buffer

? ? ? ?（6）接下來就是更新迭代器，cur = first + y 就可以得到最終buffer中下標為y的元素的地址

六、deque的優缺點?

? ? ? ? ?1.優點

? ? ? ? ? （1）支持[]下標訪問，效率還不錯

? ? ? ? ? （2）cpu高速緩存命中率不錯

? ? ? ? ? （3）內存使用效率高

? ? ? ? ? （4）擴容也只是針對于中控數組的擴容代價低

? ? ? ? ? （5）浪費空間少，最多浪費buff - 1個空間

? ? ? ? ? （6）頭部，尾部是插入刪除效率高

? ? ? ? ? 2.缺點

? ? ? ? ? ?（1）中部位置插入刪除效率低，因為要挪動數據

? ? ? ? ? ?（2）迭代器遍歷效率低，雖然看著不錯，但是相比vector和list迭代器相差甚遠

? ? ? ? ? ?（3）只是為了最大程度的融合vector和list的優點，導致deque像是一個四不像

? ? ? ? ? ? ? ? ? ? ?[]效率不及vector，cpu高速緩存命中率也不如vector

? ? ? ? ? ? ? ? ? ? ?中間位置的插入刪除不如list

七、deque為什么作為stack和queue的默認適配容器

? ? ? ? ? ? ?1.stack只注重棧頂的插入刪除，而deque一端的插入刪除效率都很高

? ? ? ? ? ? ? ? 并且使用deque沒有數據的擴容和空間浪費

? ? ? ? ? ? ?2.queue注重隊尾入數據和隊頭出數據，而deque兩端的插入刪除效率都很高

? ? ? ? ? ? ? ? ?并且使用deque可以更高效的使用內存，就不會在內存中存儲很多指針

? ? ? ? ? ? ?3.stack和queue都是容器適配器，容器適配器是沒有迭代器的

? ? ? ? ? ? ? ? ?stack和queue是不可以進行遍歷的，所以deque迭代器的缺點也不會展現出來

? ? ? ? ? ? ? 4.所以deque才作為stack和queue的適配容器? ? ? ? ? ? ?