一、STL無法實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)
首先stl是一些數(shù)據(jù)結(jié)構(gòu)以及其相關(guān)算法的集合。也就是說，stl是一種中間數(shù)據(jù)結(jié)構(gòu)件的集合，stl包含最基本的組建是數(shù)組，這玩意已經(jīng)是一種相當(dāng)?shù)讓拥臄?shù)據(jù)結(jié)構(gòu)了。相當(dāng)于樂高里面的最基本的片片（這比喻可能不恰當(dāng)，應(yīng)該int，float才是片片，stl應(yīng)該是至少拼成兩塊的片片）。
可以說只要有數(shù)組，其他的東西統(tǒng)統(tǒng)不要，我就可以通過寫相關(guān)算法表現(xiàn)任意高級數(shù)據(jù)結(jié)構(gòu)。圖我也可以用數(shù)組表現(xiàn)，哈希表我可以用數(shù)組表現(xiàn)。不過如果非要這么做，效率上可能會(huì)有點(diǎn)問題（很多高級數(shù)據(jù)結(jié)構(gòu)用鏈表表現(xiàn)在有的情況下效率更好）就算存在一種數(shù)據(jù)結(jié)構(gòu)，數(shù)組不能表現(xiàn)，我也可以通過數(shù)組，近似表現(xiàn)
這就是計(jì)算機(jī)數(shù)學(xué)的哲學(xué)：任意概念，我都能夠通過數(shù)字化，近似表示，當(dāng)這種近似足夠精細(xì)，我們可以認(rèn)為就是一個(gè)東西。所以個(gè)人認(rèn)為理論上不存在stl（或者說數(shù)組）實(shí)現(xiàn)不了的數(shù)據(jù)結(jié)構(gòu)。
延伸閱讀：
二、C++STL提供的數(shù)據(jù)結(jié)構(gòu)
1. Sequence Containers：維持順序的容器
(a). vector：
動(dòng)態(tài)數(shù)組，是我們最常使用的數(shù)據(jù)結(jié)構(gòu)之一，用于 O(1) 的隨機(jī)讀取。因?yàn)榇?/p>
部分算法的時(shí)間復(fù)雜度都會(huì)大于 O(n)，因此我們經(jīng)常新建 vector 來存儲各種數(shù)據(jù)或中
間變量。因?yàn)樵谖膊吭鰟h的復(fù)雜度是 O(1)，我們也可以把它當(dāng)作 stack 來用。
(b). list：
雙向鏈表，也可以當(dāng)作 stack 和 queue 來使用。由于 LeetCode 的題目多用 Node 來
表示鏈表，且鏈表不支持快速隨機(jī)讀取，因此我們很少用到這個(gè)數(shù)據(jù)結(jié)構(gòu)。一個(gè)例外
是經(jīng)典的 LRU 問題，我們需要利用鏈表的特性來解決，我們在后文會(huì)遇到這個(gè)問題。
(c). deque：
雙端隊(duì)列，這是一個(gè)非常強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，既支持 O(1) 隨機(jī)讀取，又支持 O(1)
時(shí)間的頭部增刪和尾部增刪，不過有一定的額外開銷。
(d). array：
固定大小的數(shù)組，一般在刷題時(shí)我們不使用。
(e). forward_list：
單向鏈表，一般在刷題時(shí)我們不使用。
2. Container Adaptors：基于其它容器實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)
(a). stack：
后入先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，默認(rèn)基于 deque 實(shí)現(xiàn)。stack 常用于深度優(yōu)先搜
索、一些字符串匹配問題以及單調(diào)棧問題。
(b). queue：
先入先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，默認(rèn)基于 deque 實(shí)現(xiàn)。queue 常用于廣度優(yōu)先
搜索。
(c). priority_queue：
最大值先出的數(shù)據(jù)結(jié)構(gòu)，默認(rèn)基于vector實(shí)現(xiàn)堆結(jié)構(gòu)。它可以在O(n log n)
的時(shí)間排序數(shù)組，O(log n) 的時(shí)間插入任意值，O(1) 的時(shí)間獲得最大值，O(log n) 的時(shí)
間刪除最大值。priority_queue 常用于維護(hù)數(shù)據(jù)結(jié)構(gòu)并快速獲取最大或最小值。
京公網(wǎng)安備 11010802030320號