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

[Devil Wang]

我倒是写好了插入以及插入平衡。

一直没写delete.

---------- Forwarded message ----------
From: 机械唯物主义 : linjunhalida 
Date: 2010/4/15
Subject: Re: [TL]{技术}[FZH][shlug]设计比STL Map更高效的Map
To: [e-mail]

有谁写过红黑树的？花了多久？多少bug？
看算法导论里面，那操作复杂的。。

我倒是写好了插入以及插入平衡。 bug当时多如牛毛。

后还还是尽数修掉了。

网上当的红黑树代码大都是半调子。

一直没写delete.

2010/4/15 jinhu wang
> 对，还是具体问题具体对待。
> 因为平衡二叉树太通用了，经常在老c代码里看到要移入rbtree来做内存数据库。
> 在 2010年4月15日 上午11:24，机械唯物主义 : linjunhalida 写道：
>
> 现在用到的这些算法都是最优的，如果还要更优，
> > 就要根据实际的场景采用自己的数据结构，
> > 让常见的操作提高性能，以不常用的操作性能作为代价。
> >
> > 2010/4/15 jinhu wang
> > > 那样不就是hash_map了吗？
> > >
> > > 在 2010年4月15日 上午11:14，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
> > > >
> > > > --
> > > > Thanks & Regards
> > > >
> > > > Linux Developer : Devil Wang