最近在读候捷的书《STL源码剖析》,且刚好要做一些相关的作业,产生了一些疑问,但,嗯~~~,第一个已经忘了,不好意思。
就说能记起的那个吧,为什么在STL中的map, set之类容器的底层实现要用RB-TREE,而不是(嗯,就我看来)平衡性要稍强,而实现也较易的AVL-TREE呢。我能想到的原因就是附加的标记的原因吧。因为要实现RB-TREE,只要多加一个颜色属性(BOOL型)即可,而AVL-TREE却需要一个HEIGHT属性,可能会产生问题。但在我看来,这个属性也可以用UNSIGNED CHAR来实现,其容量也可达到2的250次方,应该也不成问题的啊。而UNSIGNED CHAR和BOOL所占空间又一样,在我看来应该没什么问题的,不知道大家有没有什么更好的看法。