STL 容器用过哪些，查找的时间复杂度是多少，为什么？

[问答题]

真令人头秃

vector（o(1)）、list(o(n))、map(o(log n))、unordered_map(o(1))

发表于 2023-02-09 19:21:17 回复(0)

牛客689757181号

vector：插入，查看，删除 N 1 N;deque n1n;内存连续存放的)；list 1n1；

发表于 2022-09-27 20:10:23 回复(0)

雏鹰划空

1. 容器的时间复杂度取决于其底层实现方式 2. 关联式容器：插入查看删除 =》map/set | multiSet/multiMap: O(logN) O(logN) O(logN) =》unorder map/set | multiSet/multiMap: O(1-N) O(1-N) O(1-N) 3. 顺序容器：插入、查看、删除 =》 vector： O(N) O(1) O(N) =》 list： O(1) O(N) O(N) =》deque： O(N) O(1) O(1)

发表于 2023-11-11 11:32:41 回复(0)

BrightenWu

查找和查看是一个意思？比如vector，随机读取一个元素是O(1)，但是查找特定元素是O(n)。

发表于 2025-03-17 17:38:53 回复(0)

学不明白

内存连续存放的插入: O(N) 查看: O(1) 删除: O(N) 比如：vector、deque 内存链表存放的插入: O(1) 查看: O(N) 删除: O(1) 比如：list 内存红黑树存放的插入: O(logN) 查看: O(logN) 删除: O(logN) 比如：map、set、multimap、multiset 内存哈希表存放的插入: O(1)，最坏情况O(N) 查看: O(1)，最坏情况O(N) 删除: O(1)，最坏情况O(N) unordered_map、unordered_set、unordered_multimap、 unordered_multiset

发表于 2022-07-30 15:44:33 回复(0)

反对画饼的大老虎很想五点下

vector o(1) list o(n) map ologn unordered_map o(1)

发表于 2025-03-24 13:24:15 回复(0)

爆学算法

vector：查找O（1），插入O（n），删除O（n）。 deque：查找O（1），插入O（n），删除O（n）。 list：查找O（n），插入O（1），删除O（1）。 set/multiset/map/multimap：查找O（logn），插入O（logn），删除O（logn）。 unordered_set/unordered_multiset/unordered_map/unordered_multimap：查找O（1）最差O（n），插入O（1）最差O（n），删除O（1）最差O（n）。

发表于 2025-03-15 10:04:36 回复(0)

_helios_

STL 中常用的容器有 vector、deque、list、map、set、multimap、multiset、unordered_map、unordered_set、priority_queue。 1. vector 采用一维数组实现，元素在内存连续存放，不同操作的时间复杂度为：插入: O(N) 查看: O(1) 删除: O(N) 2. deque 采用双向队列实现，元素在内存连续存放，不同操作的时间复杂度为：插入: O(N) 查看: O(1) 删除: O(N) 3. list 采用双向链表实现，元素存放在堆中，不同操作的时间复杂度为：插入: O(1) 查看: O(N) 删除: O(1) 4. map、set、multimap、multiset 上述四种容器采用红黑树实现，红黑树是平衡二叉树的一种。不同操作的时间复杂度近似为: 插入: O(logN) 查看: O(logN) 删除: O(logN) 5. unordered_map、unordered_set、unordered_multimap、 unordered_multiset 上述四种容器采用哈希表实现，不同操作的时间复杂度为：插入: O(1)，最坏情况O(N) 查看: O(1)，最坏情况O(N) 删除: O(1)，最坏情况O(N)

发表于 2024-05-21 10:13:25 回复(0)

牛客393524079号

vector ：采用一维数组实现，元素在内存连续存放，插入: O(N) 查看: O(1) 删除: O(N) deque ：采用双向队列实现，元素在内存连续存放，插入: O(N) 查看: O(1) 删除: O(N) list ：采用双向链表实现，元素在内存连续存放，插入: O(1) 查看: O(N) 删除: O(1) map、set、multimap、multiset 上述四种容器采用红黑树实现，插入: O(logN) 查看: O(logN) 删除: O(logN) unordered_map、unordered_set、unordered_multimap、 unordered_multiset 采用哈希表实现，插入: O(1)，最坏情况O(N) 查看: O(1)，最坏情况O(N) 删除: O(1)，最坏情况O(N)

发表于 2023-11-11 21:16:10 回复(0)