一、STL無(wú)法實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)

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

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

這就是計(jì)算機(jī)數(shù)學(xué)的哲學(xué)：任意概念，我都能夠通過(guò)數(shù)字化，近似表示，當(dāng)這種近似足夠精細(xì)，我們可以認(rèn)為就是一個(gè)東西。所以個(gè)人認(rèn)為理論上不存在stl（或者說(shuō)數(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 來(lái)存儲(chǔ)各種數(shù)據(jù)或中

間變量。因?yàn)樵谖膊吭鰟h的復(fù)雜度是 O(1)，我們也可以把它當(dāng)作 stack 來(lái)用。

(b). list：

雙向鏈表，也可以當(dāng)作 stack 和 queue 來(lái)使用。由于 LeetCode 的題目多用 Node 來(lái)

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

是經(jīng)典的 LRU 問(wèn)題，我們需要利用鏈表的特性來(lái)解決，我們?cè)诤笪臅?huì)遇到這個(gè)問(wèn)題。

(c). deque：

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

時(shí)間的頭部增刪和尾部增刪，不過(guò)有一定的額外開銷。

(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)先搜

索、一些字符串匹配問(wèn)題以及單調(diào)棧問(wèn)題。

(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)并快速獲取最大或最小值。