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 常用于维护数据结构并快速获取最大或最小值。
3. Associative Containers：实现了排好序的数据结构。
(a). set：有序集合，元素不可重复，底层实现默认为红黑树，即一种特殊的二叉查找树（BST）。它可以在 O(n log n) 的时间排序数组，O(log n) 的时间插入、删除、查找任 意值，O(log n) 的时间获得最小或最大值。这里注意，set 和 priority_queue 都可以用于维护数据结构并快速获取最大最小值，但是它们的时间复杂度和功能略有区别，如 priority_queue 默认不支持删除任意值，而 set 获得最大或最小值的时间复杂度略高，具体使用哪个根据需求而定。
(b). multiset：支持重复元素的 set。
(c). map：有序映射或有序表，在 set 的基础上加上映射关系，可以对每个元素 key 存一个值 value。
(d). multimap：支持重复元素的 map。
4. Unordered Associative Containers：对每个 Associative Containers 实现了哈希版本。
(a). unordered_set：哈希集合，可以在 O(1) 的时间快速插入、查找、删除元素，常用于快速的查询一个元素是否在这个容器内。
(b). unordered_multiset：支持重复元素的 unordered_set。
(c). unordered_map：哈希映射或哈希表，在 unordered_set 的基础上加上映射关系，可以对每一个元素 key 存一个值 value。在某些情况下，如果 key 的范围已知且较小，我们也可以用 vector 代替 unordered_map，用位置表示 key，用每个位置的值表示 value。
(d). unordered_multimap：支持重复元素的 unordered_map。
数组
栈和队列
优先队列
优先队列（priority queue）可以在 O(1) 时间内获得最大值，并且可以在 O(log n) 时间内取出最大值或插入任意值。 优先队列常常用堆（heap）来实现。堆是一个完全二叉树，其每个节点的值总是大于等于子节点的值。实际实现堆时，我们通常用一个数组而不是用指针建立一个树。这是因为堆是完全二叉树，所以用数组表示时，位置 i 的节点的父节点位置一定为 i/2，而它的两个子节点的位置又一定分别为 2i 和 2i+1。 以下是堆的实现方法，其中最核心的两个操作是上浮和下沉：如果一个节点比父节点大，那么需要交换这个两个节点；交换后还可能比它新的父节点大，因此需要不断地进行比较和交换操作，我们称之为上浮；类似地，如果一个节点比父节小，也需要不断地向下进行比较和交换操作，我们称之为下沉。如果一个节点有两个子节点，我们总是交换最大的子节点。
双端队列
哈希表
哈希表，又称散列表，使用 O(n) 空间复杂度存储数据，通过哈希函数映射位置，从而实现近似 O(1) 时间复杂度的插入、查找、删除等操作。 C++ 中的哈希集合为 unordered_set，可以查找元素是否在集合中。如果需要同时存储键和值，则需要用 unordered_map，可以用来统计频率，记录内容等等。如果元素有穷，并且范围不大，那么可以用一个固定大小的数组来存储或统计元素。例如我们需要统计一个字符串中所有字母的出现次数，则可以用一个长度为 26 的数组来进行统计，其哈希函数即为字母在字母表的位置，这样空间复杂度就可以降低为常数。
前缀和与积分图
一维的前缀和，二维的积分图，都是把每个位置之前的一维线段或二维矩形预先存储，方便加速计算。如果需要对前缀和或积分图的值做寻址，则要存在哈希表里；如果要对每个位置记录前缀和或积分图的值，则可以储存到一维或二维数组里，也常常伴随着动态规划。
标签：set,节点,queue,哈希,数据结构,unordered From： https://www.cnblogs.com/LCAB/p/16903489.html