C++ map和set(补充)

目录

1.set

 简单使用

 set的迭代器

 set的find  

 set的erase

set的lower_bound和upper_bound

std::multiset

练习题：两个数组的交集

2.map

map的访问及其遍历

使用map统计次数

*练习题：前k个高频单词

1.set

 简单使用

插入1后存在去重效果 

 范围for同样支持

 set的迭代器

普通迭代器和const迭代器都不支持修改

 源码中普通迭代器和const迭代器用的是同一个

 set的find  

使用全局的find查找？ 

 前者时间复杂度O(logn)，后者的时间复杂的是O(n)，即暴力查找

 std:：find算法的源码

 set的erase

 使用erase的前提是set中需要用需要删除的数据，如果没有找到需要删除的数据，使用erase时会出现报错

 判断数据存在的两种方式

    if (s.count(5)){cout << "5存在" << endl;}if (s.find(5) != s.end()){cout << "5存在" << endl;}

set的lower_bound和upper_bound

 调试可知，返回3所在位置的迭代器，set中没有6时返回7所在位置的迭代器。

 综上，返回>=val的位置迭代器

 upper_bound的使用：返回>x位置的迭代器

使用lower_bound和upper_bound删除区间值。前者返回区间的[ ，后者返回区间的)。

std::multiset

不去重排序，其函数接口和set基本保持一致

 使用erase时会删除所有相同的数据

有多个相同的值时使用find会返回哪一个呢？以find(3)为例子，返回中序的第一个3

练习题：两个数组的交集

力扣

class Solution {
public:vector intersection(vector& nums1, vector& nums2) {set s1;for(auto e:nums1){s1.insert(e);}vector v;for(auto e :nums2){if(s1.count(e))v.push_back(e);}return v;}
};

 未通过的原因：没有去重。改正为下面代码即可

class Solution {
public:vector intersection(vector& nums1, vector& nums2) {//去重set s1;for(auto e:nums1){s1.insert(e);}//去重set s2;for(auto e :nums2){s2.insert(e);}//时间复杂度N*logNvectorv;for(auto e1:s1){if(s2.count(e1))v.push_back(e1);}return v;}
};

改进思路如下 

class Solution {
public:vector intersection(vector& nums1, vector& nums2) {//去重set s1;for(auto e:nums1){s1.insert(e);}//去重set s2;for(auto e :nums2){s2.insert(e);}vectorv;auto it1 = s1.begin();auto it2 = s2.begin();while(it1 != s1.end()&&it2 != s2.end()){if(*it1<*it2){++it1;}else if(*it1 > *it2){++it2;}else{v.push_back(*it1);++it1;++it2;}}return v;}
};

2.map

map的访问及其遍历

整体的返回值是迭代器节点里面的数据，节点里面的数据是一个pair。此处编译报错说明pair不支持流插入

 改正如下即可

 也可使用重载的箭头，重载的箭头返回数据的指针，数据的指针是一个pair*，pair*再加一个箭头就可以访问first和second

 也可使用范围for遍历

使用map统计次数

 通过对于insert的理解，可以对上述代码进行改进

 insert有一个返回值返回pair，返回pair后pair::first被设置为一个迭代器。该迭代器要么指向新插入的元素，或者没有插入成功（map中可能存在相同元素），指向已经存在的相同的元素所在的位置

second是一个布尔值，如果新插入了元素就是true，如果已经存在和新插入的元素相等的元素，就是false。

 使用operator[]改进如下

以插入中英文为例使用operator[]

*练习题：前k个高频单词

力扣

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！