一、STL無法實現(xiàn)的數(shù)據(jù)結構

首先stl是一些數(shù)據(jù)結構以及其相關算法的集合。也就是說，stl是一種中間數(shù)據(jù)結構件的集合，stl包含最基本的組建是數(shù)組，這玩意已經(jīng)是一種相當?shù)讓拥臄?shù)據(jù)結構了。相當于樂高里面的最基本的片片（這比喻可能不恰當，應該int，float才是片片，stl應該是至少拼成兩塊的片片）。

可以說只要有數(shù)組，其他的東西統(tǒng)統(tǒng)不要，我就可以通過寫相關算法表現(xiàn)任意高級數(shù)據(jù)結構。圖我也可以用數(shù)組表現(xiàn)，哈希表我可以用數(shù)組表現(xiàn)。不過如果非要這么做，效率上可能會有點問題（很多高級數(shù)據(jù)結構用鏈表表現(xiàn)在有的情況下效率更好）就算存在一種數(shù)據(jù)結構，數(shù)組不能表現(xiàn)，我也可以通過數(shù)組，近似表現(xiàn)

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

延伸閱讀：

二、C++STL提供的數(shù)據(jù)結構

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

(a). vector：

動態(tài)數(shù)組，是我們最常使用的數(shù)據(jù)結構之一，用于 O(1) 的隨機讀取。因為大

部分算法的時間復雜度都會大于 O(n)，因此我們經(jīng)常新建 vector 來存儲各種數(shù)據(jù)或中

間變量。因為在尾部增刪的復雜度是 O(1)，我們也可以把它當作 stack 來用。

(b). list：

雙向鏈表，也可以當作 stack 和 queue 來使用。由于 LeetCode 的題目多用 Node 來

表示鏈表，且鏈表不支持快速隨機讀取，因此我們很少用到這個數(shù)據(jù)結構。一個例外

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

(c). deque：

雙端隊列，這是一個非常強大的數(shù)據(jù)結構，既支持 O(1) 隨機讀取，又支持 O(1)

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

(d). array：

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

(e). forward_list：

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

2. Container Adaptors：基于其它容器實現(xiàn)的數(shù)據(jù)結構

(a). stack：

后入先出（LIFO）的數(shù)據(jù)結構，默認基于 deque 實現(xiàn)。stack 常用于深度優(yōu)先搜

索、一些字符串匹配問題以及單調棧問題。

(b). queue：

先入先出（FIFO）的數(shù)據(jù)結構，默認基于 deque 實現(xiàn)。queue 常用于廣度優(yōu)先

搜索。

(c). priority_queue：

最大值先出的數(shù)據(jù)結構，默認基于vector實現(xiàn)堆結構。它可以在O(n log n)

的時間排序數(shù)組，O(log n) 的時間插入任意值，O(1) 的時間獲得最大值，O(log n) 的時

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