本文主要是介绍22 rb_treesetmap深度探索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、概述
STL容器set\multiset、map和multimap是属于关联类型(associated type)。其底层结构是红黑树rb_tree。本篇先介绍红黑树的结构和使用规则，然后以set和map的特性讲述如何使用rb_tree作为底层结构。
2、红黑树rb_tree
- 红黑树是平衡二分搜索树，元素按规则排序；
- 提供遍历操作和迭代器iterator
- 不应使用rb_tree的迭代器改变元素值（因元素有排列规则），但程序并未阻止；
- rb_tree提供两种插入的方法：insert_unique()和insert_equal()，前者表示key是独一无二，后者表示key可重复。
1）G2.9中rb_tree的结构
解析：
a、rb_tree的模板类参数有5个，分别是元素的key、元素的值value(由key|data组成)、从值中取出key、元素比较以及分配器。
b、rb_tree中包含三个数据：红黑树节点大小node_count、首节点的指针header、已经key比较规则key_compare。
2）rb_tree的示例
声明一个rb_tree:
说明:此时key为int；value为int(即key和data相同，适合set或multiset)；并通过identity<int>仿函数取key；使用STL算法less<int>比大小，如下：
说明：identity通过构造仿函数返回key的值。
说明：less类是STL中定义的比较算法。
3）测试用例
解析：
a、通过上述方法什么rb_tree，初始时rb_tree为空，size()大小为0;
b、先通过insert_unique()函数插入不重复元素，若重复插入，则无效；
c、再通过insert_equal()函数出入重复的值，在rb_tree中有效，且相同元素会放在一起。
3、容器set和multiset
- set/multiset以rb_tree为底层结构，有元素自动排序的特性；
- 能够进行遍历且有迭代器iterator，能按正常的ite++来遍历获得排序状态
- 无法使用set/multiset来改变元素值，set/multiset的迭代器是const iterator，禁止了元素的赋值；
- set的key是独一无二的，因此insert是调用底层rb_tree的insert_unique();
- multiset的key是可重复的，因此insert是调用底层rb_tree的insert_equal();
1）set的结构
解析：
a、set的模板类参数有三个：第一个是key(data也是key)，第二个是默认比较方法less，第三个是分配器；
b、set中有一个数据t，类型就是底层的红黑树rb_tree；
c、此时rb_tree中的keyofvalue就是identity；
d、在实际使用过程如黄色框过程一样，声明一个int类型的set，就相当于使用了默认的key、比较方法less和identity取key法。
e、对set设置相关函数，就是间接使用rb_tree的相关函数。
f、迭代器是const类型，因此不能修改迭代器，也就是不能对元素赋值。
4、map和multimap容器
- 以rb_tree为底层结构，因此元素有自动排序的特性，排序的依据是key;
- 提供遍历操作和迭代器，正常的ite++遍历，便能得到排序状态；
- 无法使用map/multimap来改变元素的key,但可以用来改变元素的data。
- map元素的key必须独一无二，因此insert()使用的是rb_tree的insert_unique();
- multimap元素的key可以重复，因此inset()使用的是rb_tree的insert_equal().
1）map的结构
解析：
a、map模板类参数有4个，比set多了第二个参数，它是key和data的结合；
b、map中有一个数据t，它就是红黑树rb_tree类型；
c、此rb_tree默认的第三个模板参数是selectlst表示得到传入key和data中的key；
d、声明一个map<int，string>类型的map,就如上黄色狂徒过程所示。其中红海树中的value参数用标准库中的pair<const int, string>表示。
e、注意pair模板参数中是cont int，表示map中的key值是不可以改变的。
f、最后注意一点，map是可以用[ ]来来进行元素插入，而multiset则不可以。
这篇关于22 rb_treesetmap深度探索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
