map和set

目录

1、二叉搜索树

2、set

3、multiset

4、map

5、multimap

这里将会介绍二叉搜索树，以及与之相关的四种容器的使用和特性 

1、二叉搜索树

二叉搜索树我认为还是比较简单的，所以不单独写一篇博客，而是在这里进行一些介绍

二叉搜索树又称二叉排序树或二叉查找树，它可以是一棵空树，如果不是空树那就具有一些性质：

若左子树不为空，则左子树上所有节点的值都小于根节点的值

若右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树

由于二叉搜索树有这样的规律，所以用于搜索和查找时都会非常方便，对其中序遍历就可以进行升序排序。二叉搜索树有key模式和key-value模式，key模式就是树的每个节点都带有一个key值，而key-value模式就是每个节点在带有一个key值的同时还匹配一个value值，那么可以通过key值查找到对应的value值。这种结构也叫做键值对，键值对是用来表示具有一一对应关系的一种结构，比如在字典中通过查找单词就可以找到单词对应的中文意思，那么我们可以把单词看作是key值，把中文看作是对应的value值。

2、set

按照我的理解，set就可以被认为是存储key模式的搜索二叉树的容器，并且它在存储数据时会按照key的类型的比较方式对数据进行排序，set中的元素不能被修改，但是可以从容器中进行插入或者删除，set中的元素的key值是不可以重复的，在插入时也会进行自动去重，查找元素的时间复杂度为logN

可以看到set的模板参数列表中，T表示set中存放元素的类型，Compare表示set中元素的比较方式，默认按照升序来排列。Alloc是set中元素空间的管理方式，使用STL提供的空间适配器管理。对于空间适配器在后续也会进行学习和详细介绍，这里可以先不用管

根据之前的学习经验，set的用法也是差不多的包括set的构造、set的迭代器、set的插入删除等

set s;s.insert(4);s.insert(6);s.insert(8);s.insert(3);s.insert(5);s.insert(7);s.insert(7);s.insert(7);s.insert(7);set::iterator it = s.begin();while (it != s.end()){cout << *it <<\" \" ;it++;}cout << endl;for (auto& e : s){cout << e << \" \";}cout << endl;auto pos = s.find(3);s.erase(pos);s.erase(s.find(7));s.erase(5);for (auto& e : s){cout << e << \" \";}cout << endl;

不过还是有些特殊的地方的，count()函数，参数为需要寻找的元素值，返回值为0或1，可以找到就返回1，找不到就返回0。

迭代器：low和up可以用于指定边界位置，可以配合lower_bound()，upper_bound()，equal_range()，first，second一起使用

lower_bound()：参数为需要寻找的左边界元素值，返回大于等于参数的元素值位置。

upper_bound()：参数为需要寻找的有边界元素值，返回大于参数的元素值位置。

那么就可以将lower_bound()的返回值作为low的值，将upper_bound()的返回值作为up的值，就可以确定一个区间进行统一的删除操作。

还有equal_range()，参数为需要寻找的元素值，返回值为参数值相同的元素的位置区间，first为首位置，second为尾位置，将首尾位置赋值给low和up也可以确定区间并实现删除操作

set s;s.insert(4);s.insert(6);s.insert(8);s.insert(3);s.insert(5);s.insert(7);s.insert(7);s.insert(7);s.insert(7);//auto itlow=s.lower_bound(5);//auto itup=s.upper_bound(7);auto ret=s.equal_range(7);auto itlow = ret.first;auto itup = ret.second;cout << *itlow << endl;cout << *itup << endl;s.erase(itlow, itup);for (auto& e : s){cout << e << \" \";}cout << endl;

这里的count()、equal_range()看起来用处并不大，但实际他们是专门为multiset设计的，因为multiset和set使用的是同样的接口。

3、multiset

multiset大部分内容都与set一样，只是multiset里面的元素可以重复，那么count()就会返回查找到的参数的个数，而equal_range()是返回与参数值相同的位置区间

multiset s;s.insert(4);s.insert(6);s.insert(8);s.insert(3);s.insert(5);s.insert(7);s.insert(7);s.insert(7);s.insert(7);for (auto& e : s){cout << e << \" \";}cout << endl;//auto itlow=s.lower_bound(5);//auto itup=s.upper_bound(7);auto ret = s.equal_range(7);auto itlow = ret.first;auto itup = ret.second;cout << *itlow << endl;cout << *itup << endl;s.erase(itlow, itup);for (auto& e : s){cout << e << \" \";}cout << endl;

4、map

开头介绍了二叉搜索树有key模式和key_value模式，set是用于存储key模式的二叉搜索树容器，那么map就是用于存储key_value模式的二叉搜索树的容器。map中的first和second分别用于表示key值和value值

在map中，key值用于排序和标识元素，key是唯一的且不能被修改，map中的元素也是有序的，默认按照key的小于方式进行比较，key与value的类型可以不同，key与value通过成员类型value_type绑定在一起，为其取别名称为pair

在进行定义时不仅要显式定义map，还有显式定义pair，如果插入与map中已有元素的key值相同的元素，无论value值是否相同都不会进行插入，也不会进行覆盖

map dict;pair k1(\"insert\", \"插入\");dict.insert(k1);dict.insert(pair(\"erase\", \"删除\"));//c++98dict.insert(make_pair(\"string\", \"字符串\"));//c++11dict.insert({ \"find\",\"查找\" });auto it = dict.begin();while (it != dict.end()){cout << (*it).first << \":\" << (*it).second << endl;it++;}cout << endl;dict.insert(make_pair(\"string\", \"xxxxx\"));for (auto& k : dict){cout << k.first << \":\" << k.second << endl;}

map支持下标访问符，在[ ]中放入key，就可以找到与之相对应的value值

string arr[] = { \"西瓜\", \"西瓜\", \"苹果\", \"西瓜\", \"苹果\", \"苹果\", \"西瓜\", \"苹果\", \"香蕉\", \"苹果\", \"香蕉\" };map countMap;//for (auto e : arr)//{//auto it = countMap.find(e);//if (it!=countMap.end())//(*it).second++;//else//countMap.insert(make_pair(e, 1));//}for (auto e : arr){countMap[e]++;}for (auto& e : countMap){cout << e.first << \":\" << e.second << endl;}

而这里我们可以使用简单的[ ]就实现对水果进行插入并记录次数的原因在于operator[]的底层实现

这是operator[]的实现代码，首先会对key进行插入，并用pair类型来接收返回值，那么就会出现以下两种情况

并对节点的value值进行返回，因此如果这个key不在树里，那么operator[]会将其插入并返回value值，此时的value值为被初始化的值，由于是int类型所以初始值为0，当我们进行++操作那么就将value值变为1，再进行后续的循环时，首先会进行插入操作，但是由于key已经在树里面，则不进行插入，并返回key对应的value值，我们只需将其++就可以实现次数的对应了。

虽然map中的key值不可以被修改，但是value值是可以被修改的，并可以通过operator[]来实现

5、multimap

multimap与map大部分内容都是相同的，唯一的区别在于map中的key值不能重复，而multimap中的key值是可以重复的，正因如此，multimap中并没有重载operator[]操作