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

[Devil Wang]

2010/4/15 Ian Yang
> 根据使用的场景会有更适合的。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
> > 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