【C++】二叉搜索树set/map
文章目录
- 关联式容器
- 键值对
- key模型搜索平衡二叉树
- set的基本使用
- set的插入（insert）
- set的查找（find）
- set的删除（erase）
- set的遍历
- multiset使用
- key/val模型搜索二叉树
- map的基本使用
- map的插入（insert）
- map的删除（erase）
- map的查找（find）
- map的遍历
- operator[] (重点)
关联式容器
序列式容器：如vector，list等，这些容器底层为线性数据结构，其存储的就是元素本身
关联式容器：map/set，与序列式容器不同，其通过键值对<key, val>来存储数据，其检索效率更高
键值对
在C++中使用pair结构体存储键值对，其有两个模板参数。其中存储了两个成员变量first（key）和second（val）。我们可以通过make_pair()函数创建键值对
key模型搜索平衡二叉树
STL中的set就是以key为模型创建的搜索平衡二叉树
在STL中有两种set，普通的set的key不允许两个节点出现相同的key，但multiset允许。
普通的set可以实现查重，搜索查询的功能。
在set中key就是val，val就是key
set的基本使用
set定义的类型
set的插入（insert）
第一种插入方法
形参为一个const 修饰的val，很好理解就是插入一个值为val的节点但是返回值是一个pair
，其第一个参数类型是个迭代器，第二个参数是个bool类型的。第一个类型返回的就是值为val节点的迭代器。bool表示是否插入成功，若插入失败返回false，成功返回true
void test1()
{
set<int> s;
s.insert(1);
pair<set<int>::iterator, bool> ret1 = s.insert(1); //已经有1，不支持重复，插入失败
pair<set<int>::iterator, bool> ret2 = s.insert(2);//没有2，插入2，成功
cout << ret1.second << endl;
cout << ret2.second << endl;
}
[clx@VM-20-6-centos test]$ ./test
0
1
第二种插入方法（不常用）：
给一个迭代器，在迭代器处放入值为val的节点
可以对数据进行排序，删重
set的查找（find）
set的find函数很简单，输入一个key返回其的迭代器。若没找到则返回 set.end()
set的删除（erase）
第一种方法：使用迭代器删除（和find结合使用）
第二种方法：直接使用key删除
第三种方法：给一个迭代器区间，对其中数据删除
void test2()
{
set<int> s;
s.insert(1);
pair<set<int>::iterator, bool> ret1 = s.insert(1);
pair<set<int>::iterator, bool> ret2 = s.insert(2);
cout << s.erase(1) << endl;
cout << s.erase(3) << endl;
}
[clx@VM-20-6-centos test]$ ./test
1 //删除成功返回1
0 //删除失败返回0
1.若使用第一种方法删除，传入的迭代器无效，则编译器会报错
2.第二种方法会删除此树中所有值为key的节点，在set中若有那节点数量必定为1，所以返回1，但是在multiset中可能会有多个，erase会将这些节点全部删除，并返回删除节点数量
void set_test()
{
set<int> s;
//insert 用法
//insert 可以排序加去重
s.insert(3);
s.insert(5);
s.insert(2);
s.insert(4);
s.insert(1);
s.insert(6);
//erase 用法
//1.key 2.iterator 3.iterator range
set_print(s);
//方法2
s.erase(2); //删除成功返回1,失败返回0 返回值的类型是 unsigned int
set_print(s);
//方法1
s.erase(s.find(4)); //find返回一个迭代器
set_print(s);
//方法3
s.erase(s.find(1), s.find(3)); //find range
set_print(s);
//s.erase(s.find(100));//若使用迭代器必须要是有效的，无效会报错
}
set的遍历
void set_test()
{
set<int> s;
//insert 用法
//insert 可以排序加去重
s.insert(3);
s.insert(5);
s.insert(2);
s.insert(4);
s.insert(1);
s.insert(6);
//method 1 : iterator(迭代器)
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
it++;
}
cout << endl;
//method 2 : range for(范围for)
for (auto& e : s)
{
cout << e << " ";
}
cout << endl;
multiset使用
void multiset_test()
{
//multiset 不去重 可排序
multiset<int> ms;
ms.insert(5);
ms.insert(3);
ms.insert(2);
ms.insert(6);
ms.insert(1);
ms.insert(4);
ms.insert(5);
for (auto& e : ms)
{
cout << e << " ";
}
cout << endl;
//cout << ms.erase(5) << endl; //返回值是5在ms中出现的次数
multiset<int>::iterator pos = ms.find(5); //find 的 val有多个值时, 返回的是中序第一个val的结点的迭代器
while (pos != ms.end())
{
cout << *pos << " ";
pos++;
}
cout << endl;
//方法1
//删除所有key为5的结点
//auto start = pos;
//auto end = pos;
//while (pos != ms.end() && *pos == 5)
//{
// end = pos;
// pos++;
//}
//ms.erase(start, end);
//方法2
//while (pos != ms.end() && *pos == 5)
//{
// //必须要记录下一个结点的位置，不然erase后pos就变成野指针，无法++
// auto next = pos;
// next++;
// ms.erase(pos);
// pos = next;
//}
}
因为使用和set相近，就不重新描述了，部分需要注意的点都写在代码中了
key/val模型搜索二叉树
STL中map就是key/val模型的搜索二叉树，其通过pair（键值对）来存储数据，并通过key来对数据进行排列，便于检索
map的基本使用
map的成员类型
map的插入（insert）
其中最常用的方法是1，接下来我们将用三种形式进行插入数据
void map_test1()
{
map<string, string> dict;
//方法1：创建一个键值对pair，然后调用insert
pair<string, string> kv1("sort", "排序");
dict.insert(kv1);
//方法2：创建一个临时对象
dict.insert(pair<string, string>("left", "左"));
//方法3：调用make_pair函数
dict.insert(make_pair("right", "右"));
}
map的删除（erase）
和set相同，这里就不赘述了
map的查找（find）
map的遍历
void map_test1()
{
map<string, string> dict;
pair<string, string> kv1("sort", "排序");
dict.insert(kv1);
dict.insert(pair<string, string>("left", "左"));
dict.insert(make_pair("right", "右"));
//使用迭代器调用
map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
cout << it->first << ":" << it->second << endl;
it++;
}
cout << endl;
//使用范围for调用
for (auto& kv : dict)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
}
operator[] (重点)
重载[ ]操作符是map非常特殊的地方，和其他容器不同其方括号并非返回其中数据。其返回值非常特殊，是pair.second的引用。
若key == k的结点存在，返回此节点value的引用
若key == k的结点不存在，创建key == k的结点，并将此节点的value初始化为mapped_type(),并返回此结点val的引用
operatorp[]的功能 1.插入key == k的结点 2.查找key == k的结点的val 3.修改key == k的结点的val
本质：
mapped_type& operator[] (const key_type& k)
{ return (this->insert(make_pair(k, mapped_type())).first->second); }
接下来我们将通过一道题来解释operator[]的用法
题目：统计不同水果出现的次数
方法1：
void map_test2()
{
string arr[] = {"苹果" , "香蕉", "菠萝", "桃子", "苹果", "菠萝", "苹果"};
map<string, int> count_map;
//方法一:find + insert
for (auto fruit : arr)
{
auto ret = count_map.find(fruit); //若不存在fruit则返回count_map.end()
if (ret == count_map.end())
{
count_map.insert(make_pair(fruit, 1)); //插入节点
}
else
{
ret->second++; //已存在ret迭代器的second次数加一
}
}
}
方法2：
for (auto fruit : arr)
{
auto ret = count_map.insert(make_pair(fruit, 1));
//直接使用insert的返回值pair<iterator, bool>
if (ret.second == false) //若已经存在
{
(ret.first)->second++; //ret.first 得到目标节点迭代器
}
}
方法三：
//方法三：operator[]
for (auto& fruit : arr)
{
count_map[fruit]++;
}
//operaotp[]解释
//mapped_type& operator[] (const key_type& k)
//{ return (this->insert(make_pair(k, mapped_type())).first->second); }
//mapped_type()就是临时对象，也就是调用默认构造出来的mapped_type类型的临时对象
//若key==k的结点存在，返回此节点value的引用
//若key==k的结点不存在，创建key==k的结点，并将此节点的value初始化为mapped_type(),并返回此结点val的引用
//operatorp[]的功能 1.插入key==k的结点 2.查找key==k的结点的val 3.修改key==k的结点的val
count_map["樱桃"]; //插入
count_map["樱桃"] = 3; //修改 等价与 count_map.insert(makepair("樱桃", 3)); 插入 + 修改
cout << "樱桃" << ":" << count_map["樱桃"] << endl; //查找
for (auto& e : count_map)
{
cout << e.first << ":" << e.second << endl;
}
cout << endl;
//multimap 没有operatorp[], 与 map的区别就是不管key在不在都插入，允许冗余
//count(key_type k)函数可以帮助multimap查找有多少个相同key的结点
进阶：
输出喜欢人数最多的三种水果
struct Compare
{
bool operator()(const map<string, int>::iterator m1, const map<string, int>::iterator m2)
{
return m1->second > m2->second;
}
};
struct Compare_priority_max
{
bool operator()(map<string, int>::iterator l, map<string, int>::iterator r)
{
//小于建大堆，大于建小堆
return l->second < r->second;
}
};
void GetFavoriteFruit(const vector<string>& fruits, size_t k)
{
//仿函数，用于方法一sort 的 Compare条件
Compare comp;
map<string, int> count_map;
for (auto str : fruits)
{
count_map[str]++;
}
//方法一:将map的迭代器放入vector进行快排
//vector<map<string, int>::iterator> v;
//map<string, int>::iterator it = count_map.begin();
//while (it != count_map.end())
//{
// v.push_back(it);
// it++;
//}
//sort(v.begin(), v.end(), comp);
//for (size_t i = 0; i < k; i++)
//{
// cout << v[i]->first << ":" << v[i]->second << endl;
//}
//cout << endl;
//方法二:使用搜索树
//multimap<int, string> max_tree;
//for (auto fruit : count_map)
//{
// max_tree.insert(make_pair(fruit.second, fruit.first));
//}
//auto max = max_tree.rbegin();
//for (size_t i = 0; i < k; i++)
//{
// cout << max->second << ":" << max->first << endl;
// max++;
//}
//cout << endl;
//
//方法三:使用优先级队列
priority_queue<map<string, int>::iterator, vector<map<string,int>::iterator>, Compare_priority_max> sort_queue;
map<string, int>::iterator it = count_map.begin();
while (it != count_map.end())
{
sort_queue.push(it);
it++;
}
for (size_t i = 0; i < k; i++)
{
cout << sort_queue.top()->first << ":" << sort_queue.top()->second << endl;
sort_queue.pop();
}
cout << endl;
}
void map_test3()
{
vector<string> arr = {"苹果" , "香蕉", "菠萝", "桃子", "苹果", "菠萝", "苹果", "樱桃", "苹果", "香蕉"};
GetFavoriteFruit(arr, 3);
}