一、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 常用于维护数据结构并快速获取最大或最小值。