C++ STL 体系结构与内核分析(四)STL六大部件-关联式容器RB-tree

关联式容器RB-tree

关联器底层主要用红黑树和哈希table来实现。

红黑树由红色节点和黑色节点组成，也叫平衡二元搜寻树。排列规则有利search和insert,并保持平衡。

走法从最左边开始，类似于中序遍历。先左再中再右。获得排序状态。

红黑树是按照key来排，允许改变它的data，key不可改变。

提供插入操作：独一无二insert_unique()/可以重复insert_equal();

标准库对于红黑树的实现：

输入参数包括key/value/keyofvalue：告诉编译器key怎么拿到/compare比大小/分配器默认值

data:node_count节点数量/header:指向红黑树的节点/key_compare:传给compare的函数/

sizeof: 4 + 4 + 1 = 9,但是得往上调成（必须对齐）->12

建立红黑树流程下图所示：建立rb_tree,选用标准库identity，同一个东西，彷函数 return x，传递key。less比较大小 return x < y;

测试用例：

新版本：标红色的是改变的

set/map内部都有一个红黑树。新版24个字节。3ptr + 1color = 24字节