容器

包括顺序式容器和关联式容器

顺序式容器

经学长提醒，stack、queue、priority_queue更准确的定义是“适配器”，参考C++（STL）容器适配器

Vector

复杂度：

• 访问复杂度：$O(1)$
• 移动复杂度：$O(n)$

vector是STL的动态数组。以数组形式储存，内存空间连续。插入和删除操作，以及需要增长数组时，需要进行内存块的复制，影响效率。

菜鸟教程 - C++ Vector容器浅析

经典例题：约瑟夫问题

栈和Stack

先进后出。

队列和queue

先进先出。

优先队列和priority_queue

复杂度：$O(n\log_2n)$

每次push和pop操作，优先队列都会按照设定的规则进行动态调整（排序），把优先级最高的元素放在前面。
在C++中，优先队列是通过二叉堆来实现的（堆排序）。

链表和list

STL中的list是双向链表。

关联式容器

set

访问、添加元素复杂度: $O(\log_2n)$

set是集合。STL的set用红黑树(基于二叉搜索树，还未学习）实现，集合中的元素是排好序的。

map

访问、添加元素复杂度$O(\log_2n)$

map实现从键（key）到值（value）的映射，使用红黑树(基于二叉搜索树，还未学习）来储存和访问。这里涉及到《数据结构》中学习的哈希表和平衡二叉树的知识。

默认是按key从小到大存放。

void main {
    map <string, int> student;    // 定义一个学生map
    student["Tom"] = 15;      // 定义Tom的学号为15
    int id = student["Tom"];  // 获取Tom的学号
}

sort()

复杂度：$O(n\log_2n)$

STL中的sort函数并不只是简单的快速排序，参考https://zhuanlan.zhihu.com/p/36274119

void sort(
    RandomAccessIterator first,
    RandomAccessIterator last
    [, Compare comp])

comp函数内置有less(),greater(),less_equal(),greater_equal。
comp函数默认为greater()。

相关函数
stable_sort()：稳定的sort()
partial_sort()：局部排序。将[fisr, last)区域中的数据进行排序。

next_permutation()

复杂度:$O(n)$
求下一个排列组合。

bool next_permutation(
    BidirectionalIterator fist,
    BidirectionalIterator last,
    Compare comp)

将整个区间内的数据按照comp（默认按照字典顺序）进行排序，新生成的序列是所有字典顺序大于排序前的序列中，最小的那一个。如果没有下一个排列组合，则返回false，否则返回true。
一般来说，若想要获得某个序列的所有可能结果，需要先将序列sort为最大或最小序列，然后再使用next_permutation()函数进行排序。

例如：假如有字符串abc，按照字典顺序，下一个排序应该是acb,然后是bac; bca; cab; cba。每一次调用该函数，都会改变原字符串；第几次调用，原字符串就会变成字典顺序第几的序列（前提是每次都返回true）。

相关函数
prev_permutation()：求前一个排列组合
lexicographical_compare()：字典比较