红黑树
set/multiset以红黑树为底层结构,因此元素在插入过程中自动排序。
STL中的红黑树为了方便实现,创建了一个假的header,并使用指针指向真正的红黑树根节点。
红黑树使用三个数据记录树结构:
- node_count:节点的个数。
- header:指向真正的根节点。
- key_compare:仿函数,如果节点中存储的是一个类/对象,使用仿函数来比较元素大小。
红黑树提供遍历操作和iterator。遍历得到的是元素排列的中序遍历,也就是从大到小或者从小到大的顺序。
set/multiset
set的迭代器无法改变元素值(因为需要保持红黑树的性质),实现的技巧是使用const迭代器。