• C++：map和set

    目录

    一.set介绍

    1.set介绍

    2.insert 使用

     set中的普通迭代器就是用的const迭代器！！

    3.find

    set::find和std::find对比

    4.erase

    5.swap 根节点交换

    6.count 比find方便

    7.lower_bound：返回>= val得位置迭代器

    （1）lower_bound

    用途：举例：要求删除>=x的所有值：

    （2）upper_bound 返回>x位置的迭代器

    8. std::multiset 跟set接口一样，只是允许冗余，不去重

    9.set相关题目

    二.map用法介绍

    几个map和set的冷知识：

    map：

    ①map是C++98中已存在的，unordered_map是C++11中才有的

    ②map中都重载了[]运算符，multimap中没有重载[]运算符，set也没有重载[]。

    ③map中key不能修改，因为如果修改了就不能保证红黑树的有序特性了

    set：

    ①set中也可以存储键值对，实例化set时，将set中元素类型设置为pair即可

    ②set默认是升序，但是其内部默认不是按照大于比较，而是按照 less小于比较

    ③map和set查询的时间复杂度都是O(log_2N)

    ④map和set底层都是使用红黑树实现的

    1.pair和make_pair

    （1）pair键值对 的介绍

    （2）make_pair 介绍

    2.map的遍历

    （1）英汉字典的遍历

    （2）记录水果次数

    3.insert写法提高 记录水果次数 的效率（不这么写，只是为[]做铺垫）

    4.operator[] 运算符重载 

    （1） 提高 记录水果次数 的效率的真正写法：

    （2） 字典中利用[]插入或修改 示例

    5.multimap 允许键值冗余

    三.相关题目

    1.692. 前K个高频单词

    （1）做法一：stable_sort稳定排序

    （2）做法二：stable_sort稳定排序 2

    （3）做法三：sort 非稳定排序，可以控制比较方法使其稳定

     （4）做法四：利用map自身按照first排序

    四.模拟实现

    Map.h

    Set.h

    RBTree.h

    一.set介绍

    1.set介绍

    set 是一个K模型的搜索二叉树 #include

    2.insert 使用

    (1)和(2)相当于一样，在pos位置插入也会自动排序

     insert ：排序 + 去重 

    1. void test_set1()
    2. {
    3. 	set<int> s;
    4. 	s.insert(4);
    5. 	s.insert(5);
    6. 	s.insert(2);
    7. 	s.insert(1);
    8. 	s.insert(1);
    9. 	s.insert(3);
    10. 	s.insert(2);
    11. 	s.insert(1);
    12.  
    13.  
    14. 	// 排序 + 去重 
    15. 	set<int>::iterator it = s.begin();
    16. 	while (it != s.end())
    17. 	{
    18. 		//*it = 10;    迭代器不支持修改
    19. 		cout << *it << " ";
    20. 		++it;
    21. 	}
    22. 	cout << endl;
    23.  
    24.     for (auto e : s)
    25. 	{
    26. 		cout << e << " ";
    27. 	}
    28. 	cout << endl;
    29. }

     set中的普通迭代器就是用的const迭代器！！


     

    3.find

    能找到就返回元素的迭代器，找不到就返回end

    set::find和std::find对比

    set::find 搜索二叉树特性查找，时间复杂度是O(logN)

    全局的find 是暴力查找，时间复杂度是O(N)

    所以set::find效率更高

    1. void test_set2()
    2. {
    3. 	set<int> s;
    4. 	s.insert(4);
    5. 	s.insert(5);
    6. 	s.insert(2);
    7. 	s.insert(1);
    8. 	s.insert(1);
    9. 	s.insert(3);
    10. 	s.insert(2);
    11. 	s.insert(1);
    12.  
    13. 	set<int>::iterator pos = s.find(20);  // O(logN)
    14. 	if (pos != s.end())
    15. 	{
    16. 		cout << "set.find找到了" << endl;
    17. 	}
    18.  
    19. 	pos = find(s.begin(), s.end(), 2); // O(N)
    20. 	if (pos != s.end())
    21. 	{
    22. 		cout << "find找到了" << endl;
    23. 	}
    24. }

    4.erase

    size_type就是size_t，也就是unsigned int

    (1) void erase (iterator position); 必须加检查if (pos != s.end()) s.erase(pos); 因为有pos时，正常运行，如果没有pos，就会报错。例如：s.erase(pos);

    (2)size_ type erase (const value_ type& val) ; 则可以随便删，无论有没有都不报错 例如：s.erase(3)

    (3)void erase (iterator first，iterator last) 删的是[ first， last），即不包含 last

    1. void test_set3()
    2. {
    3. 	set<int> s;
    4. 	s.insert(4);
    5. 	s.insert(5);
    6. 	s.insert(2);
    7. 	s.insert(1);
    8. 	s.insert(1);
    9. 	s.insert(3);
    10. 	s.insert(2);
    11. 	s.insert(1);
    12.  
    13. 	cout << s.erase(3) << endl;    //有就返回1
    14. 	cout << s.erase(30) << endl;   //没有就返回0
    15.  
    16. 	for (auto e : s)
    17. 	{
    18. 		cout << e << " ";
    19. 	}
    20. 	cout << endl;
    21.  
    22. 	set<int>::iterator pos = s.find(3);
    23. 	if (pos != s.end())
    24. 		s.erase(pos);
    25.  
    26. 	for (auto e : s)
    27. 	{
    28. 		cout << e << " ";
    29. 	}
    30. 	cout << endl;

    5.swap 根节点交换

    6.count 比find方便

    1.  
    2. 	if (s.count(5))
    3. 	{
    4. 		cout << "5在" << endl;
    5. 	}
    6.  
    7. 	if (s.find(5) != s.end())
    8. 	{
    9. 		cout << "5在" << endl;
    10. 	}

    打印：

    5在

    5在

    7.lower_bound：返回>= val得位置迭代器

    （1）lower_bound

    返回>= val得位置迭代器 3返回3位置 6 返回7位置

    1. 返回>= val的位置迭代器 3返回3位置 6 返回7位置
    2.     set<int> s;
    3. 	s.insert(4);
    4. 	s.insert(5);
    5. 	s.insert(1);
    6. 	s.insert(3);
    7. 	s.insert(2);
    8. 	s.insert(7);
    9. 	s.insert(9);
    10.     set<int>::iterator lowIt = s.lower_bound(3); 存在
    11. 	lowIt = s.lower_bound(6); 不存在

    用途：举例：要求删除>=x的所有值：

    1. void test_set4()
    2. {
    3. 	set<int> s;
    4. 	s.insert(4);
    5. 	s.insert(5);
    6. 	s.insert(1);
    7. 	s.insert(3);
    8. 	s.insert(2);
    9. 	s.insert(7);
    10. 	s.insert(9);
    11.     for (auto e : s)
    12. 	{
    13. 		cout << e << " ";
    14. 	}
    15. 	cout << endl;
    16.  
    17. 	// 要求删除>=x的所有值
    18. 	int x;
    19. 	cin >> x;
    20. 	set<int>::iterator lowIt = s.lower_bound(x);
    21. 	s.erase(lowIt, s.end());
    22.  
    23. 	for (auto e : s)
    24. 	{
    25. 		cout << e << " ";
    26. 	}
    27. 	cout << endl;
    28. }

    （2）upper_bound 返回>x位置的迭代器

    返回>x位置的迭代器，s.upper_bound(5) 存在5，不存在6，则返回7；s.upper_bound(6) 不存在6，返回7；

    1.     set<int> s;
    2. 	s.insert(4);
    3. 	s.insert(5);
    4. 	s.insert(1);
    5. 	s.insert(3);
    6. 	s.insert(2);
    7. 	s.insert(7);
    8. 	s.insert(9);
    9.  
    10. 	返回>x位置的迭代器  -》 都是返回 7位置的迭代器
    11. 	set<int>::iterator upIt = s.upper_bound(5);  // 存在
    12. 	upIt = s.upper_bound(6); // 不存在

    用途：例如 删除x <=  <= y的区间 删除 [x,y]

    1. void test_set4()
    2. {
    3. 	set<int> s;
    4. 	s.insert(4);
    5. 	s.insert(5);
    6. 	s.insert(1);
    7. 	s.insert(3);
    8. 	s.insert(2);
    9. 	s.insert(7);
    10. 	s.insert(8);
    11.  
    12. 	// 返回>= val得位置迭代器  3返回3位置  6 返回7位置
    13. 	/*set::iterator lowIt = s.lower_bound(3); 存在
    14. 	lowIt = s.lower_bound(6); 不存在*/
    15. 	for (auto e : s)
    16. 	{
    17. 		cout << e << " ";
    18. 	}
    19. 	cout << endl;
    20.  
    21. 	// 删除x <=  <= y的区间 删除 [x,y]
    22. 	int x, y;
    23. 	cin >> x >> y;
    24. 	auto leftIt = s.lower_bound(x);  // [
    25. 	auto rightIt = s.upper_bound(y); // )
    26. 	s.erase(leftIt, rightIt);
    27. 	for (auto e : s)
    28. 	{
    29. 		cout << e << " ";
    30. 	}
    31. 	cout << endl;
    32. }

    8. std::multiset 跟set接口一样，只是允许冗余，不去重

    插入重复的数时set会去重，multiset不去重，允许冗余

    不同：

    multiset 的count和erase 返回查找或删除个数

    find(x) 多个x的话，find返回中序第一个x

    1. void test_set6()
    2. {
    3. 	multiset<int> s;
    4. 	s.insert(4);
    5. 	s.insert(5);
    6. 	s.insert(2);
    7. 	s.insert(1);
    8. 	s.insert(1);
    9. 	s.insert(3);
    10. 	s.insert(2);
    11. 	s.insert(1);
    12. 	s.insert(3);
    13. 	s.insert(3);
    14. 	s.insert(3);
    15. 	s.insert(3);
    16.  
    17. 	// 排序 
    18. 	set<int>::iterator it = s.begin();    //迭代器打印
    19. 	while (it != s.end())
    20. 	{
    21. 		//*it = 10;
    22. 		cout << *it << " ";
    23. 		++it;
    24. 	}
    25. 	cout << endl;
    26.  
    27. 	for (auto e : s)        //范围for打印
    28. 	{
    29. 		cout << e << " ";
    30. 	}
    31. 	cout << endl;
    32.  
    33. 	cout << s.count(1) << endl;    //测试count，打印3，因为1有3个
    34. 	cout << s.erase(1) << endl;    //测试erase，打印3，因为1有3个
    35. 	for (auto e : s)    
    36. 	{
    37. 		cout << e << " ";
    38. 	}
    39. 	cout << endl;
    40.                            
    41. 	auto pos = s.find(3);         // 多个x的话，find返回中序第一个x
    42. 	while (pos != s.end())        //从中序第一个3开始打印完整个
    43. 	{
    44. 		cout << *pos << " ";
    45. 		++pos;
    46. 	}
    47. 	cout << endl;
    48. }

     

    9.set相关题目

    349. 两个数组的交集

    方法一：把nums1和nums2分别放进s1和s2中进行去重，再利用范围for把s2中的每个元素在s1中进行查找，如果找到就放进v中。时间复杂度是：O(n*logn) n个节点，每个节点找logn高度次

    1. class Solution {
    2. public:
    3.     vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    4.         //去重
    5.         set<int> s1;
    6.         for(auto e:nums1)
    7.         {
    8.             s1.insert(e);
    9.         }
    10.         //去重
    11.         set<int> s2;
    12.         for(auto e:nums2)
    13.         {
    14.             s2.insert(e);
    15.         }
    16.         vector<int> v;
    17.         for(auto e:s2)
    18.         {
    19.             if(s1.count(e))
    20.             {
    21.                 v.push_back(e);
    22.             }
    23.         }
    24.         return v;
    25.     }
    26. };

    方法二：

    1. class Solution {
    2. public:
    3.     vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    4.         set<int> s1;
    5.         for(auto e:nums1)
    6.         {
    7.             s1.insert(e);
    8.         }
    9.  
    10.         set<int> s2;
    11.         for(auto e:nums2)
    12.         {
    13.             s2.insert(e);
    14.         }
    15.         vector<int> v;
    16.         set<int>::iterator it1=s1.begin();
    17.         set<int>::iterator it2=s2.begin();
    18.         while(it1!=s1.end() && it2!=s2.end())
    19.         {
    20.             if(*it1>*it2)    //相比较，值小的++
    21.             {
    22.                 ++it2;
    23.             }
    24.             else if(*it1<*it2)    //相比较，值小的++
    25.             {
    26.                 ++it1;
    27.             }
    28.             else                //相比较，值相等就放进v中，同时++
    29.             {
    30.                 v.push_back(*it1);
    31.                 ++it1;
    32.                 ++it2;
    33.             }
    34.         }
    35.         return v;
    36.     }
    37. };

    二.map用法介绍

    map是KV模型的搜索二叉树，insert和[]用法是重点，其他用法参考set        #include

    几个map和set的冷知识：

    map：

    ①map是C++98中已存在的，unordered_map是C++11中才有的

    ②map中都重载了[]运算符，multimap中没有重载[]运算符，set也没有重载[]。

    原因：map中key是唯一的，每个key都有与之对应的value，经常需要通过key获取value，因此 map为了形象简单 就重载了[]运算符, multimap中key是可以重复的，如果重载了[]运算符，给定 一个key时，就没有办法返回     value了，因此，multimap中没有重载[]运算符

    ③map中key不能修改，因为如果修改了就不能保证红黑树的有序特性了

    set：

    ①set中也可以存储键值对，实例化set时，将set中元素类型设置为pair即可

    ②set默认是升序，但是其内部默认不是按照大于比较，而是按照 less小于比较

    less是把小的放左边，所以是升序；greater是把大的放左边，所以是降序

    ③map和set查询的时间复杂度都是O(log_2N)

    解释：map和set的底层结构都是红黑树，而红黑树是近似的平衡二叉搜索树，故查询时间 复杂度为O(log_2N)

    ④map和set底层都是使用红黑树实现的

    1.pair和make_pair

    （1）pair键值对 的介绍

    用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代
    表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然
    有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应
    该单词，在词典中就可以找到与其对应的中文含义。

    pair 打包了KV模型的key和val两个类型的值，c++不支持返回两个值，也就不知道返回key和val哪一个了，所以干脆打包key和val，返回一个pair结构

    （value_type 是 pair）

    pair中的first就相当于KV模型中的key，second相当于KV模型中的val

    （2）make_pair 介绍

    make_pair 相当于返回了一个pair的匿名对象

    2.map的遍历

    （1）英汉字典的遍历

    几种插入英汉字典的方式：匿名对象插入，普通对象插入，make_pair插入

    1. void test_map1()
    2. {
    3. 	map dict;
    4.  
    5. 	// pair构造函数
    6. 	dict.insert(pair("sort", "排序")); //匿名对象插入更便捷
    7. 	pair kv("insert", "插入");    //普通对象插入
    8. 	dict.insert(kv);
    9.  
    10. 	// make_pair
    11. 	auto ret1 = dict.insert(make_pair("left", "左边"));  //make_pair插入
    12. 	auto ret2 = dict.insert(make_pair("left", "剩余"));
    13. 	// 遍历
    14. //map::iterator it = dict.begin();
    15. 	auto it = dict.begin();
    16. 	while (it != dict.end())
    17. 	{
    18. 		//cout << *it << " "; // it->operator*()
    19. 		//cout << (*it).first << ":" << (*it).second << endl;
    20. 		cout << it->first << ":" << it->second << endl;
    21. 		++it;
    22. 	}
    23. 	cout << endl;
    24.  
    25. 	for (const auto& kv : dict)
    26. 	{
    27. 		cout << kv.first << ":" << kv.second << endl;
    28. 	}
    29. }
    30.  
    31. int main()
    32. {
    33. 	test_map1();
    34. 	return 0;
    35. }

    （2）记录水果次数

    1. void test_map2()
    2. {
    3. 	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    4. 	mapint> countMap;
    5. 	for (auto& str : arr)
    6. 	{
    7. 		mapint>::iterator it = countMap.find(str);	
    8. 		if (it != countMap.end())	//如果countMap中有，就计数加1
    9. 		{
    10. 			it->second++;
    11. 		}
    12. 		else
    13. 		{
    14. 			countMap.insert(make_pair(str, 1));	//没有就插入水果
    15. 		}
    16. 	}
    17. 	for (auto& str : arr)
    18. 	{
    19. 		countMap[str]++;
    20. 	}
    21. 	for (const auto& kv : countMap)
    22. 	{
    23. 		cout << kv.first << ":" << kv.second << endl;
    24. 	}
    25. }

    3.insert写法提高 记录水果次数 的效率（不这么写，只是为[]做铺垫）

    map的insert默认是按照pair中的first进行排序的

     

    1.     string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    2. 	mapint> countMap;
    3. 	for (auto& str : arr)
    4. 	{
    5. pairint>::iterator, bool> ret = countMap.insert(make_pair(str, 1));
    6. 		//或者 auto ret = countMap.insert(make_pair(str, 1));
    7. 		if (ret.second == false)
    8. 		{
    9. 			ret.first->second++;
    10. 		}
    11. 	}
    12. 	for (const auto& kv : countMap)
    13. 	{
    14. 		cout << kv.first << ":" << kv.second << endl;
    15. 	}

    解释：

    pair::iterator, bool>  ret = countMap.insert(make_pair(str, 1)) 插入节点，若插入成功，ret.first这个iterator 存的是新插入节点的迭代器，ret.second 存的是true；若插入失败，ret.first这个iterator 存的是已有的相同节点的迭代器，ret.second 存的是false；插入失败就再记录个数++就行，ret.first->second++; 用于访问记录水果个数，ret.first 是节点迭代器，ret.first->second++; 节点中的second用于记录对应水果的个数

    4.operator[] 运算符重载 

    （1） 提高 记录水果次数 的效率的真正写法：

    1. void test_map2()
    2. {
    3. 	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    4. 	mapint> countMap;
    5. 	for (auto& str : arr)
    6. 	{
    7. 		countMap[str]++;
    8. 	}
    9.  
    10. 	for (const auto& kv : countMap)
    11. 	{
    12. 		cout << kv.first << ":" << kv.second << endl;
    13. 	}
    14. }

     

     解释：

     countMap[str]++; 中 countMap[str] 返回的是新插入节点中的 次数second 。

    如果插入的str不在 对象countMap中，countMap[str]++; 就是插入这个节点，迭代器就是新节点的迭代器，看原码可知 int类型的次数second用的是缺省值（对应原码中的mapped_typed()，是缺省值 ），所以开始second就是0，++后就是1。作用就是插入并修改val (val意思就是second)。

    如果插入的str在 对象countMap中，countMap[str]++; 就是查找到这个节点，迭代器就是已有节点的迭代器，int类型的次数second在第一次已经是1了，++后就是2。作用就是插入并修改val (val意思就是second，用于计水果次数)。

    （2） 字典中利用[]插入或修改 示例

    1. void test_map1()
    2. {
    3. 	map dict;
    4.  
    5. 	// pair构造函数
    6. 	dict.insert(pair("sort", "排序"));
    7. 	pair kv("insert", "插入");
    8. 	dict.insert(kv);
    9.  
    10. 	// make_pair
    11. 	auto ret1 = dict.insert(make_pair("left", "左边"));
    12. 	auto ret2 = dict.insert(make_pair("left", "剩余"));
    13.  
    14. 	dict["operator"] = "重载"; // 插入+修改
    15. 	dict["left"] = "左边、剩余"; // 修改
    16. 	dict["erase"];  // 插入
    17. 	cout << dict["left"] << endl; // 查找
    18. }

    5.multimap 允许键值冗余

    相比map，multimap使用函数接口最大的区别是什么?
    答：不支持operator[] 。

    三.相关题目

    1.692. 前K个高频单词

    （1）做法一：stable_sort稳定排序

    把map中的pair放到v中再用stable_sort稳定排序，再把各个pair对应的first放到vv中，再输出vv

    1. class Solution {
    2. public:
    3.     typedef mapint>::iterator CountIter;
    4.     struct less
    5.     {
    6.         bool operator()(const pairint>& x,const pairint>& y)
    7.         {
    8.             return x.second>y.second;
    9.         }
    10.     };
    11.  
    12.     vector topKFrequent(vector& words, int k) {
    13.         mapint> countMap;
    14.         for(auto& str:words)
    15.         {
    16.            countMap[str]++;
    17.         }
    18.  
    19.         vectorint>> v;
    20.         CountIter it=countMap.begin();
    21.         while(it!=countMap.end())
    22.         {
    23.             //cout<first<<" "<second<
    24.             v.push_back(*it);
    25.             ++it;
    26.         }
    27.  
    28.         stable_sort(v.begin(),v.end(),less());  //stable_sort稳定排序
    29.         vector vv;
    30.         for(int i=0;i
    31.         {
    32.             vv.push_back(v[i].first);
    33.         }
    34.         for(auto e:v)
    35.         {
    36.             cout<" "<
    37.         }
    38.         return vv;
    39.     }
    40. };

    （2）做法二：stable_sort稳定排序 2

    与做法一不同的是：pair很大，为了减少拷贝，我们可以选择不拷贝pair而是拷贝迭代器，把map中的迭代器放到v中，比较方法中通过迭代器找到second，再用stable_sort稳定排序这些迭代器，再把各个迭代器对应的first放到vv中，再输出vv

    自己敲的：

    1. class Solution {
    2. public:
    3.     typedef mapint>::iterator CountIter;
    4.     struct less //降序
    5.     {
    6.         bool operator()(const CountIter& x,const CountIter& y)
    7.         {
    8.             return x->second > y->second;
    9.         }
    10.     };
    11.     
    12.     vector topKFrequent(vector& words, int k) {
    13.         mapint> countMap;
    14.         for(auto& str:words)
    15.         {
    16.            countMap[str]++;
    17.         }
    18.  
    19.         vector v;
    20.         CountIter it=countMap.begin();
    21.         while(it!=countMap.end())
    22.         {
    23.             //cout<first<<" "<second<
    24.             v.push_back(it);
    25.             ++it;
    26.         }
    27.  
    28.         stable_sort(v.begin(),v.end(),less());  //stable_sort稳定排序
    29.         for(auto e:v)
    30.         {
    31.             cout<first<<" "<second<
    32.         }
    33.         vector vv;
    34.         for(int i=0;i
    35.         {
    36.             vv.push_back(v[i]->first);
    37.         }
    38.         
    39.         return vv;
    40.     }
    41. };

    （3）做法三：sort 非稳定排序，可以控制比较方法使其稳定

    相比较上面的方法，把stable_sort换成sort后，只需要控制比较方法即可使其稳定：因为map中默认是按照分first小的在前排序的，sort 时我们设计的比较方法是按second排序的，但是当second相等时，sort有可能打乱之前map中按 first 排的先后顺序，这样就是不稳定。我们只需要比较方法中让second相等时的情况再按first小的在前排好就可以达到稳定的目的。（相等时会多比一下first，会影响一点效率）

    自己敲的：

     （4）做法四：利用map自身按照first排序

    map的insert默认是按照pair中的first进行排序的，因此我们可以创建一个sortMap，int对应first，string对应second，然后一个一个从kv中插入进sortMap（kv中的first和second颠倒一下插入进去），因为map默认去掉重复的first，这样会导致把次数重复的元素去掉（因为次数放在了first位置），因此要用允许重复的multimap，插入顺序map默认是less降序，因为是top-k问题，我们要把map中插入顺序改成升序插入greater。

    1. class Solution {
    2. public:
    3.     vector topKFrequent(vector& words, int k) {
    4.         mapint> countMap;
    5.         for(auto& str:words)
    6.         {
    7.            countMap[str]++;
    8.         }
    9.         //排序
    10.         multimap<int,string,greater<int>> sortMap;
    11.         for(auto& kv:countMap)
    12.         {
    13.             sortMap.insert(make_pair(kv.second,kv.first));
    14.         }
    15.         // auto it=sortMap.begin();  
    16.         // while(it!=sortMap.end())
    17.         // {
    18.         //     cout<first<<" "<second<
    19.         //     ++it;
    20.         // }
    21.         vector vv;
    22.         auto it=sortMap.begin();
    23.         for(int i=0;i
    24.         {
    25.             vv.push_back(it->second);
    26.             ++it;
    27.         }
    28.         
    29.         return vv;
    30.     }
    31. };

    官方写法：

    四.用红黑树模拟实现map,set

    重点：

    struct SetKeyOfT 仿函数，用于在RBTree.h找到map/set中所要比较的值，用于控制RBTree.h中pair类型的比较方法，因为库中的pair类型 先比first再比second 的比较方法不是我们想要的

    Map.h

    1. #pragma once
    2. #include "RBTree.h"
    3.  
    4. namespace bit
    5. {
    6. 	template<class K, class V>
    7. 	class map
    8. 	{
    9. 		struct MapKeyOfT
    10. 		{
    11. 			const K& operator()(const pair& kv)
    12. 			{
    13. 				return kv.first;
    14. 			}
    15. 		};
    16. 	public:
    17. 		typedef typename RBTree, MapKeyOfT>::iterator iterator;
    18. 		typedef typename RBTree, MapKeyOfT>::const_iterator const_iterator;
    19.  
    20. 		iterator begin()
    21. 		{
    22. 			return _t.Begin();
    23. 		}
    24.  
    25. 		iterator end()
    26. 		{
    27. 			return _t.End();
    28. 		}
    29.  
    30. 		pairbool> insert(const pair& kv)
    31. 		{
    32. 			return _t.Insert(kv);
    33. 		}
    34.  
    35. 		iterator find(const K& key)
    36. 		{
    37. 			return _t.Find(key);
    38. 		}
    39.  
    40. 		V& operator[](const K& key)
    41. 		{
    42. 			pairbool> ret = insert(make_pair(key, V()));
    43. 			return ret.first->second;
    44. 		}
    45.  
    46. 	private:
    47. 		RBTree, MapKeyOfT> _t;
    48. 	};
    49.  
    50. 	void test_map1()
    51. 	{
    52. 		mapint> m;
    53. 		m.insert(make_pair("111", 1));
    54. 		m.insert(make_pair("555", 5));
    55. 		m.insert(make_pair("333", 3));
    56. 		m.insert(make_pair("222", 2));
    57.  
    58. 		mapint>::iterator it = m.begin();
    59. 		while (it != m.end())
    60. 		{
    61. 			cout << it->first << ":" << it->second << endl;
    62. 			++it;
    63. 		}
    64. 		cout << endl;
    65.  
    66. 		for (auto& kv : m)
    67. 		{
    68. 			cout << kv.first << ":" << kv.second << endl;
    69. 		}
    70. 		cout << endl;
    71. 	}
    72.  
    73. 	void test_map2()
    74. 	{
    75. 		string arr[] = { "ƻ", "", "ƻ", "", "ƻ", "ƻ", "", "ƻ", "㽶", "ƻ", "㽶" };
    76.  
    77. 		mapint> countMap;
    78. 		for (auto& str : arr)
    79. 		{
    80. 			countMap[str]++;
    81. 		}
    82.  
    83. 		for (const auto& kv : countMap)
    84. 		{
    85. 			cout << kv.first << ":" << kv.second << endl;
    86. 		}
    87. 	}
    88.  
    89. 	void test_map3()
    90. 	{
    91. 		map dict;
    92. 		dict["insert"];
    93. 		dict["insert"] = "";
    94. 		dict["left"] = "";
    95.  
    96. 	}
    97. }

    Set.h

    1. #pragma once
    2.  
    3. #include "RBTree.h"
    4.  
    5. namespace bit
    6. {
    7. 	template<class K>
    8. 	class set
    9. 	{
    10. 		struct SetKeyOfT
    11. 		{
    12. 			const K& operator()(const K& key)
    13. 			{
    14. 				return key;
    15. 			}
    16. 		};
    17. 	public:
    18. 		typedef typename RBTree::const_iterator iterator;
    19. 		typedef typename RBTree::const_iterator const_iterator;
    20.  
    21. 		iterator begin() const    //set内容不想被修改(key值不修改)，则给this设置const，
    22. 		{                          //调用时会调用带const的Begin()
    23. 			return _t.Begin();
    24. 		}
    25.  
    26. 		iterator end() const
    27. 		{
    28. 			return _t.End();
    29. 		}
    30.  
    31. 		pairbool> insert(const K& key)
    32. 		{
    33. 			//pair::iterator, bool> ret = _t.Insert(key);
    34. 			auto ret = _t.Insert(key);
    35. 			return pairbool>(iterator(ret.first._node), ret.second);
    36. 		}
    37.  
    38. 		iterator find(const K& key)
    39. 		{
    40. 			return _t.Find(key);
    41. 		}
    42. 	private:
    43. 		RBTree _t;
    44. 	};
    45.  
    46. 	void test_set1()
    47. 	{
    48. 		set<int> s;
    49. 		s.insert(8);
    50. 		s.insert(6);
    51. 		s.insert(11);
    52. 		s.insert(5);
    53. 		s.insert(6);
    54. 		s.insert(7);
    55. 		s.insert(10);
    56. 		s.insert(13);
    57. 		s.insert(12);
    58. 		s.insert(15);
    59.  
    60. 		set<int>::iterator it = s.begin();
    61. 		while (it != s.end())
    62. 		{
    63. 			cout << *it << " ";
    64. 			++it;
    65. 		}
    66. 		cout << endl;
    67.  
    68. 		for (auto e : s)
    69. 		{
    70. 			cout << e << " ";
    71. 		}
    72. 		cout << endl;
    73. 	}
    74. }

    RBTree.h

    1. pragma once
    2.  
    3. enum Colour
    4. {
    5. 	RED,
    6. 	BLACK,
    7. };
    8.  
    9. template<class T>
    10. struct RBTreeNode
    11. {
    12. 	RBTreeNode* _left;
    13. 	RBTreeNode* _right;
    14. 	RBTreeNode* _parent;
    15. 	T _data; // 数据
    16.  
    17. 	Colour _col;
    18.  
    19. 	RBTreeNode(const T& data)
    20. 		:_data(data)
    21. 		, _left(nullptr)
    22. 		, _right(nullptr)
    23. 		, _parent(nullptr)
    24. 		, _col(RED)
    25. 	{}
    26. };
    27.  
    28. template<class T, class Ref, class Ptr>
    29. struct __RBTreeIterator
    30. {
    31. 	typedef RBTreeNode Node;
    32. 	typedef __RBTreeIterator Self;
    33. 	Node* _node;
    34.  
    35. 	__RBTreeIterator(Node* node)
    36. 		:_node(node)
    37. 	{}
    38.  
    39. 	Ref operator*()
    40. 	{
    41. 		return _node->_data;
    42. 	}
    43.  
    44. 	Ptr operator->()
    45. 	{
    46. 		return &_node->_data;
    47. 	}
    48. 	// 休息17:00
    49. 	Self& operator++() //中序遍历
    50. 	{
    51. 		if (_node->_right == nullptr) //当前节点的右节点为空
    52. 		{
    53. 			// 就找祖先里面，孩子是父亲左的那个父亲
    54. 			Node* cur = _node;
    55. 			Node* parent = cur->_parent;
    56. 			while (parent && parent->_right == cur)
    57. 			{    //只要这个父亲的孩子不是父亲的左，就继续往上找
    58. 				cur = cur->_parent;
    59. 				parent = parent->_parent;
    60. 			}
    61.             //直到这个父亲的孩子是父亲的左，这个父亲就是该++走到的节点
    62. 			_node = parent;
    63. 		}
    64. 		else    //当前节点的右节点不为空
    65. 		{
    66. 			// 就走完右子树的最左节点
    67. 			Node* subLeft = _node->_right;
    68. 			while (subLeft->_left)
    69. 			{
    70. 				subLeft = subLeft->_left;
    71. 			}
    72.  
    73. 			_node = subLeft;
    74. 		}
    75. 		
    76. 		return *this;
    77. 	}
    78.  
    79. 	Self operator++(int)
    80. 	{
    81. 		Self tmp(*this);
    82. 		
    83. 		++(*this);
    84.  
    85. 		return tmp;
    86. 	}
    87.  
    88. 	Self& operator--()
    89. 	{
    90. 		if (_node->_left == nullptr)
    91. 		{
    92. 			// 找祖先里面，孩子是父亲
    93. 			Node* cur = _node;
    94. 			Node* parent = cur->_parent;
    95. 			while (parent && cur == parent->_left)
    96. 			{
    97. 				cur = cur->_parent;
    98. 				parent = parent->_parent;
    99. 			}
    100.  
    101. 			_node = parent;
    102. 		}
    103. 		else
    104. 		{
    105. 			// 左子树的最右节点
    106. 			Node* subRight = _node->_left;
    107. 			while (subRight->_right)
    108. 			{
    109. 				subRight = subRight->_right;
    110. 			}
    111.  
    112. 			_node = subRight;
    113. 		}
    114.  
    115. 		return *this;
    116. 	}
    117.  
    118. 	Self operator--(int)
    119. 	{
    120. 		Self tmp(*this);
    121.  
    122. 		--(*this);
    123.  
    124. 		return tmp;
    125. 	}
    126.  
    127. 	bool operator!=(const Self& s) const
    128. 	{
    129. 		return _node != s._node;
    130. 	}
    131.  
    132. 	bool operator==(const Self& s) const
    133. 	{
    134. 		return _node == s->_node;
    135. 	}
    136. };
    137.  
    138. // T决定红黑树存什么数据
    139. // set  RBTree
    140. // map  RBTree>
    141. // KeyOfT -> 支持取出T对象中key的仿函数
    142. template<class K, class T, class KeyOfT>
    143. class RBTree
    144. {
    145. 	typedef RBTreeNode Node;
    146. public:
    147. 	typedef __RBTreeIterator iterator;
    148. 	typedef __RBTreeIteratorconst T&, const T*> const_iterator;
    149.  
    150. 	// 构造 拷贝构造 赋值 和析构 跟搜索树实现方式是一样的
    151.  
    152. 	iterator Begin()
    153. 	{
    154. 		Node* subLeft = _root;
    155. 		while (subLeft && subLeft->_left)
    156. 		{
    157. 			subLeft = subLeft->_left;
    158. 		}
    159.  
    160. 		return iterator(subLeft);
    161. 	}
    162.  
    163. 	iterator End()
    164. 	{
    165. 		return iterator(nullptr);
    166. 	}
    167.  
    168. 	const_iterator Begin() const
    169. 	{
    170. 		Node* subLeft = _root;
    171. 		while (subLeft && subLeft->_left)
    172. 		{
    173. 			subLeft = subLeft->_left;
    174. 		}
    175.  
    176. 		return const_iterator(subLeft);
    177. 	}
    178.  
    179. 	const_iterator End() const
    180. 	{
    181. 		return const_iterator(nullptr);
    182. 	}
    183.  
    184. 	pairbool> Insert(const T& data)
    185. 	{
    186. 		// 1、搜索树的规则插入
    187. 		// 2、看是否违反平衡规则，如果违反就需要处理：旋转
    188. 		if (_root == nullptr)
    189. 		{
    190. 			_root = new Node(data);
    191. 			_root->_col = BLACK;
    192. 			return make_pair(iterator(_root), true);
    193. 		}
    194.  
    195. 		KeyOfT kot;
    196.  
    197. 		Node* parent = nullptr;
    198. 		Node* cur = _root;
    199. 		while (cur)
    200. 		{
    201. 			if (kot(cur->_data) < kot(data))
    202. 			{
    203. 				parent = cur;
    204. 				cur = cur->_right;
    205. 			}
    206. 			else if (kot(cur->_data) > kot(data))
    207. 			{
    208. 				parent = cur;
    209. 				cur = cur->_left;
    210. 			}
    211. 			else
    212. 			{
    213. 				return make_pair(iterator(cur), true);
    214. 			}
    215. 		}
    216.  
    217. 		cur = new Node(data);
    218. 		Node* newnode = cur;
    219. 		cur->_col = RED;  
    220. 		if (kot(parent->_data) < kot(data))
    221. 		{
    222. 			parent->_right = cur;
    223. 		}
    224. 		else
    225. 		{
    226. 			parent->_left = cur;
    227. 		}
    228.  
    229. 		cur->_parent = parent;
    230.  
    231. 		// 存在连续红色节点
    232. 		while (parent && parent->_col == RED)
    233. 		{
    234. 			Node* grandfater = parent->_parent;
    235. 			assert(grandfater);
    236.  
    237. 			if (grandfater->_left == parent)
    238. 			{
    239. 				Node* uncle = grandfater->_right;
    240. 				// 情况一：
    241. 				if (uncle && uncle->_col == RED) // 叔叔存在且为红
    242. 				{
    243. 					// 变色
    244. 					parent->_col = uncle->_col = BLACK;
    245. 					grandfater->_col = RED;
    246.  
    247. 					// 继续往上处理
    248. 					cur = grandfater;
    249. 					parent = cur->_parent;
    250. 				}
    251. 				else // 叔叔不存在 或者 叔叔存在且为黑
    252. 				{
    253. 					if (cur == parent->_left) // 单旋
    254. 					{
    255. 						//     g
    256. 						//   p
    257. 						// c
    258. 						RotateR(grandfater);
    259. 						parent->_col = BLACK;
    260. 						grandfater->_col = RED;
    261. 					}
    262. 					else // 双旋
    263. 					{
    264. 						//     g
    265. 						//   p
    266. 						//     c 
    267. 						RotateL(parent);
    268. 						RotateR(grandfater);
    269. 						cur->_col = BLACK;
    270. 						grandfater->_col = RED;
    271. 					}
    272.  
    273. 					break;
    274. 				}
    275. 			}
    276. 			else //(grandfater->_right == parent)
    277. 			{
    278. 				Node* uncle = grandfater->_left;
    279. 				// 情况一：
    280. 				if (uncle && uncle->_col == RED)
    281. 				{
    282. 					// 变色
    283. 					parent->_col = uncle->_col = BLACK;
    284. 					grandfater->_col = RED;
    285.  
    286. 					// 继续往上处理
    287. 					cur = grandfater;
    288. 					parent = cur->_parent;
    289. 				}
    290. 				else
    291. 				{
    292. 					if (cur == parent->_right)
    293. 					{
    294. 						// g
    295. 						//   p
    296. 						//     c 
    297. 						RotateL(grandfater);
    298. 						parent->_col = BLACK;
    299. 						grandfater->_col = RED;
    300. 					}
    301. 					else // 双旋
    302. 					{
    303. 						// g
    304. 						//   p
    305. 						// c
    306. 						RotateR(parent);
    307. 						RotateL(grandfater);
    308. 						cur->_col = BLACK;
    309. 						grandfater->_col = RED;
    310. 					}
    311.  
    312. 					break;
    313. 				}
    314. 			}
    315. 		}
    316.  
    317. 		_root->_col = BLACK;
    318.  
    319. 		return make_pair(iterator(newnode), true);
    320. 	}
    321.  
    322. 	void RotateL(Node* parent)
    323. 	{
    324. 		Node* subR = parent->_right;
    325. 		Node* subRL = subR->_left;
    326.  
    327. 		parent->_right = subRL;
    328. 		if (subRL)
    329. 			subRL->_parent = parent;
    330.  
    331. 		Node* ppNode = parent->_parent;
    332.  
    333. 		subR->_left = parent;
    334. 		parent->_parent = subR;
    335.  
    336. 		if (parent == _root)
    337. 		{
    338. 			_root = subR;
    339. 			_root->_parent = nullptr;
    340. 		}
    341. 		else
    342. 		{
    343. 			if (parent == ppNode->_left)
    344. 			{
    345. 				ppNode->_left = subR;
    346. 			}
    347. 			else
    348. 			{
    349. 				ppNode->_right = subR;
    350. 			}
    351.  
    352. 			subR->_parent = ppNode;
    353. 		}
    354. 	}
    355.  
    356. 	void RotateR(Node* parent)
    357. 	{
    358. 		Node* subL = parent->_left;
    359. 		Node* subLR = subL->_right;
    360.  
    361. 		parent->_left = subLR;
    362. 		if (subLR)
    363. 			subLR->_parent = parent;
    364.  
    365. 		Node* ppNode = parent->_parent;
    366.  
    367. 		subL->_right = parent;
    368. 		parent->_parent = subL;
    369.  
    370. 		if (parent == _root)
    371. 		{
    372. 			_root = subL;
    373. 			_root->_parent = nullptr;
    374. 		}
    375. 		else
    376. 		{
    377. 			if (ppNode->_left == parent)
    378. 			{
    379. 				ppNode->_left = subL;
    380. 			}
    381. 			else
    382. 			{
    383. 				ppNode->_right = subL;
    384. 			}
    385. 			subL->_parent = ppNode;
    386. 		}
    387. 	}
    388.  
    389. 	iterator Find(const K& key)
    390. 	{
    391. 		Node* cur = _root;
    392. 		KeyOfT kot;
    393. 		while (cur)
    394. 		{
    395. 			if (kot(cur->_data) < key)
    396. 			{
    397. 				cur = cur->_right;
    398. 			}
    399. 			else if (kot(cur->_data) > key)
    400. 			{
    401. 				cur = cur->_left;
    402. 			}
    403. 			else
    404. 			{
    405. 				return iterator(cur);
    406. 			}
    407. 		}
    408.  
    409. 		return End();
    410. 	}
    411.  
    412. private:
    413. 	Node* _root = nullptr;
    414. };

  • 相关阅读:
    python3读取yaml文件
    [ jquery 选择器 :nth-of-type() ] 选取指定类型(p)父元素下的第几个子元素
    扬帆起航：CCF开源发展论坛在深举办
    Idea部署dubbo-admin
    深入解读GLIDE/PITI代码
    零数科技荣获2022金融科技创新引领奖
    大数据Doris（二）：Doris原理篇
    [思维]Yet Another Problem Codeforces1747D
    MMLAB系列：MMCLS基本操作
    企业安全—SDL概述篇
  • 原文地址：https://blog.csdn.net/zhang_si_hang/article/details/126398107