一、STL無法實現的數據結構

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

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

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

延伸閱讀：

二、C++STL提供的數據結構

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

(a). vector：

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

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

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

(b). list：

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

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

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

(c). deque：

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

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

(d). array：

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

(e). forward_list：

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

2. Container Adaptors：基于其它容器實現的數據結構

(a). stack：

后入先出（LIFO）的數據結構，默認基于 deque 實現。stack 常用于深度優先搜

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

(b). queue：

先入先出（FIFO）的數據結構，默認基于 deque 實現。queue 常用于廣度優先

搜索。

(c). priority_queue：

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

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

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