10.2 Python 常用数据结构

# 10.2 Python 常用数据结构

类似于 C++ STL，Python 也提供了类似的数据结构（实际底层细节可能因编译器而异）：

1. Sequence Containers：维持顺序的容器。
   1. list：`动态数组`，是我们最常使用的数据结构之一，用于 $O(1)$ 的随机读取。因为大部分算法的时间复杂度都会大于 $O(n)$，因此我们经常新建 list 来存储各种数据或中间变量。因为在尾部增删的复杂度是 $O(1)$，我们也可以把它当作 stack 来用。
   2. tuple: `元组`，immutable list，不可改变其中元素或总长度。
   3. collections.deque：`双端队列`，这是一个非常强大的数据结构，既支持 $O(1)$ 随机读取，又支持 $O(1)$ 时间的头部增删和尾部增删（因此可以当作 stack 和 queue 来使用），不过有一定的额外开销。也可以用来近似一个双向链表来使用。
2. Container Adaptors：基于其它容器实现的容器。
   1. heapq：`最小堆（最小值先出的数据结构）`，默认基于 list 实现堆结构。它可以在 $O(n \log n)$ 的时间排序数组，$O(\log n)$ 的时间插入任意值，$O(1)$ 的时间获得最小值，$O(\log n)$ 的时间删除最小值。heapq 常用于维护数据结构并快速获取最小值，但不支持自定义比较函数。所以通常我们需要提前算好自定义值，再把 (自定义值，位置) 的 tuple 存进 heapq。这样进行比较时就会默认从左到右比较 tuple 中的元素，即先比较自定义值，再比较元素的插入次序。
3. Ordered Associative Containers：有序关联容器。
   1. collections.OrderedDict：`顺序映射或顺序表`，注意这里的 Ordered 不同于 C++ 中 map的按大小排序，而是按照插入的先后次序排序。OrderedDict 很适合用来做 LRU。
4. Unordered Associative Containers：无序关联容器。
   1. set：`哈希集合`，可以在 $O(1)$ 的时间快速插入、查找、删除元素，常用于快速的查询一个元素是否在这个容器内。
   2. dict：`哈希映射或哈希表`，在 set 的基础上加上映射关系，可以对每一个元素 key 存一个值 value。在某些情况下，如果 key 的范围已知且较小，我们也可以用 list 代替 dict，用位置表示 key，用每个位置的值表示 value。
   3. collections.Counter：`计数器`，是 dict 的一个特殊版本，可以直接传入一个 list，并对其中的每一个元素进行计数统计，key 是元素值，value 是元素出现的频次。可以用来当作多重集合。
   
同样的，因为这并不是一本讲解 Python 原理的书，更多的数据结构细节请读者自行搜索。只有理解了这些数据结构的原理和使用方法，才能够更加游刃有余地解决算法和数据结构问题。