一、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)。不過如果非要這么做，效率上可能會有點(diǎn)問題（很多高級數(shù)據(jù)結(jié)構(gòu)用鏈表表現(xiàn)在有的情況下效率更好）就算存在一種數(shù)據(jù)結(jié)構(gòu)，數(shù)組不能表現(xiàn)，我也可以通過數(shù)組，近似表現(xiàn)

這就是計算機(jī)數(shù)學(xué)的哲學(xué)：任意概念，我都能夠通過數(shù)字化，近似表示，當(dāng)這種近似足夠精細(xì)，我們可以認(rèn)為就是一個東西。所以個人認(rèn)為理論上不存在stl（或者說數(shù)組）實(shí)現(xiàn)不了的數(shù)據(jù)結(jié)構(gòu)。

延伸閱讀：

二、C++STL提供的數(shù)據(jù)結(jié)構(gòu)

1. Sequence Containers：維持順序的容器

(a). vector：

動態(tài)數(shù)組，是我們最常使用的數(shù)據(jù)結(jié)構(gòu)之一，用于 O(1) 的隨機(jī)讀取。因?yàn)榇?/p>

部分算法的時間復(fù)雜度都會大于 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ī)讀取，因此我們很少用到這個數(shù)據(jù)結(jié)構(gòu)。一個例外

是經(jīng)典的 LRU 問題，我們需要利用鏈表的特性來解決，我們在后文會遇到這個問題。

(c). deque：

雙端隊列，這是一個非常強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，既支持 O(1) 隨機(jī)讀取，又支持 O(1)

時間的頭部增刪和尾部增刪，不過有一定的額外開銷。

(d). array：

固定大小的數(shù)組，一般在刷題時我們不使用。

(e). forward_list：

單向鏈表，一般在刷題時我們不使用。

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ù)組，O(log n) 的時間插入任意值，O(1) 的時間獲得最大值，O(log n) 的時

間刪除最大值。priority_queue 常用于維護(hù)數(shù)據(jù)結(jié)構(gòu)并快速獲取最大或最小值。