福永网站建设公司有没有,网站开发 软件有哪些,温州市住房和城乡建设厅网站,怎么做html5网站吗#x1f431;作者#xff1a;一只大喵咪1201 #x1f431;专栏#xff1a;《C学习》 #x1f525;格言#xff1a;你只管努力#xff0c;剩下的交给时间#xff01; map和set的使用#x1f308;关联式容器⚡键对值#x1f308;set⚡构造函数⚡增删查改#x1f308;… 作者一只大喵咪1201 专栏《C学习》 格言你只管努力剩下的交给时间 map和set的使用关联式容器⚡键对值set⚡构造函数⚡增删查改multisetmap⚡构造函数⚡增删查改⚡operator[]multimapmap和set在题目中的应用⚡统计前K个高频单词⚡求两个数组的交集总结map和set的底层都是二叉搜索树只是做了更进一步的限制使其不会出现单只的情况搜索的时间复杂度保证在O(log2N)具体的底层结构后面本喵再详细介绍现在先来认识以下set和map
关联式容器
首先要知道的是序列式容器这种容器我们之前接触过比如vectorlistdeque等等。 序列式容器 底层为线性的数据结果(物理上或者逻辑上)容器中的元素储存的是元素本身。而且我们之前在使用序列式容器的时候插入数据和删除数据只管操作就行不用考虑其他因素。 关联式容器 存储的是keyvalue结构的键对值在数据检索时比序列式容器效率更高。插入和删除数据时要考虑该数据和它前后数据之间的关联性。 总的来说关联式容器存放的数据不同而且数据前后有一点的关联性。
⚡键对值 键对值用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息。 比如现在要建立一个英汉互译的字典那字典中就得右英文单词和与之对应的中文含义而且它们的关系是一一对应的此时用就可以使用键对值来存放如单词汉语。
在STL中定义了一个键对值的类 这个类的名字叫做pair是一个模板类可以存放任意类型的键对值而且能够自定推演。 它的成员变量右两个分别是first和second结构如first,second。 它也右自己的默认成员函数和普通成员函数。
伪代码形式
template class T1, class T2
struct pair
{typedef T1 first_type;typedef T2 seco_type;T1 first;T2 second;pair():first(T1()),second(T2()){}pair(const T1 a, const T2 b):first(a),second(b){}
};键对值注定是要在类外进行访问的所以使用struct而不用class。
make_pair():
该函数是用来制作一个pair类型的匿名对象的:
pairstring, string(string, 字符串);
make_pair(string, 字符串);上面俩句代码是等价的都是在创建一个pair类型的匿名对象让你选择你会选择哪种方式呢 make_pair()是为了让我们更加方便的使用键值对。 set set和之前学习的容器一样也是一个模板类但是它的底层是关联式容器也就是二叉搜索树并且有很多的成员函数这些接口相信大家大部分都不陌生。 set存放的数据只有一个就是它本身。 ⚡构造函数 构造函数有三个分别是默认构造函数、使用迭代器区间的构造函数、拷贝构造函数。 因为底层是二叉搜索树所有就会涉及到比较构造函数参数就是比较方式是一个仿函数但是默认情况下是有缺省值的。 使用默认构造函数构造出来的s1是空的里面什么都没有。 使用迭代器区间构造出来的s2里面是这段区间中的数据。 拷贝构造函数构造出来的s3内容和s2的完全一样。
set的去重功能
上面使用迭代器区间构造s2的时候原本的数组中有很多个1但是构造出来的set中只有一1。 set具有降重的功能当插入的数据已经存在时就不会再插入这一点在二叉搜索树中就讲解过。 可以看到数组中有多个重复数字用这些数字构造出来的set里面每个数字只存在一个重复的都被去除了。
迭代器的中序移动
在打印set中的数据时我们发现打印出来的结果是升序的在学习二叉搜索树的时候我们知道采用中序遍历的方式打印出来的结果就是升序的。 迭代器时移动的顺序就是中序遍历的顺序所以使用迭代器遍历时得到的结果和中序遍历是一样的。
⚡增删查改
insert(): 插入函数insert有3个重载函数其中第一个是插入一个数据并且返回一个键对值第二个是指定位置插入返回插入的位置第三个是插入一段迭代器区间。 在set中插入原本没有的数据50插入成功返回键对值中迭代器指向新插入的位置布尔值是1。 在set中插入原本就存在的数据5插入石板返回键对值中迭代器指向set中5的位置布尔值是0。
强烈不建议使用指定位置插入。
指定位置向set中插入数据有可能会破环二叉搜索的结构除非在插入之前能够确定不会破坏结构。一般情况下我们都不会指定位置插入。 迭代器区间中的数据全部插入到了set中。 set中原本就存在5所以迭代器区间中的5不会再插入。
find(): 根据指定的值在set中插入如果存在则返回该值所在位置的迭代器如果不存在则返回set的结束位置的迭代器end()。 5存在于set中返回该位置的迭代器。 50不存在于set中返回set的end迭代器。
还有一个接口函数可以代替find该结构名为count() 返回指定数据的个数如果不存在则返回0。
由于set具有降重功能里面不会存在重复的数据所以它在这里的功能是和find一样的只是不过返回的是数字而不是迭代器。 存在时返回值是1不存在时返回值是0。
erase(): 有三个重载函数第一个删除指定迭代器位置的值第二个返回删除指定值的个数第三个删除迭代器区间中所有数据。 第二个重载函数由于set中没有重复值所以返回的值就是1。 使用指定迭代器位置的erase时需要先使用find找到。 使用指定数据的erase时删除成功返回1如果不存在则返回0。 使用迭代器区间的erase时将区间内的数据全部删除。 迭代器区间用的是set的迭代器区间。 修改
在二叉搜索树的时候本喵就说过不支持修改因为很有可能会破环树的结构同样的set也不支持修改。
获取上下边界: 下边界给的数据是2时返回的就是2的迭代器。 上边界给的数据是7时返回的是8的迭代器也就是返回7的下一个数据所在位置的迭代器因为C中的迭代器都是左闭右开区间的。 上边界给的数据是5时返回的是6的迭代器因为5不存在所以返回它下一个数据的迭代器。 lower_boubder(val):返回的iterator val所在的位置的迭代器。upper_bounder(val):返回的iterator val所在的位置迭代器。 但是这两个接口用的非常少仅了解就可以。
其他成员函数的使用包括迭代器我们在学习vectorlist等容器时已经用的炉火纯青了本喵就不再介绍了还有一些很不常用的接口再以后用到的时候再详细介绍。
multiset multiset和set在同一个头文件中而且几乎是一模一样的。 区别在于multiset支持数据重复而set不可以。 重复数据仍然可以插入到multiset中。 set排序 降重multiset排序(不降重) count()
在set中count成员函数和find功能类似但是在multiset中它就有了它的作用。 mutiset中有3个5返回就是3。 multiset中没有50返回就是0。
erase(): erase中的第二个重载函数也是给multiset使用的。 mutiset中有2个3全部被删除所以返回值就是2。 mutiset中没有30所以返回值就是0。
find():
使用find查找multiset中的重复元素时返回的是哪个呢 find找到的是中序遍历的第一个3。
multiset其他方面和set一模一样本喵就不再介绍了。
map map和set一样也是一个关联式容器底层是二叉搜索树。 map中存放的是键对值如上图所示有两个模板参数这两个参数组成一对键对值。 ⚡构造函数 没有使用一个键对值进行构造的构造函数只有一个键对值时只能先创建在使用insert插入。 使用默认构造函数创建的map是空的。 插入键对值时使用make_pair创建匿名对象更加方便。 使用迭代器区间进行初始化。 拷贝构造初始化。
特性 map具有降重功能和set一样。 不能插入相同的键值对和set一样map不支持重复数据。 不能插入key值相同val值不同的键值对。 map中虽然存放的是键值对但是它的判断逻辑都只看key值也就是first所表示的变量。 map也具有排序 降重的功能依据只看key值而不管value值。
⚡增删查改
insert(): 用法和set中的一样只是map插入的是键值对。 插入一个键值对时返回的也是一个键值对返回的键值对中first是插入键值对所在位置的迭代器second是bool值成功就返回1失败就返回0。 迭代器区间插入时map已经有的元素就不再插入了。
同样强烈不建议使用指定位置插入。
find(): 查找时只需要指定要查找键值对中的键值key就可以find是根据key去搜索的。 查找到以后返回键值对所在位置没有找到返回end迭代器。 键值4存在它的value值是李四所以通过返回的迭代器可以找到。 键值5不存在所以返回map的end迭代器。
erase(): 和set中的使用情况一样除了指定迭代器位置和迭代器区间外只需要指定键值key就可以删除对应的键值对。
map和set一样不支持修改因为可能会破坏二叉搜索树的结构。 除了插入这样的增加操作时需要一个键值对其他操作都是根据键值对中的键值key来处理的。
⚡operator[]
现在使用map来统计KV模型例子中水果的个数
void TestMap6()
{string arr[] { 苹果, 西瓜, 香蕉, 草莓, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (auto e : arr){mapstring, int::iterator it countMap.find(e);//map没有该水果插入数量为1if (it countMap.end()){countMap.insert(make_pair(e,1));}//map中有该水果数量加1else{it-second;}}//查看mapfor (auto e : countMap){cout e.first : e.second endl;}cout endl;
}成功统计出了水果的个数此时水果名是key值数量是value值。
还有一种非常不可思议的方式 原本那么一大堆的判断逻辑此时一句代码就搞定了。
要想知道原因就必须了解operator[]成员函数。 键对值中的key值充当下标。 文档中解释调用operator[]相当于在调用上面那一句代码。可以看到这句代码非常长得需要好好分析。 这句代码可以这样解释但是还是有些复杂。
Value operator[](const K key)
{//1.插入 2.查找pairmapK, Value::iterator, bool ret insert(make_pair(key, Value()));//3.修改return ret.first-second;}插入使用insert进行了插入。 查找插入后返回的键对值中有布尔类型插入就返回true否则返回false。 修改最终的返回值是插入键对值中的value。
一个operator[]可以实现3个功能所以可以代替最开始那一堆逻辑。
countMap[e];这句代码是如何实现插入查找修改三个功能呢 首先insert(e)map中如果不存在e则插入返回e的second的引用也就是计数值。如果存在e则不插入直接返回e的second的引用。如果是新插入的e此时e的second的引用是0加加后变成了1。如果不是新插入的对e的second的引用进行加加数量也就被加加了。这里只是用到了operator[]的插入和修改功能没有使用到查找。 multimap multimap和map也是在一个头文件中使用和map也一样就像是multiset和set的关系。 multimap也是支持数据重复的而map不可以。 重复数据仍然可以插入到multimap中同样也只是看key值。 map排序 降重multimap排序(不降重) mutimap中没有operator[]。
如果有它的话operator[e]返回的second应该返回哪个呢毕竟可以找到多个first所以mutimap不提供operator[]成员函数。
insert(): multimap的insert中没有返回键对值的返回的是插入键对值所在位置的迭代器。其他使用都一样。
map和set以及multiset和multimap的用法非常相似可以相互参考。
map和set在题目中的应用
⚡统计前K个高频单词 思路分析 将字典放入到map中统计每个单词的次数。 再将键值对中的key值和value交换并插入到一个vector中。 使用sort按照key进行排序。 然后将排序后vector中键值对的value(也就是字符串)插入到返回vector。 统计之后map中的数据形式pair“单词”,次数。将pair次数,“单词”放入到vector中此时key就成了次数value成了单词。使用sort对vector中的数据进行排序。输出排序后vector中键值对的value也就是单词。 此时的结果i和love位置不对这是因为sort采用的快排快排是一个不稳定的算法所以采用一个稳定算法就可以。 算法库中提供了稳定的排序算法。 但是此时函数不行位置还是不对这是什么原因呢 原因就在于pair类型中对大于号的重载 库中对operator()的重载中主要取决于两个键值对中的key值。
所以需要我们在仿函数中指定更严格的比较方式 当键值对中的first相等时意味着这两个单词的个数相同。 此时在仿函数中指定按照字典序排列。 此时就成功了。
⚡求两个数组的交集 思路分析 首先进行排序 去重将两个数组放在两个set中。 两个set中的数据同时进行比较相等就是交集输出到返回vector中不相等时小的set的迭代器继续向后移动。 上边是思路的示意图。 上边代码可以成功通过。
总结
map和set的使用相对于之前的容器来说确实有一点复杂主要在一些接口上面。要知道set和multiset以及map和mutimap的区别。
