首页 > 试题广场 >

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

[问答题]
STL 容器用过哪些,查找的时间复杂度是多少,为什么?
vector(o(1))、list(o(n))、map(o(log n))、unordered_map(o(1))
发表于 2023-02-09 19:21:17 回复(0)
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)
内存连续存放的 插入: 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)。
发表于 2025-03-17 17:38:53 回复(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)
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)
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)