是不是可以这样理解,只要是后来需要迭代这个set的话,就需要set而不是unordered?

来源:4-3 set和map不同底层实现的区别

zombo29

2017-08-09

如果不需要迭代数据的话,大多数情况下,有序还是无序真的无所谓?即都可以利用unordered_set的O(1)效率?

谢谢老师解答

写回答

1回答

liuyubobobo

2017-08-09

在很多时候,我们并不在意存储在set中的元素顺序,只在意这些元素是否存在。比如,现在有100万个学生,我们想知道这100万个学生都来自哪些不同的学校。在这种情况下,我们只在意“有哪些不同的学校”,但是对于这些学校的顺序,并不在意,清华在前还是北大在前并不重要:)


这样的例子还有很多。比如,我们想统计一本书中共使用了多少个不同的单词(可能以此为最根本的依据定义英文阅读材料的难度),那么,这些单词在容器中的顺序并不重要:)


再比如,一个网站,我们想知道有多少个不同的IP访问,那么IP的排列次序也并不重要;一个游戏有多少不同用户登录,用户排列次序也不重要,等等等等。


事实上,看了这一章,你会发现,我们使用unordered_set和unordered_map比使用set和map多。大多数时候,我们只需要建立查找表,但是查找表的键值之间的排列顺序并不重要。这一章的最后一节给出了一个顺序相关的例子:)


当然,如果你要解决的问题是需要顺序性的,自然就要使用set和map来解决。


在底层实现上,unordered_set和unordered_map通常使用哈希表来实现,所以存取的复杂度是O(1)级别的;具有顺序的set和map通常使用平衡树来实现,存取的复杂度是O(logn)级别的。通过这个数字,我们也可以看出,维护顺序性,是需要额外开销的:)

2
2
liuyubobobo
回复
zombo29
哈哈 正好在工作,看到慕课网弹出提醒就回答了:)继续加油!:)
2017-08-09
共2条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7408 学习 · 1150 问题

查看课程