程序员人生 网站导航

STL中set底层实现方式? 为什么不用hash?

栏目:互联网时间:2016-04-27 09:15:16

红黑树与hash table最大的不同是,红黑树是有序结构,而hash table不是。但不是说set就不能用hash,如果只是判断set中的元素是不是存在,那

么hash明显更适合,由于set 的访问操作时间复杂度是log(N)的,而使用hash底层实现的hash_set是近似O(1)的。

但是,set应当更加被强调理解

为“集合”,而集合所触及的操作并、交、差等,即STL提供的如交集set_intersection()、并集set_union()、差集set_difference()和对称差集

set_symmetric_difference(),都需要进行大量的比较工作,那末使用底层是有序结构的红黑树就10分恰当了,这也是其相对hash结构的优势所

在。 

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐