c++STL系列:set & multiset

红黑树

set/multiset以红黑树为底层结构,因此元素在插入过程中自动排序。

STL中的红黑树为了方便实现,创建了一个假的header,并使用指针指向真正的红黑树根节点。
红黑树使用三个数据记录树结构:

  • node_count:节点的个数。
  • header:指向真正的根节点。
  • key_compare:仿函数,如果节点中存储的是一个类/对象,使用仿函数来比较元素大小。

红黑树提供遍历操作和iterator。遍历得到的是元素排列的中序遍历,也就是从大到小或者从小到大的顺序。

set/multiset

set的迭代器无法改变元素值(因为需要保持红黑树的性质),实现的技巧是使用const迭代器。