是不是可以这样理解,只要是后来需要迭代这个set的话,就需要set而不是unordered?
来源:4-3 set和map不同底层实现的区别
zombo29
2017-08-09
如果不需要迭代数据的话,大多数情况下,有序还是无序真的无所谓?即都可以利用unordered_set的O(1)效率?
谢谢老师解答
写回答
1回答
-
在很多时候,我们并不在意存储在set中的元素顺序,只在意这些元素是否存在。比如,现在有100万个学生,我们想知道这100万个学生都来自哪些不同的学校。在这种情况下,我们只在意“有哪些不同的学校”,但是对于这些学校的顺序,并不在意,清华在前还是北大在前并不重要:)
这样的例子还有很多。比如,我们想统计一本书中共使用了多少个不同的单词(可能以此为最根本的依据定义英文阅读材料的难度),那么,这些单词在容器中的顺序并不重要:)
再比如,一个网站,我们想知道有多少个不同的IP访问,那么IP的排列次序也并不重要;一个游戏有多少不同用户登录,用户排列次序也不重要,等等等等。
事实上,看了这一章,你会发现,我们使用unordered_set和unordered_map比使用set和map多。大多数时候,我们只需要建立查找表,但是查找表的键值之间的排列顺序并不重要。这一章的最后一节给出了一个顺序相关的例子:)
当然,如果你要解决的问题是需要顺序性的,自然就要使用set和map来解决。
在底层实现上,unordered_set和unordered_map通常使用哈希表来实现,所以存取的复杂度是O(1)级别的;具有顺序的set和map通常使用平衡树来实现,存取的复杂度是O(logn)级别的。通过这个数字,我们也可以看出,维护顺序性,是需要额外开销的:)
222017-08-09
相似问题