数据结构 红黑树和set/map

一、set/multiset

set 与multiset 的区别： set 不能存相同元素， multiset 可以存相同的元素，其余的使
⽤⽅式完全⼀致。因此，我们有时候可以⽤set 帮助我们给数据去重。
在这⾥只练习使⽤set 。 set 会⽤， multiset 也会⽤。

创建set

#include <iostream>
#include <set>
using namespace std;
int main()
{
 set<int> mp1;
 set<string> mp2;
 return 0;
}

size/empty
1. size ：返回set 中实际元素的个数。时间复杂度：O(1) 。
2. empty ：判断set 是否为空。时间复杂度：O(1) 。
begin/end
迭代器，可以使⽤范围for遍历整个红⿊树。
遍历是按照中序遍历的顺序，因此是⼀个有序的序列。
insert
向红⿊树中插⼊⼀个元素
时间复杂度：O(log N) 。
erase
删除⼀个元素
时间复杂度：O(log N) 。
find/count
1. find ：查找⼀个元素，返回的是迭代器。时间复杂度：O(log N) 。
2. count ：查询元素出现的次数，⼀般⽤来判断元素是否在红⿊树中。时间复杂度：
。O(log N)
如果想查找元素是否在set中，我们⼀般不使⽤find，⽽是⽤count。因为find的返回值是⼀个迭代器，判断起来不⽅便。

lower_bound/upper_bound
1. lower_bound ：⼤于等于x的最⼩元素，返回的是迭代器；
时间复杂度：O(log N) 。
2. upper_bound ：⼤于x的最⼩元素，返回的是迭代器。

时间复杂度：O(log N) 。

#include <iostream>
#include <set>
using namespace std;
int a[] = {10, 60, 20, 70, 80, 30, 90, 40, 100, 50};
int main()
{
 set<int> mp;
 // 插⼊ 
 for(auto x : a)
 {
 mp.insert(x);
 }
 // 遍历 set，最终的结果应该是有序的 
 for(auto x : mp)
 {
 cout << x << " ";
 }
 cout << endl;
 // if(mp.count(1)) cout << "1" << endl;
 // if(mp.count(99)) cout << "99" << endl;
 // if(mp.count(30)) cout << "30" << endl;
 // if(mp.count(10)) cout << "10" << endl;
 // mp.erase(30);
 // mp.erase(10);
 // if(mp.count(30)) cout << "30" << endl;
 // else cout << "no:30" << endl;
 // if(mp.count(10)) cout << "10" << endl;
 // else cout << "no:10" << endl;
 auto x = mp.lower_bound(20);
 auto y = mp.upper_bound(20);
 cout << *x << " " << *y << endl;
 return 0;
}

二、map/multimap

map 与multimap 的区别： map 不能存相同元素， multimap 可以存相同的元素，其余的使
⽤⽅式完全⼀致。因此，这⾥只练习使⽤map 。
map 与set 的区别： set ⾥⾯存的是⼀个单独的关键字，也就是存⼀个int 、 char 、
double 或者string 。⽽map ⾥⾯存的是⼀个pair<key, value> ，（k-v模型）不仅
有⼀个关键字，还会有⼀个与关键字绑定的值，⽐较⽅式是按照key 的值来⽐较。
可以这样理解：红⿊树⾥⾯⼀个⼀个的结点都是⼀个结构体，⾥⾯有两个元素分别是key 和value 。插⼊、删除和查找的过程中，⽐较的是key 的值。
⽐如，我们可以在map 中：
• 存<int, int> ，来统计数字出现的次数；
• 存<string, int> ，来统计字符串出现的次数；
• 存<string, string> ，表⽰⼀个字符串变成另⼀个字符串；
• 甚⾄存<int, vector<int>> 来表⽰⼀个数后⾯跟了若⼲个数......，⽤来存储树。

创建map

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main()
{
 map<int, int> mp1;
 map<int, string> mp2;
 map<string, int> mp3;
 map<int, vector<int>> mp4; // 甚⾄可以挂⼀个 vector

size/empty
1. size ：求红⿊树的⼤⼩。时间复杂度：O(1) 。
2. empty ：判断红⿊树是否为空。时间复杂度：O(1) 。
 begin/end
迭代器，可以使⽤范围for遍历整个红⿊树。
遍历是按照中序遍历的顺序，因此是⼀个有序的序列。
 insert
向红⿊树中插⼊⼀个元素。这⾥需要插⼊⼀个pair，可以⽤{} 形式。⽐如： mp.insert({1, 
2}) 。
时间复杂度：O(log N) 。
 operator[]
重载[] ，使的map可以像数组⼀样使⽤。
这是map最好⽤的接⼝，有了这个重载，map的使⽤就变得特别轻松，不⽤写很多冗余的代码。
它的底层其实就是调⽤了insert函数，并且会返回val的引⽤。
erase
删除⼀个元素。
时间复杂度：O(log N) 。
 find/count

1. find ：查找⼀个元素，返回的是迭代器。时间复杂度：O(log N) 。
2. count ：查询元素出现的次数，⼀般⽤来判断当前元素是否在红⿊树中。时间复杂度：
O(log N) 。
5.8 lower_bound/upper_bound
1. lower_bound ：⼤于等于x的最⼩元素，返回的是迭代器。时间复杂度：O(log N) 。
2. upper_bound ：⼤于x的最⼩元素，返回的是迭代器。时间复杂度：O(log N) 。

#include <iostream>
#include <map>
using namespace std;
void print(map<string, int>& mp)
{
 for(auto& p : mp)
 {
 cout << p.first << " " << p.second << endl;
 }
}
// 统计⼀堆字符串中，每⼀个字符串出现的次数 
void fun()
{
 string s;
 map<string, int> mp; // <字符串，字符串出现的次数> 
 for(int i = 1; i <= 10; i++)
 {
 cin >> s;
 mp[s]++; // 体现了 operator 的强⼤ 
 }
 print(mp);
}
int main()
{
 fun();
 // map<string, int> mp;
 // // 插⼊ 
 // mp.insert({"张三", 1}); 
 // mp.insert({"李四", 2}); 
 // mp.insert({"王五", 3}); 
 // // print(mp);
 // // operator[] 可以让 map 像数组⼀样使⽤ 
 // cout << mp["张三"] << endl; 
 // mp["张三"] = 110; 
 // cout << mp["张三"] << endl; 
 // // 注意事项：operator[] 有可能会向 map 中插⼊本不想插⼊的元素 
 // // [] ⾥⾯的内容如果不存在 map 中，会先插⼊，然后再拿值 
 // // 插⼊的时候：第⼀个关键字就是 [] ⾥⾯的内容，第⼆个关键字是⼀个默认值 
 // if(mp.count("赵六") && mp["赵六"] == 4) cout << "yes" << endl; 
 // else cout << "no" << endl;
 // // 删除 
 // mp.erase("张三"); 
 // print(mp);
 return 0;
}