算法学习入门--- set与map（C++）
目录
1.set、multiset介绍
- set不能存相同元素，multiset能存相同元素，存10个1前者只会存1个1，后者会存10个1，除此以外所有的函数功能相同。所以，set是具有去重的功能的
- 创建格式：set<type> mp1
- size：返回实际元素个数
- empty：返回是否为空
- begin、end：可以使用for遍历整个set（红黑树），遍历时按照中序遍历来遍历的，根据红黑树的性质，遍历结果会是一个有序的序列；begin表示的是第一个元素的迭代器，end表示的是最后一个元素之后的迭代器，所以遍历范围为 [begin,end)；迭代器作为一个抽象化的指针（无法被直接访问的指针，即无法cout其地址），无法通过 < 来和 end迭代器 比较，所以必须要使用 it != mp.end()
- insert：插入一个元素，O(logN)
- erase：删除一个元素，O(logN)
- find：查找一个元素，返回的是迭代器，如果没找到就返回set.end()，O(logN)
- count：查询元素出现的次数，因为set中的元素唯一，所以只会返回1（存在）或0（不存在），一般用来查询元素是否在红黑树中，O(logN)
- lower_bound：大于等于x的最小元素，返回的是迭代器
- upper_bound：大于x的最小元素，返回的是迭代器
代码演示：
#include<iostream> #include<set> using namespace std; int a[]={10,10,60,20,70,80,30,90,40,100,50}; int main() { set<int> mp; for(auto x:a)mp.insert(x); //for(auto it = mp.begin();it != mp.end();it++) //cout<<*it<<" "; for(auto x:mp)cout<<x<<" "; cout<<endl; mp.erase(60); mp.erase(100); for(auto x:mp)cout<<x<<" "; cout<<endl; if(mp.count(10))cout<<"Yes"<<" "; else cout<<"No"<<" "; if(mp.count(1))cout<<"Yes"<<" "; else cout<<"No"<<" "; cout<<endl; auto x = mp.lower_bound(20); auto y = mp.upper_bound(20); cout<<*x<<" "<<*y; return 0; }
2.map、multimap介绍
- map相当于set当中存取的数据为pair类型
- map当中，比较方式是以key来做比较的，换言之遍历map时，中序遍历的是key而不是key所对应的value；map只允许一个键对应一个值，multimap允许一个键对应多个值
- 创建格式：map<type,type> mp1
- size、empty、begin、end与上同，不解释
- insert：插入的元素为键值对，insert({1,2})
- operator[]：重载[]，使得map可以像数组一样使用，并且重载[]这一步操作C++提供的模板已经帮我们搞好了，直接用即可；但使用[]访问map时，会把不存在于map当中的键值对插入进去，并给键所对应的值赋上一个0；为了防止这个情况发生，可以先count一下看看这个键值对是否存在，然后再使用[]访问
- erase：删除一个元素，传入key即可删除
- count：查看一个元素是否存在，传入key即可
- lower_bound，upper_bound：比较的是传入值与键的大小，其他与set不变
代码演示：
#include<iostream> #include<map> using namespace std; void print(map<string,int>& mp) { for(auto& p:mp) cout<<p.first<<" "<<p.second<<endl; } int main() { map<string,int> mp; mp.insert({"zhang",1}); mp.insert({"lisi",2}); mp.insert({"wang",3}); print(mp); cout<<mp["zhang"]<<endl; if(mp["zhao"]==4)cout<<"yes"<<endl; //if(mp.count("zhao")&&mp["zhao"]==4)cout<<"yes"<<endl; else cout<<"no"<<endl; print(mp); mp.erase("zhao"); print(mp); return 0; }
3.洛谷---英语1（eng1）- 英语作文
为了方便截取单词，需要以字符的格式读取，并以输入的非单词字符作为分割；如果以字符串读取，就需要我们自己来截取单词，比较麻烦
在c++中，string类型字符串重新赋空的代码为
map的键值对代表的是<高级词汇,词汇分数>
代码：
#include<iostream> #include<map> #include<cstdio> using namespace std; #define int long long signed main() { int N,P;cin>>N>>P; map<string,int> sc;//词汇和成绩对照表 while(N--) { string in;int num;cin>>in>>num; sc.insert({in,num}); } string word; char cur; int ret=0; while(scanf("%c",&cur)!=EOF)//while((cur=getchar())!=EOF) { if((cur>='a'&&cur<='z')||(cur>='A'&&cur<='Z')||(cur>='0'&&cur<='9'))//单词输入 word+=cur; else { if(sc.count(word)) ret+=sc[word];;//说明一个单词结束了 } } cout<<(ret%P); return 0; }代码易错点：
cin遇到空格时会自动跳过，那么空格分隔的特性就失效了
scanf虽然%s读取会省略空白字符，但%c读取不会；getchar读取失败时和scanf一样，返回EOF；scanf返回值为一个整数，表示成功读取的变量个数（占位符与输入数据格式不匹配也算失败读取），一个变量都没有成功读取发生错误则返回EOF（-1），如果全都只是占位符与输入数据格式不匹配那么返回0
4.洛谷--- [HNOI2002] 营业额统计
对于第i天的营业额来说，就是从[0,i-1]范围中找到和他相差最小的那个元素
例如当前元素为4 ，从1 2 5 7 8 9 当中寻找，那么找到的那个数是比他要大的5，此处视作y
例如当前元素为3，从1 2 5 7 8 9 当中寻找，那么找到的那个书是比他要小的2，此处视作z
最终获得的波动值应该为min(|y-x|,|z-x|)
寻找大于等于x的最小值时，使用lower-bound即可
当序列有序时，迭代器it--以后，就能获得小于等于x的最大值
对于红黑树遍历来说，因为是有序的，所以可以直接it--，不需要再对其进行排序，但需要注意的是：不能*(it-1)，只能it--后再对it进行解引用，换言之只能让迭代器变化位置，但不能对迭代器进行指针运算
当x正好大于等于set中的第一个元素，那么it--可能会存在越界访问的情况，此时可以初始化给到一个左右护法，即整个set的前面加上一个-∞，整个set的后面加上一个+∞，那么就不会再有越界访问的情况（如下图所示）
正确性检验：无论是it所指向的元素多小，最要比代表-∞的值要大，这个-∞的值可以取为-1e7，+∞也是这样判断的
代码：
#include<iostream> #include<set> #include<algorithm> #include<cmath> using namespace std; #define int long long signed main() { int d;cin>>d; set<int> mp; //第一次为特殊情况 int fst,ret=0;cin>>fst; mp.insert(fst);ret+=fst;d--; mp.insert(1e7); mp.insert(-1e7); while(d--) { int in;cin>>in; auto it = mp.lower_bound(in);int y = *it; it--;int z = *it; ret+=min(abs(y-in),abs(z-in)); mp.insert(in); } cout<<ret; return 0; }5.洛谷---【深基17.例5】木材仓库
代码：
#include<iostream> #include<set> #include<cmath> using namespace std; #define int long long signed main() { int m;cin>>m; set<int> mp; mp.insert(1e10); mp.insert(-1e10); while(m--) { int flag,len;cin>>flag>>len; if(flag==1) { //先判断在仓库中是否存在 if(mp.count(len))cout<<"Already Exist"<<endl; mp.insert(len); } else { //仓库为空 if(mp.size()==2) { cout<<"Empty"<<endl; continue; } //开始寻找差值最小的木材 auto it = mp.lower_bound(len);int y = *it; it--;int z = *it; if(abs(y-len)>=abs(z-len)) { cout<<z<<endl; mp.erase(z); } else { cout<<y<<endl; mp.erase(y); } } } return 0; }
