• 【STL】容器 - set和map的使用

    目录

    前言

    一.键值对

    1.在SGI - STL中对键值对的定义: 

    2.make_pair

    3. pair支持直接比较大小

    二.set

    1.set的概念与注意事项

    2.set的使用(常用接口)

    <1>.构造函数

    <2>.迭代器与范围for

    <3>.插入和查找

    <4>.删除erase

    <5>.计数count

    三.map

    1.map的概念与注意事项

    2.map的使用(常用接口)

    <1>.构造函数

    <2>.迭代器与范围for

    <3>.查找find

    <4>插入insert

    <5>.删除erase

    <6>.计数count

    <7>.operator[]与at(重点)

    四.set/map模拟实现

    1.前言

    2.RBTree实现

    3.set实现

    4.map实现

    前言

    序列式容器与关联式容器

    序列式容器:

    string, vector, list, deque是序列式容器, 其底层都为线性结构, 在结构上没有其余特点, 里面存储的值是元素本身

    关联式容器:

    set, map, multiset, multimap是关联式容器, 其底层的结构有一定的特性与规则, 存储的是键值对, 对于数据检索而言效率更高

    set和map, multiset和multimap

    set和map的底层都是用红黑树实现的, 都自带去重

    set和map的区别: set存储key, map存储key/value

    multiset, multimap和set, map的区别: multiset, multimap不会去重, 其余都相同

    由于其他内容过于相似, 只是去不去重的问题, 本篇博客主要介绍set和map, 对于multiset和multimap的介绍更像是基于map和set的扩展

    一.键值对

    一对用来表示一对对应关系, 经典的模型, key代表键值, value表示对应的信息

    在stl中, 用pair类将键值对进行了封装, 一个pair类对象就是一个键值对

    1.在SGI - STL中对键值对的定义: 

    1. template<class T1, class T2>
    2. struct pair
    3. {
    4. 	typedef T1 first_type;
    5. 	typedef T2 second_type;
    6. 	//默认构造
    7. 	pair()
    8. 		:first(T1())
    9. 		, second(T2())
    10. 	{}
    11. 	//有参构造
    12. 	pair(const T1& a, const T2& b)
    13. 		:first(a)
    14. 		, second(b)
    15. 	{}
    16. 	//成员变量
    17. 	T1 first; // key
    18. 	T2 second;// value
    19. };

    2.make_pair

    make_pair是C++提供的一个函数模板, 用来构建pair对象

    为了使用者在创建键值对对象时更加轻松, 不用再去写过长的模板参数, 而是可以通过函数模板自动类型推导(这一点在使用map时会深有体会)

    1. //模拟实现
    2. template<class T1, class T2>
    3. pair& make_pair(const T1& first, const T2& second)
    4. {
    5. 	return pair(first, second);
    6. }

    3. pair支持直接比较大小

    pair类型可以直接比较大小

    比较规则: 先比first, 如果first相等, 就去比second

    二.set

    1.set的概念与注意事项

    1.set中只可以存储key, 从更严谨的角度: set也可以存储键值对, 但是是将整个键值对当作key来存储的

    2.set支持增删查, 而并不支持修改操作, 因为key是不可以被修改的

    3.set的底层使用红黑树实现

    4.set的查找效率是OlogN

    5.set中不可以存储相同数据, 故可以达到去重的效果

    6.set可以自己控制仿函数, 可以按照自己的比较规则来实现, 默认情况下使用less仿函数, 中序遍历是一个升序序列, 相反如果使用greater仿函数, 中序遍历就是一个降序序列

    2.set的使用(常用接口)

    set中元素不是连续存储的, 每个元素也只是一个单一的值, 所以不支持operator[]

    <1>.构造函数

    1. //构造函数
    2. void set_test1()
    3. {
    4. 	//默认构造
    5. 	set<int> s1;
    6. 	//迭代器区间构造
    7. 	vector<int> v = { 7,2,4,3,5,1,9 };
    8. 	set<int> s2(v.begin(), v.end());
    9. 	//拷贝构造
    10. 	set<int> s3(s2);//or: set s3 = s2;
    11. 	//C++11新增构造函数
    12. 	set<int> s = { 7,2,4,3,5,1,9 };
    13. }

    <2>.迭代器与范围for

    1. void set_test2()
    2. {
    3. 	//正向遍历:
    4. 	//默认使用less仿函数
    5. 	set<int> s = { 7,2,4,3,5,1,9 };
    6. 	//正向迭代器 - 底层是中序遍历
    7. 	set<int>::iterator it = s.begin();
    8. 	while (it != s.end())
    9. 	{
    10. 		cout << *it++ << ' ';
    11. 	}
    12. 	cout << endl;
    13. 	//范围for
    14. 	for (auto& elem : s)
    15. 	{
    16. 		cout << elem << ' ';
    17. 	}
    18. 	cout << endl;
    19. 	//反向遍历:
    20. 	//方法一: 反向迭代器 reverse_iterator, rbegin(), rend()
    21. 	set<int>::reverse_iterator rit = s.rbegin();
    22. 	while (rit != s.rend())
    23. 	{
    24. 		cout << *rit++ << ' ';
    25. 	}
    26. 	cout << endl;
    27. 	//方法二:
    28. 	//显式使用greater仿函数, 改变值的比较规则, 需要包头文件functional
    29. 	set<int, greater<int>> s2 = { 7,2,4,3,5,1,9 };
    30. 	set<int>::iterator it2 = s2.begin();
    31. 	while (it2 != s2.end())
    32. 	{
    33. 		cout << *it2++ << ' ';
    34. 	}
    35. 	cout << endl;
    36. 	//范围for
    37. 	for (auto& elem : s2)
    38. 	{
    39. 		cout << elem << ' ';
    40. 	}
    41. 	cout << endl;
    42. }

    <3>.插入和查找

    1. void set_test4()
    2. {
    3. 	set<int> s = { 7,2,4 };
    4. 	s.insert(3);
    5. 	s.insert(5);
    6. 	s.insert(1);
    7. 	s.insert(9);
    8. 	for (auto& elem : s)
    9. 	{
    10. 		cout << elem << ' ';
    11. 	}
    12. 	cout << endl;
    13. 	set<int>::iterator pos = s.find(5);
    14. 	if (pos != s.end())
    15. 	{
    16. 		cout << *pos << " is find" << endl;
    17. 	}
    18. }

    在multiset中查找会找到中序遍历中的第一个符合条件的值

    1. multiset<int> ms = { 5,6,8,12,1,5,3,12,9,4,2,5 };
    2. for (auto& elem : ms)
    3. {
    4. 	cout << elem << ' ';
    5. }
    6. cout << endl;
    7. multiset<int>::iterator pos = ms.find(5);
    8. while (pos != ms.end())
    9. {
    10. 	cout << *pos << ' ';
    11. 	pos++;
    12. }
    13. cout << endl;

    multiset的插入会插入到所有相同值的最右侧, 也就是中序遍历的最后一个 

    且set的insert与multiset的insert返回值类型不同

    1. multiset<int> ms = { 5,6,8,12,1,5,3,12,9,4,2,5 };
    2. for (auto& elem : ms)
    3. {
    4. 	cout << elem << ' ';
    5. }
    6. cout << endl;
    7. multiset<int>::iterator pos = ms.insert(5);;
    8. while (pos != ms.end())
    9. {
    10. 	cout << *pos << ' ';
    11. 	pos++;
    12. }
    13. cout << endl;
    14. for (auto& elem : ms)
    15. {
    16. 	cout << elem << ' ';
    17. }

    <4>.删除erase

    1. void set_test3()
    2. {
    3. 	set<int> s = { 7,2,4,3,5,1,9 };
    4. 	//set容器的erase接口既可以传值删除, 又可以传iterator删除
    5. 	//有什么区别?
    6. 	s.erase(3);
    7. 	for (auto& elem : s)
    8. 	{
    9. 		cout << elem << ' ';
    10. 	}
    11. 	cout << endl;
    12.  
    13. 	set<int>::iterator pos = s.find(4);
    14. 	if (pos != s.end())
    15. 	{
    16. 		s.erase(pos);
    17. 	}
    18. 	for (auto& elem : s)
    19. 	{
    20. 		cout << elem << ' ';
    21. 	}
    22. 	cout << endl;
    23. }

    set容器的erase接口既可以传值删除, 又可以传iterator删除, 有什么区别? 

    如果传入的是iterator, 则必须要走一步find操作, 在底层看来erase的传值删除实际是封装了先调用find查找, 再使用find返回的iterator删除这两步

    上面是删除存在的数据, 如果此时删除一个不存在的数据且不用if(pos != s.end())进行判断, 传iterator删除是有问题的, 因为如果find找不到对应数据会返回end(), 所以erase传值删除的底层也是封装了find, 如果返回end(), erase底层会有检查, 所以如果是传iterator删除, 需要手动添加if(pos != s.end())这个条件, 否则如果数据不存在就会有问题

    在multiset中会存在重复元素, erase会删除所有存在的元素

    1. void multiset_test()
    2. {
    3. 	multiset<int> ms = { 5 ,6,8,12,1,5,3,12,9,4,2,5 };
    4. 	for (auto& elem : ms)
    5. 	{
    6. 		cout << elem << ' ';
    7. 	}
    8. 	cout << endl;
    9. 	ms.erase(5);
    10. 	for (auto& elem : ms)
    11. 	{
    12. 		cout << elem << ' ';
    13. 	}
    14. 	cout << endl;
    15. }

    <5>.计数count

    set为了与multiset保持一致也支持了这个接口, 因为set中不能存放重复数据所以count只有1或这是0

    但在multiset中, count可以统计这个元素存在多少个

    1. multiset<int> ms = { 5,6,8,12,1,5,3,5,9,4,2,5 };
    2. for (auto& elem : ms)
    3. {
    4. 	cout << elem << ' ';
    5. }
    6. cout << endl;
    7. cout << "数字5有: " << ms.count(5) << "个" << endl;

    三.map

    1.map的概念与注意事项

    1.map中存储的是键值对 --- pair

    2.map支持增删查改, 这个改指的是value可以修改, key不可以修改

    3.map的底层使用红黑树实现

    4.map的查找效率是OlogN

    5.map中不可以存储相同数据, 故可以达到去重的效果

    6.map可以自己控制仿函数, 可以按照自己的比较规则来实现, 默认情况下使用less仿函数, 中序遍历是一个升序序列, 相反如果使用greater仿函数, 中序遍历就是一个降序序列

    7.map中存储的是键值对pair, 比较只能用key比

    2.map的使用(常用接口)

    <1>.构造函数

    1. void map_test1()
    2. {
    3. 	//默认构造
    4. 	map m1;
    5. 	//迭代器区间构造
    6. 	pair kv1("home", "家");
    7. 	pair kv2("happy", "高兴");
    8. 	pair kv3("sort", "排序");
    9. 	vector> v = { kv1,kv2,kv3 };
    10. 	map m2(v.begin(), v.end());
    11. 	//拷贝构造
    12. 	map m3(m2);
    13. }

    <2>.迭代器与范围for

    1. void map_test2()
    2. {
    3. 	pair kv1("home", "家");
    4. 	pair kv2("happy", "高兴");
    5. 	pair kv3("sort", "排序");
    6. 	vector> v = { kv1,kv2,kv3 };
    7. 	map m(v.begin(), v.end());
    8.  
    9. 	//迭代器遍历
    10. 	map::iterator it = m.begin();
    11. 	while (it != m.end())
    12. 	{
    13. 		cout << it->first << "-" << it->second << ' ';
    14. 		it++;
    15. 	}
    16. 	cout << endl;
    17.  
    18. 	//范围for遍历
    19. 	for (auto& elem : m)
    20. 	{
    21. 		cout << elem.first << "-" << elem.second << ' ';
    22. 	}
    23. 	cout << endl;
    24. }

    <3>.查找find

    1. void map_test3()
    2. {
    3. 	pair kv1("home", "家");
    4. 	pair kv2("happy", "高兴");
    5. 	pair kv3("sort", "排序");
    6. 	vector> v = { kv1,kv2,kv3 };
    7. 	map m(v.begin(), v.end());
    8. 	//根据键值查找
    9. 	map::iterator pos = m.find("happy");
    10.     //如果没找到, m.find()返回m.end()
    11. 	if (pos != m.end())
    12. 	{
    13. 		cout << pos->first << '-' << pos->second << endl;
    14. 	}
    15. }

    <4>插入insert

    这里insert的返回值是pair这是一个伏笔, 在后面operator[]的实现会体现他的作用 

    1. void map_test4()
    2. {
    3. 	map m;
    4. 	//第一种插入方式, 先构造对象, 再插入
    5. 	pair kv("good", "好");
    6. 	m.insert(kv);
    7. 	//第二种插入方式, 匿名对象
    8. 	m.insert(pair("bad", "坏"));
    9. 	//第三种插入方式, 使用make_pair函数模板
    10. 	m.insert(make_pair("beautiful", "漂亮"));
    11.  
    12. 	for (auto& elem : m)
    13. 	{
    14. 		cout << elem.first << "-" << elem.second << ' ';
    15. 	}
    16. 	cout << endl;
    17. }

    <5>.删除erase

    1. void map_test5()
    2. {
    3. 	pair kv1("home", "家");
    4. 	pair kv2("happy", "高兴");
    5. 	pair kv3("sort", "排序");
    6. 	vector> v = { kv1,kv2,kv3 };
    7. 	map m(v.begin(), v.end());
    8. 	for (auto& elem : m)
    9. 	{
    10. 		cout << elem.first << "-" << elem.second << ' ';
    11. 	}
    12. 	cout << endl;
    13. 	//传迭代器删除
    14. 	map::iterator pos = m.find("happy");
    15. 	if (pos != m.end())
    16. 	{
    17. 		m.erase(pos);
    18. 	}
    19. 	for (auto& elem : m)
    20. 	{
    21. 		cout << elem.first << "-" << elem.second << ' ';
    22. 	}
    23. 	cout << endl;
    24. 	//传key值删除
    25. 	cout << m.erase("home") << endl;
    26. 	for (auto& elem : m)
    27. 	{
    28. 		cout << elem.first << "-" << elem.second << ' ';
    29. 	}
    30. 	cout << endl;
    31. }

    <6>.计数count

    与set一样, count函数也是为multimap准备的, map中的count只是为了与multimap保持一致

    <7>.operator[]与at(重点)

    首先强调:

    set, multiset是没有重载operator[]的, 原因很简单, set系列是key模型, 并不存在value

    multimap也不支持operator[], 这是因为在multimap中允许插入重复的key值, 这样就违背了operator[]的意图, 所以自然也就没有支持operator[]

    在map中重载的operator[]是根据key返回对应的value的引用

    map中的operator[]存在两种情况

    1.传入的key值存在在map中, 则operator[]执行: 查找+修改value 

    2.传入的key值不存在于map中, 则operator[]执行: 插入+修改value

    如果这里insert没有返回这个pair, 那么在第2种情况, operator[]就要遍历两次, 第一次遍历, 查找且没有找到; 则需第二次遍历, 执行插入

    解释insert的返回值pair:

    由于map不会插入重复的键值, 插入时如果该键值已经存在, 则直接返回存在的这个键值对的迭代器, 如果插入的键值不存在, 则先插入, 后返回插入的这个键值对的迭代器, 但是需要插入的是, 这时value就通过一个value的匿名对象去调用他的默认构造, 来构造出一个键值对

    注: 对于内置类型, 例如int而言, int()这难道也要去调用int的默认构造吗? C++为了兼容自定义类型, 规定如int()这样的值就默认为0, float()就是0.0

    这样operator[]的实现就可以复用一个insert就可以了

    1. void map_test6()
    2. {
    3. 	string str_array[] = { "老师", "学生", "校长","学生" ,"学生" ,"学生" ,"学生" ,"学生" ,"学生","老师","老师" };
    4. 	//统计老师,学生,校长各自的人数
    5. 	mapint> m;
    6. 	for (int i = 0; i < sizeof(str_array) / sizeof(str_array[0]); ++i)
    7. 	{
    8. 		m[str_array[i]]++;
    9. 	}
    10. 	for (auto& elem : m)
    11. 	{
    12. 		cout << elem.first << "-" << elem.second << ' ';
    13. 	}
    14. 	cout << endl;
    15. }

    对operator[]实现的解读

    (this->insert(make_pair(key, value))) --- 拿到insert返回值 --- pair对象

    ( (this->insert(make_pair(key, value))) ).first --- 根据拿到的返回值对象, 去访问第一个成员iterator, 这个iterator是新插入或者查找到的key的键值对

    (* ( (this->insert(make_pair(key, value))) ).first ).second --- 对拿到的iterator解引用, 在去访问iterator的第二个成员value, 以引用的形式返回

    对于at而言, 只有查找+修改value的功能, 如果找不到就会抛出异常

    1. void map_test7()
    2. {
    3. 	string str_array[] = { "老师", "学生", "校长","学生" ,"学生" ,"学生" ,"学生" ,"学生" ,"学生","老师","老师" };
    4. 	//统计老师,学生,校长各自的人数
    5. 	mapint> m;
    6. 	for (int i = 0; i < sizeof(str_array) / sizeof(str_array[0]); ++i)
    7. 	{
    8. 		m[str_array[i]]++;
    9. 	}
    10. 	for (auto& elem : m)
    11. 	{
    12. 		cout << elem.first << "-" << elem.second << ' ';
    13. 	}
    14. 	cout << endl;
    15. 	m.at("校长") += 100;
    16. 	for (auto& elem : m)
    17. 	{
    18. 		cout << elem.first << "-" << elem.second << ' ';
    19. 	}
    20. 	cout << endl;
    21. 	m.at("主任");
    22. }

    四.set/map模拟实现

    1.前言

    map和set容器的底层使用的红黑树, set只存储值, map存储键值对

    为了体现复用思想, 红黑树存储类型统一为K/T模型, 如果是set实现T则传K, map实现T则传pair

    再通过仿函数KeyOfT来取到T中的K类型对象key

    注: 以下只是模拟实现的迭代器/插入功能

    2.RBTree实现

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #pragma once
    3.  
    4. enum Color
    5. {
    6. 	RED,
    7. 	BLACK
    8. };
    9.  
    10. template<class T>
    11. struct RBTreeNode
    12. {
    13. 	RBTreeNode* _left;
    14. 	RBTreeNode* _right;
    15. 	RBTreeNode* _parent;
    16. 	Color _col;
    17. 	T _val;
    18. 	//构造
    19. 	RBTreeNode(const T& val)
    20. 		:_left(nullptr)
    21. 		, _right(nullptr)
    22. 		, _parent(nullptr)
    23. 		, _col(RED)//默认添加的新节点为红色
    24. 		, _val(val)
    25. 	{}
    26. };
    27.  
    28. template<class T, class Ref, class Ptr>
    29. struct Iterator
    30. {
    31. 	typedef RBTreeNode Node;
    32. 	typedef Iterator Self;
    33. 	Iterator(Node* node)
    34. 		:_node(node)
    35. 	{}
    36.  
    37. 	Ref operator*()
    38. 	{
    39. 		return _node->_val;
    40. 	}
    41.  
    42. 	Ptr operator->()
    43. 	{
    44. 		//return &(_node->_val);
    45. 		return &(*Iterator(_node));
    46. 	}
    47.  
    48. 	bool operator==(const Self& val)const
    49. 	{
    50. 		return _node == val._node;
    51. 	}
    52.  
    53. 	bool operator!=(const Self& val)const
    54. 	{
    55. 		return _node != val._node;
    56. 	}
    57.  
    58. 	//前置++
    59. 	Self& operator++()
    60. 	{
    61. 		if (_node->_right != nullptr)
    62. 		{
    63. 			//找右节点为根节点的最左节点
    64. 			Node* left = _node->_right;
    65. 			while (left->_left != nullptr)
    66. 			{
    67. 				left = left->_left;
    68. 			}
    69. 			_node = left;
    70. 		}
    71. 		else
    72. 		{
    73. 			Node* parent = _node->_parent;
    74. 			Node* cur = _node;
    75. 			//如果当前是父的左,说明还没走过,下一步要走到父;
    76. 			//如果当前是父的右,说明已经走过了,下一步循环判断父是爷的左还是右,重复这个过程
    77. 			while (parent && parent->_right == cur)
    78. 			{
    79. 				cur = parent;
    80. 				parent = parent->_parent;
    81. 			}
    82. 			//出循环说明1.parent为nullptr说明到了end()2.当前是父的左
    83. 			//结论:下一步都要走到parent
    84. 			_node = parent;
    85. 		}
    86. 		return *this;
    87. 	}
    88.  
    89. 	//前置--
    90. 	//与前置++逻辑逆置
    91. 	Self& operator--()
    92. 	{
    93. 		if (_node->_left != nullptr)
    94. 		{
    95. 			Node* right = _node->_left;
    96. 			while (right->_right != nullptr)
    97. 			{
    98. 				right = right->_right;
    99. 			}
    100. 			_node = right;
    101. 		}
    102. 		else
    103. 		{
    104. 			Node* parent = _node->_parent;
    105. 			Node* cur = _node;
    106. 			while (parent && cur == parent->_left)
    107. 			{
    108. 				cur = parent;
    109. 				parent = parent->_parent;
    110. 			}
    111. 			_node = parent;
    112. 		}
    113. 		return *this;
    114. 	}
    115.  
    116. 	Node* _node;
    117. };
    118.  
    119. template<class K, class T, class KeyOfT>
    120. class RBTree
    121. {
    122. public:
    123. 	typedef RBTreeNode Node;
    124. 	typedef Iterator iterator;
    125. 	
    126. 	iterator begin()
    127. 	{
    128. 		Node* cur = root;
    129. 		while (cur && cur->_left != nullptr)
    130. 		{
    131. 			cur = cur->_left;
    132. 		}
    133. 		return iterator(cur);
    134. 	}
    135.  
    136. 	iterator end()
    137. 	{
    138. 		return iterator(nullptr);
    139. 	}
    140.  
    141. 	pairbool> insert(const T& val)
    142. 	{
    143. 		KeyOfT key;
    144. 		if (root == nullptr)
    145. 		{
    146. 			//如果此时为空树
    147. 			root = new Node(val);
    148. 			//将根节点修正为黑色
    149. 			root->_col = BLACK;
    150. 			return make_pair(iterator(root), true);
    151. 		}
    152. 		Node* cur = root;
    153. 		Node* parent = nullptr;//cur的父节点
    154. 		while (cur)
    155. 		{
    156. 			if (key(cur->_val) > key(val))
    157. 			{
    158. 				parent = cur;
    159. 				cur = cur->_left;
    160. 			}
    161. 			else if (key(cur->_val) < key(val))
    162. 			{
    163. 				parent = cur;
    164. 				cur = cur->_right;
    165. 			}
    166. 			else
    167. 			{
    168. 				//如果插入的节点是重复值, 则插入失败
    169. 				return make_pair(iterator(cur), false);
    170. 			}
    171. 		}
    172. 		cur = new Node(val);
    173. 		if (key(parent->_val) > key(cur->_val))
    174. 		{
    175. 			parent->_left = cur;
    176. 		}
    177. 		else if (key(parent->_val) < key(cur->_val))
    178. 		{
    179. 			parent->_right = cur;
    180. 		}
    181. 		cur->_parent = parent;
    182. 		//以上为插入节点
    183. 		//-------------------------------------------------------
    184. 		//以下为调整为红黑树
    185. 		//因为默认插入的节点为红色,所以如果出现了两个连续为红的节点就需要处理
    186. 		while (parent && parent->_col == RED)
    187. 		{
    188. 			Node* grandfather = parent->_parent;
    189. 			Node* uncle = nullptr;
    190. 			//确定叔叔节点的位置
    191. 			if (grandfather->_left == parent)
    192. 			{
    193. 				uncle = grandfather->_right;
    194. 			}
    195. 			else//grandfather->_right == parent
    196. 			{
    197. 				uncle = grandfather->_left;
    198. 			}
    199. 			//将分为三种情况
    200. 			//1.父节点为红,叔叔节点存在且为红(变色 + 向上迭代)
    201. 			//2/3.父节点为红,叔叔节点不存在或者存在且为黑(旋转 + 变色)
    202. 			if (uncle && uncle->_col == RED)//情况一
    203. 			{
    204. 				//父变黑,叔叔变黑,祖父变红->向上迭代
    205. 				parent->_col = BLACK;
    206. 				uncle->_col = BLACK;
    207. 				grandfather->_col = RED;
    208. 				cur = grandfather;
    209. 				parent = cur->_parent;
    210. 			}
    211. 			else//情况二/三
    212. 			{
    213. 				//情况二
    214. 				//     g
    215. 				//   p   u
    216. 				// c
    217. 				if (uncle == grandfather->_right && cur == parent->_left)
    218. 				{
    219. 					//右单旋
    220. 					RotateR(grandfather);
    221. 					//
    222. 					parent->_col = BLACK;
    223. 					grandfather->_col = RED;
    224. 					break;
    225. 				}
    226. 				//     g
    227. 				//   u   p
    228. 				//         c 
    229. 				else if (uncle == grandfather->_left && cur == parent->_right)
    230. 				{
    231. 					//左单旋
    232. 					RotateL(grandfather);
    233. 					//
    234. 					parent->_col = BLACK;
    235. 					grandfather->_col = RED;
    236. 					break;
    237.  
    238. 				}
    239. 				//情况三
    240. 				//     g
    241. 				//   u   p
    242. 				//     c
    243. 				else if (uncle == grandfather->_left && cur == parent->_left)
    244. 				{
    245. 					//左双旋
    246. 					RotateRL(grandfather);
    247. 					//
    248. 					grandfather->_col = RED;
    249. 					cur->_col = BLACK;
    250. 					break;
    251.  
    252. 				}
    253. 				//     g
    254. 				//   p   u
    255. 				//     c
    256. 				else if (uncle == grandfather->_right && cur == parent->_right)
    257. 				{
    258. 					//右双旋
    259. 					RotateLR(grandfather);
    260. 					//
    261. 					grandfather->_col = RED;
    262. 					cur->_col = BLACK;
    263. 					break;
    264.  
    265. 				}
    266. 				else
    267. 				{
    268. 					cout << "不存在这种情况" << endl;
    269. 					exit(-1);
    270. 				}
    271. 			}
    272. 		}
    273. 		root->_col = BLACK;
    274. 		return make_pair(iterator(cur), true);
    275. 	}
    276.  
    277. 	void inorder()
    278. 	{
    279. 		_inorder(root);
    280. 	}
    281.  
    282. 	bool isRBTree()
    283. 	{
    284. 		if (root->_col == RED)
    285. 		{
    286. 			cout << "出错: 根节点为红" << endl;
    287. 			return false;
    288. 		}
    289. 		//判断是否有连续红节点,且每条路径的黑节点是否相等
    290. 		int benchmark = 0;//算出最左路径的黑节点个数
    291. 		Node* cur = root;
    292. 		while (cur)
    293. 		{
    294. 			if (cur->_col == BLACK)
    295. 			{
    296. 				++benchmark;
    297. 			}
    298. 			cur = cur->_left;
    299. 		}
    300. 		return _isRBTree(root, 0, benchmark);
    301. 	}
    302.  
    303. private:
    304. 	//四种旋转
    305. 	void RotateL(Node* prev)
    306. 	{
    307. 		Node* subR = prev->_right;
    308. 		Node* subRL = subR->_left;
    309. 		Node* ppNode = prev->_parent;
    310.  
    311. 		prev->_right = subRL;
    312. 		if (subRL)
    313. 		{
    314. 			subRL->_parent = prev;
    315. 		}
    316.  
    317. 		subR->_left = prev;
    318. 		prev->_parent = subR;
    319.  
    320. 		if (root == prev)
    321. 		{
    322. 			root = subR;
    323. 		}
    324. 		else
    325. 		{
    326. 			if (ppNode->_left == prev)
    327. 			{
    328. 				ppNode->_left = subR;
    329. 			}
    330. 			else
    331. 			{
    332. 				ppNode->_right = subR;
    333. 			}
    334. 		}
    335. 		subR->_parent = ppNode;
    336. 	}
    337.  
    338. 	void RotateR(Node* prev)
    339. 	{
    340. 		Node* subL = prev->_left;
    341. 		Node* subLR = subL->_right;
    342. 		Node* ppNode = prev->_parent;
    343.  
    344. 		subL->_right = prev;
    345. 		prev->_parent = subL;
    346.  
    347. 		prev->_left = subLR;
    348. 		if (subLR)
    349. 		{
    350. 			subLR->_parent = prev;
    351. 		}
    352.  
    353. 		if (root == prev)
    354. 		{
    355. 			root = subL;
    356. 		}
    357. 		else
    358. 		{
    359. 			if (ppNode->_left == prev)
    360. 			{
    361. 				ppNode->_left = subL;
    362. 			}
    363. 			else
    364. 			{
    365. 				ppNode->_right = subL;
    366. 			}
    367. 		}
    368. 		subL->_parent = ppNode;
    369. 	}
    370.  
    371. 	void RotateRL(Node* prev)
    372. 	{
    373. 		//先右旋, 再左旋
    374. 		RotateR(prev->_right);
    375. 		RotateL(prev);
    376. 	}
    377.  
    378. 	void RotateLR(Node* prev)
    379. 	{
    380. 		//先左旋, 再右旋
    381. 		RotateL(prev->_left);
    382. 		RotateR(prev);
    383. 	}
    384.  
    385. 	void _inorder(Node* root)
    386. 	{
    387. 		if (root)
    388. 		{
    389. 			_inorder(root->_left);
    390. 			cout << root->_kv.first << "--" << root->_kv.second << endl;
    391. 			_inorder(root->_right);
    392. 		}
    393. 	}
    394.  
    395. 	bool _isRBTree(Node* root, int blackNum, int benchmark)
    396. 	{
    397. 		if (root == nullptr)//走到空节点
    398. 		{
    399. 			if (benchmark == blackNum)
    400. 			{
    401. 				//for debug
    402. 				//cout << blackNum << endl;
    403. 				return true;
    404. 			}
    405. 			else
    406. 			{
    407. 				//for debug
    408. 				//cout << blackNum << endl;
    409. 				cout << "不是所有路径的黑色节点个数都相同" << endl;
    410. 				return false;
    411. 			}
    412. 		}
    413. 		if (root->_col == BLACK)
    414. 		{
    415. 			++blackNum;
    416. 		}
    417. 		//判断是否有连续的红节点
    418. 		if (root->_col == RED && root->_parent->_col == RED)
    419. 		{
    420. 			cout << "出现了连续的红色节点" << endl;
    421. 			return false;
    422. 		}
    423. 		return _isRBTree(root->_left, blackNum, benchmark)
    424. 			&& _isRBTree(root->_right, blackNum, benchmark);
    425. 	}
    426.  
    427. 	Node* root = nullptr;
    428. };

    3.set实现

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include"RBTree.h"
    3.  
    4.  
    5. template<class K>
    6. class Set
    7. {
    8. public:
    9. 	struct SetKeyOfT
    10. 	{
    11. 		const K& operator()(const K& key)
    12. 		{
    13. 			return key;
    14. 		}
    15. 	};
    16. 	
    17. 	typedef typename RBTree::iterator iterator;
    18.  
    19. 	pairbool> insert(const K& key)
    20. 	{
    21. 		return _t.insert(key);
    22. 	}
    23.  
    24. 	iterator begin()
    25. 	{
    26. 		return _t.begin();
    27. 	}
    28.  
    29. 	iterator end()
    30. 	{
    31. 		return _t.end();
    32. 	}
    33.  
    34. private:
    35. 	RBTree _t;
    36. };

    4.map实现

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include"RBTree.h"
    3.  
    4. template<class K, class V>
    5. class Map
    6. {
    7. public:
    8. 	struct MapKeyOfT
    9. 	{
    10. 		const K& operator()(const pair& kv)
    11. 		{
    12. 			return kv.first;
    13. 		}
    14. 	};
    15.  
    16. 	typedef typename RBTree, MapKeyOfT>::iterator iterator;
    17.  
    18. 	pairbool> insert(const pair& kv)
    19. 	{
    20. 		return _t.insert(kv);
    21. 	}
    22.  
    23. 	V& operator[](const K& key)
    24. 	{
    25. 		pairbool> ret = insert(make_pair(key, V()));
    26. 		return ret.first->second;
    27. 	}
    28.  
    29. 	iterator begin()
    30. 	{
    31. 		return _t.begin();
    32. 	}
    33.  
    34. 	iterator end()
    35. 	{
    36. 		return _t.end();
    37. 	}
    38.  
    39. private:
    40. 	RBTree, MapKeyOfT> _t;
    41. };
  • 相关阅读:
    JVM内部世界(内存划分,类加载,垃圾回收)
    对标金九银十！各大厂面试八股文，三天背完分分钟斩下offer！
    Spring的创建和使用
    今年嵌入式行情怎么样？
    Spring学习篇(三)
    Serverless之Knative部署应用实例；
    Spring Boot集成redis集群拓扑动态刷新
    数据挖掘是什么？
    【MySQL基础 安装】CentOS 7 Yum网络部署 最新官方MySQL5 2020_2_1
    TextRCNN、TextCNN、RNN
  • 原文地址：https://blog.csdn.net/Hello_World_213/article/details/127671360