c++ multimap是红黑树还是什么?

一、c++ multimap是红黑树还是什么

C++标准并未硬性规定multimap必须使用哪种数据结构，只是对其特性有所要求，比如容器内元素必须有序，查找删除时间复杂度得是对数级等等。而红黑树确实非常适合用于这种场景，所以主流的STL版本都采用红黑树来实现multimap。事实上如果你喜欢也可以自己用AVL树或者甚至都不需要平衡二叉树，比如skiplist就是个不错的选择，来实现multimap。这些都是符合C++标准规定的。

红黑树（RB-Tree）—map，set，multimap,multiset底层使用红黑树

Red-Black tree(红黑树)是平衡二分搜索树（balanced binary search tree）中常被使用的一种。平衡二分搜索树的特性：排列规则有利search和insert，并保持适度平衡—无任何结点过深。

RB-Tree提供遍历操作及iterators。

按正常规则（++ite）遍历，便能获得排序状态（sorted）。

我们不应该使用RB-Tree的iterators改变元素值（因为元素有其严谨的排列规则）。变成层面并未阻止此事。如此设计是正确的，因为RB-Tree即将为set何map服务（作为其底层支持），而map允许元素的data被改变，只有元素的key才是不可被改变的。

RB-Tree提供两种insertion操作：insert_unique()和insert_equal()。前者表示节点的key一定在整个tree中独一无二，否则安插失败；后者表示节点的key可重复。

容器set和multiset，底层容器使用的是红黑树（rb_tree）

set/multiset以rb_tree为底层结构，因此有元素自动排序特性。排序的依据是key，而set/multiset元素的value和key合一：value就是key。

set/multiset提供遍历操作及iterators。按正常规则（++ite）遍历，便能获得排序状态（sorted）。

我们无法使用set\multiset的iterators改变元素值（因为key有其严谨的排列规则）。set\multiset的iterator是其底部的rb_tree的const iterator，就是为了禁止用户对元素赋值。

set元素的key必须独一无二，因此其insert()用的是rb_tree的insert_unique()。

multiset元素的key可以重复，因此其insert()用的是rb_tree的insert_qeual()。

延伸阅读：

二、红黑树概念

与AVL树一样，红黑树也是map、set等关联式容器的底层结构。但红黑树是现代主流的底层结构，STL使用的便是红黑树。其原因在于：AVL树保持平衡的方法太过于绝对(必须保证每个节点的左右子树的高度差不超过1)，而红黑树的性质保证了其具有一定的”柔韧性”以及可观的效率。

红黑树的本质也是一颗二叉搜索树，但在原有的基础上做了平衡处理。红黑树的每个节点都会增加一个存储位，用来表示节点的颜色，可以是红色也可以是黑色。