C++ STL 容器入门：set 与 map 详解

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. 例题：英语作文

为了方便截取单词，需要以字符的格式读取，并以输入的非单词字符作为分割；如果以字符串读取，就需要我们自己来截取单词，比较麻烦

在 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. 例题：营业额统计

对于第 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. 例题：木材仓库

代码：

#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;
}