[FZH] [TL]{技术}[shlug]设计比STL Map更高效的Map

[Devil Wang]

2010/4/15 Ian Yang <doit.ian在gmail.com>

> 根据使用的场景会有更适合的。stl::map在插入查找交替进行的情况下性能是比较平均的，比较通用。基于有序的表的search不可能O(1)，
> 既然search不能O(1)，当然insert和delete也不能O(1)。不需要有序可以考虑hash，选一个好的hash函数可以达到O(1)
>
>
我也在想，hash是不是实现这个需求的唯一结构。

有没有种类似树的结构的，能实现这个需求的？

我之前在看swirl 的source code的时候，看到他们在底层实现了以个hash
的structer,但是也是基于__gnu_cxx::hash_map实现了一个类似功能的map.效率的提高也是惊人的。



> 2010/4/15 Devil Wang <wxjeacen在gmail.com>
>
>> HI all,
>>
>>
>> 众所周知，STL里面的map 是由RBT来实现的。search ,insert跟delete的效率都应该是lg(n)的。
>>
>> 而且在做上面操作的时候，还需要维持树本身的平衡。
>>
>> 虽然RBT已经很高效了，探索下有没有什么更优的结构来替代 STL的这些功能。
>>
>> 需求是search , insert,delete 操作尽量更优( 能达到O(1)就最好了)，但是也能实现STL map的那些功能。
>>
>>
>>
>> --
>> Thanks & Regards
>>
>> Linux Developer : Devil Wang
>>
>
>
>
> --
> Sincerely, Ian Yang
>
>
>


-- 
Thanks & Regards

Linux Developer : Devil Wang