C++ STL 常见容器查找、删除和增添的时间复杂度

一. Vector

动态数组，在内存中具有连续的储存空间，在堆上分配内存，支持快速随机访问，在中间插入和删除慢，但在末尾插入和删除快。

头部插入删除：$O(N)$

尾部插入删除: $O(1)$

中间插入删除：$O(N)$

查找：$O(N)$

适用场景：适用于元素结构简单，变化小，并且频繁随机访问的场景。

是一个动态数组，可以向两端发展(双向开口的连续线性空间)，因此无论在头部或者尾部安插元素都十分迅速，在中间按插元素则比较费时，因为必须移动其他元素。

双端队列的元素被表示为一个分段数组，容器中的元素分段存放在一个个大小固定的数组中。

由于分段数组的大小是固定的，并且他们的首地址被连续存放在索引数组中，因此可以对其进行随机访问，但是效率比vector低很多。

向两端加入新元素时，如果这一端的分段数组未满，则可以直接加入，如果这一端的分段数组已满，只需要创建新的分段数组，并把该分段数组的地址加入到索引数组中即可，这样就不需要对已有的元素进行移动，因此在双端队列的两端加入新的元素都具有较高的效率。

当双端队列删除首尾元素时，也不需要移动，所以效率也比较高。

双端队列中间插入元素时，需要将插入点到某一端之间的所有元素向容器的这一端移动，因此向中间插入元素的效率较低，而且往往插入的位置越靠近中间，效率越低，删除队列中元素时，情况也类似。

头部尾部插入删除：$O(1)$

中间插入删除：$O(N)$

查找：$O(N)$

适用场景：适用于既要频繁随机储存，又要关心两端数据的插入与删除操作，并且不需要频繁对中间元素进行插入删除的场景。

list由双向链表实现，元素存放在堆中，每个元素都是存放在一块内存中，它的内存空间可以是不连续的，通过指针来进行数据访问，这个特点使得它的随机储存变得非常的没有效率，但是由于链表的特点，它可以很有效率的支持任意地方的插入和删除操作。

任何位置的插入删除：$O(1)$ (假设告诉了你插入删除的位置，不需要你线查找再删除)

头尾查询：$O(1)$

其他位置查询：$O(N)$

适用场景：适用于经常进行插入和删除并且不经常随机访问的场景。

set由红黑树实现，其内部元素依照其值自动排序，每个元素只出现一次，不允许重复(红黑树是平衡二叉树的一种)

增删改查近似：O(log N)

适用场景：适用与经常查找一个元素是否在某集群中并且不要排序的场景

multiset和set相同，只不过它允许重复元素，也就是说multiset可包括多个数值相同的元素。这里不再做过多介绍。

map由红黑树实现，其元素都是键值对，每个元素的键是排序的准则，每个键只能出现一次，不允许重复

增删改查基本是O(log N)

适用场景：适用于需要储存一个字典，并要求方便的根据key找value的场景

multimap 和 map 相同，但允许重复元素，也就是说multimap可包含多个键值（key）相同的元素。这里不再做过多介绍。

📝 备注
stack，queue，prioroty_queue都属于容器配接器，是由容器按照特殊的逻辑实现的

小结：