c++ STL库常见增删查时间复杂度

【C++】STL各容器的实现，时间复杂度，适用情况分析 - 西*风 - 博客园 (cnblogs.com)

C++ STL 常见容器查找、删除和增添的时间复杂度_c++ map查找时间复杂度_黑化草莓熊的博客-CSDN博客

1. vector

采用一维数组实现，元素在内存连续存放，不同操作的时间复杂度为：

插入: O(N)

查看: O(1)

删除: O(N)

1. deque

   采用双向队列实现，元素在内存连续存放，不同操作的时间复杂度为：

   插入: O(N)

   查看: O(1)

   删除: O(N)

2. list

   采用双向链表实现，元素存放在堆中，不同操作的时间复杂度为：

   插入: O(1)

   查看: O(N)

   删除: O(1)

3. map、set、multimap、multiset

   上述四种容器采用红黑树实现，红黑树是平衡二叉树的一种。不同操作的时间复杂度近似为:

   插入: O(logN)

   查看: O(logN)

   删除: O(logN)

4. unordered_map、unordered_set、unordered_multimap、 unordered_multiset

   上述四种容器采用哈希表实现，不同操作的时间复杂度为： 插入: O(1)，最坏情况O(N)

   查看: O(1)，最坏情况O(N)

   删除: O(1)，最坏情况O(N)

   注意：容器的时间复杂度取决于其底层实现方式