【C++】二叉搜索树set/map

set/map"/>

【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 rangeset_print(s);//方法2s.erase(2);                    //删除成功返回1,失败返回0 返回值的类型是 unsigned intset_print(s);//方法1s.erase(s.find(4));            //find返回一个迭代器set_print(s);//方法3s.erase(s.find(1), s.find(3)); //find rangeset_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，然后调用insertpair<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的结点的valcount_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);
}