首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
STL 容器用过哪些,查找的时间复杂度是多少,为什么?
[问答题]
STL 容器用过哪些,查找的时间复杂度是多少,为什么?
添加笔记
求解答(0)
邀请回答
收藏(89)
分享
纠错
9个回答
添加回答
7
真令人头秃
vector(o(1))、list(o(n))、map(o(log n))、unordered_map(o(1))
发表于 2023-02-09 19:21:17
回复(0)
3
牛客689757181号
vector:插入,查看,删除 N 1 N;deque n1n;内存连续存放的);list 1n1;
发表于 2022-09-27 20:10:23
回复(0)
2
雏鹰划空
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)
1
学不明白
内存连续存放的 插入: 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)
0
反对画饼的大老虎很想五点下
vector o(1) list o(n) map ologn unordered_map o(1)
发表于 2025-03-24 13:24:15
回复(0)
0
BrightenWu
查找和查看是一个意思?比如vector,随机读取一个元素是O(1),但是查找特定元素是O(n)。
发表于 2025-03-17 17:38:53
回复(0)
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)
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)
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)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
C++
上传者:
real1993
难度:
9条回答
89收藏
2748浏览
热门推荐
相关试题
运行 ldd hello 可以得到...
百度
C++
评论
(3)
无限长正整数排列字符串
枚举
评论
(1)
BFS
枚举
评论
(1)
多组数据a+b III
过关题目
语言题
评论
(2)
素数判断
过关题目
语言题
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题