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

[Devil Wang]

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

一直没写delete.


---------- Forwarded message ----------
From: 机械唯物主义 : linjunhalida <linjunhalida在gmail.com>
Date: 2010/4/15
Subject: Re: [TL]{技术}[FZH][shlug]设计比STL Map更高效的Map
To: pongba在googlegroups.com


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


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

后还还是尽数修掉了。

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

一直没写delete.

2010/4/15 jinhu wang <wangjinhuman在gmail.com>

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



-- 
Thanks & Regards

Linux Developer : Devil Wang