STL_map

map简介

map描述的是一种对应关系，类似于一种函数，实质是一种映射

定义map：

#include<map> //库函数
map<string,int> mp; //map的定义
m["cealivanus"]=100; //赋值
cout<<mp["cealivanus"]; //输出1

此时，map的定义表示每一个string对应一个int，前边为自变量后面为因变量。

基本成员函数：

mp.find(x); //查找返回因变量为x的自变量
mp.count(x); //判断x为下标的元素是不是在a中，是就返回1，不是就返回0
mp.erase(x); //删除a中x为下标的元素
mp.size(); //返回a中元素的个数
mp.empty(); //返回mp是否为空
mp.clear(); //清空mp
mp.begin(); //返回映射中第一个元素
mp.end(); //返回到map中最后一个元素后面的理论元素

更多用法见：STL教程（七）——map_map.begin-CSDN博客

在对应关系的题目中，map方便快捷

PS：当数据范围很大时，map可以用作桶排序

单次操作时间复杂度：O（lg n)

例题：洛谷P5266P5266 【深基17.例6】学籍管理 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include <bits/stdc++.h>
#include <map>
#define fast                          \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(nullptr);
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
map<string,int> m;
int main()
{
    fast;
    int n;
    cin>>n;
    while(n--)
    {
        int op;string name;
        cin>>op;
        if(op!=4) cin>>name;
        switch (op)
        {
        case 1:
            int sco;
            cin>>sco;
            m[name]=sco;
            cout<<"OK\n";
            break;
        case 2:
            if(m.count(name)) cout<<m[name]<<'\n';
            else cout<<"Not found\n";
            break;
        case 3:
            if(m.count(name)) 
            {
                m.erase(name);
                cout<<"Deleted successfully\n";
            }
            else cout<<"Not found\n";
            break;
        case 4:
            cout<<m.size()<<'\n';
            break;
        default:
            break;
        }
    }
    return 0;
}

洛谷P5250P5250 【深基17.例5】木材仓库 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include <bits/stdc++.h>
#include <map>
using namespace std;
int i, j, n, x, y;
map<int, int> m;
int main()
{
    cin >> n;
    while(n--)
    {
        cin >> x >> y;
        if (x == 1)
        {
            if (m.count(y))
                cout << "Already Exist" << endl;
            else
                m[y] = 1;
        }
        else
        {
            if (m.empty())
                cout << "Empty" << endl;
            else if (m.count(y))
            {
                m.erase(y);
                cout << y << endl;
            }
            else
            {
                m[y] = 1;            
                auto it = m.find(y); 
                auto it2 = it;
                it++;
                if (it2 == m.begin())
                { 
                    cout << it->first << endl;
                    m.erase(it);
                }
                else if (it == m.end())
                { 
                    cout << (--it2)->first << endl;
                    m.erase(it2);
                }
                else if (y - (--it2)->first > it->first - y)
                {
                    cout << it->first << endl;
                    m.erase(it);
                }
                else
                {
                    cout << it2->first << endl;
                    m.erase(it2);
                }
                m.erase(y); 
            }
        }
    }
    return 0;
}