合肥那個公司做網站優(yōu)化好,網站模板之家免費下載,深圳龍華區(qū)郵政編碼,權威發(fā)布是什么意思目錄前言一、stack的模擬實現(xiàn)1.1 適配器Container的封裝概念二、queue的模擬實現(xiàn)三、deque的介紹3.1 deque的使用3.2 CPU高速緩存訪問命中率與數據訪問效率3.2.1 數據訪問效率3.2.2 CPU高速緩存訪問命中率結語#x1f3ac; 云澤Q#xff1a;個人主頁#x1f525; 專欄傳送入…目錄前言一、stack的模擬實現(xiàn)1.1 適配器Container的封裝概念二、queue的模擬實現(xiàn)三、deque的介紹3.1 deque的使用3.2 CPU高速緩存訪問命中率與數據訪問效率3.2.1 數據訪問效率3.2.2 CPU高速緩存訪問命中率結語 云澤Q個人主頁 專欄傳送入口: 《C語言》《數據結構》《C》《Linux》《藍橋杯系列》??遇見安然遇見你不負代碼不負卿~前言大家好啊我是云澤Q歡迎閱讀我的文章一名熱愛計算機技術的在校大學生喜歡在課余時間做一些計算機技術的總結性文章希望我的文章能為你解答困惑~一、stack的模擬實現(xiàn)對于一般人來說模擬實現(xiàn)的棧的底層就是一個數組讓數組尾部做棧頂。無論是數組棧還是鏈式棧很多的東西都是和順序表和鏈表是類似的但是STL中的棧不是這樣實現(xiàn)的STL在設計初的考量就是相似的一些東西直接復用像實現(xiàn)一個數組棧直接如圖封裝一個vector實現(xiàn)就不用再實現(xiàn)順序表和鏈表的內部的一些邏輯了。1.1 適配器Container的封裝概念且C設計STL的這些大佬的思路還更開闊一些他們還加入了一種叫做容器適配器Container轉換的意思的東西這樣封裝適配器的思路是非常牛的“自己從頭實現(xiàn)棧” 的寫法比如注釋里的T* _a_top_capacity—— 需要自己管理動態(tài)數組的擴容、釋放而現(xiàn)在這個stack是“復用現(xiàn)有容器比如vector/list的功能包裝成棧的接口”底層存儲完全交給Container比如vector自己只封裝 “棧需要的操作”push/pop/top 等。這種適配結構的核心優(yōu)點【少寫重復代碼】復用現(xiàn)有容器不用自己實現(xiàn)底層存儲原來注釋里的 “數組?！?需要自己寫動態(tài)數組的初始化、擴容比如_capacity滿了要realloc內存的釋放防止內存泄漏下標訪問、邊界檢查等。而現(xiàn)在的stack直接用vector/list作為底層容器 —— 這些容器本身已經實現(xiàn)了動態(tài)擴容、內存管理、尾插 / 尾刪等功能你只需要調用_con.push_back()/_con.pop_back()相當于 “站在現(xiàn)有容器的肩膀上”不用重復造輪子?！眷`活切換場景】換底層容器只改模板參數不用動棧的邏輯代碼里用的是vector int 作為底層yunze::stackint, vector int 但如果場景變了比如需要 “頻繁在棧頂插入 / 刪除且不想承擔vector擴容的開銷”—— 只需要把模板參數換成list int 代碼改成yunze::stackint,listintst;// 底層變成鏈表其他代碼完全不用改st.push(1);// 還是用同樣的push接口st.top();// 還是用同樣的top接口底層容器換了但棧的調用代碼完全不用改—— 因為stack封裝了統(tǒng)一的接口不管底層是vector還是list對外都是 “棧的操作”?！窘y(tǒng)一接口】不用關心底層實現(xiàn)只用記 “棧的用法”不管底層是vector數組還是list鏈表你用這個stack時只需要調用push/pop/top—— 不用關心底層是 “數組尾插” 還是 “鏈表尾插”也不用記vector的push_back或list的push_back細節(jié)只需要記 “棧的標準操作” 即可降低了學習和使用的成本?！痉€(wěn)定可靠】借現(xiàn)有容器的成熟性減少 bugSTL 里的vector/list是經過大量測試、優(yōu)化的容器比自己寫的 “數組?！北热缱⑨尷锏腡* _a更穩(wěn)定比如vector的擴容邏輯是經過性能優(yōu)化的通常是 2 倍擴容減少頻繁申請內存的開銷list的尾插 / 尾刪是 O (1) 且不會有內存碎片問題這些容器本身也做了邊界檢查比如empty()時調用back()會報錯。用它們作為底層比自己手寫的存儲結構更不容易出 bug?！具m配多類型】底層容器支持的類型棧都能直接用比如你想存string類型的棧只需要寫yunze::stackstring,vectorstringst;st.push(hello);coutst.top()endl;// 輸出hello因為vector string 本身支持string類型你的stack不需要額外寫任何代碼直接適配所有Container支持的類型。看到這里可能看著該全新的寫法還有一些疑問下面再看一下具體的模板參數實例化和函數調用過程庫中的STL還支持使用缺省參數deque一個容器deque既不是一個數組棧也不是一個鏈式棧而是一個雙端隊列適配出來的棧雙端隊列不要求先進先出其在功能上是list和vector的融合體二、queue的模擬實現(xiàn)隊列是隊尾入數據隊頭出數據也可以在queue的類中用erase代替pop_front();vector不支持直接頭刪但是erase是支持頭刪的但是這就讓效率強行降低了STL中的vector設計之初沒有直接支持頭刪接口的原因就是希望少用功能上還是支持的voidpop(){_con.erase();}三、deque的介紹deque雙端隊列是一種雙開口的“連續(xù)”空間的數據結構雙開口的含義是可以在頭尾兩端進行插入和刪除操作且時間復雜度為O1也可以在中間任意位置插入刪除與vector比較頭插效率高不需要搬移元素與list比較空間利用率比較高其在功能上是list和vector的融合體接口和list和vector的接口都基本是類似的3.1 deque的使用僅管從功能上看deque好像可以替代vector和list但是在實際情況下是不可以的如果可以的話STL就沒有vector和list兩個容器了deque更像是一個有著很好的設計初衷為了解決vector和list的問題但實際成品沒有達到預期的一個容器但是其也有很多可取之處下圖是vector和list的優(yōu)缺點3.2 CPU高速緩存訪問命中率與數據訪問效率3.2.1 數據訪問效率CPU高速緩存訪問命中率高間接的也就是說數據訪問效率高反之。該優(yōu)缺點在歸并排序和快速排序的性能測試尤其體現(xiàn)這里的性能測試該篇文章有寫C List 容器詳解迭代器失效、排序與高效操作這里上面打錯了是100w個數據的數組。排序的性能差異就是由于數據的訪問效率低排序的過程就要對數據結構中的數據進行大量的訪問和交換數據越多這個差異就體現(xiàn)出來了3.2.2 CPU高速緩存訪問命中率下面說一下CPU高速緩存訪問命中率這個概念一、計算機存儲介質的層級特性計算機的存儲體系核心是“速度越快→容量越小→成本越高”的層級設計從慢到快、從大到小分為硬盤永久存儲介質斷電數據不丟失容量極大幾百 GB~ 數 TB但訪問速度最慢毫秒級。程序 / 文件的持久化存儲依賴硬盤讀取硬盤數據時需先將數據加載到內存中才能被 CPU 訪問內存臨時存儲介質斷電數據丟失容量適中8GB/16GB/32GB 為主訪問速度遠快于硬盤幾十納秒級但仍慢于 CPU 運算速度。所有運行中的程序、數據結構如 vector/list的實際數據都存儲在內存中CPU 緩存L1/L2/L3介于內存和寄存器之間的高速存儲容量遠小于內存L1 幾十 KB、L2 幾百 KB、L3 幾 MB~ 幾十 MB訪問速度是內存的 10~100 倍納秒級寄存器CPU 內部的超高速存儲幾字節(jié)幾十字節(jié)速度最快亞納秒級但容量極小僅能存儲 CPU 運算時的臨時數據如 操作的中間值。還有專門寫該部分原理的博客程序員相關的CPU緩存知識結語