成员方法 功能
begin() 返回指向容器中第一个（注意，是已排好序的第一个）键值对的双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
end() 返回指向容器最后一个元素（注意，是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 begin() 结合使用。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
rbegin() 返回指向最后一个（注意，是已排好序的最后一个）元素的反向双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
rend() 返回指向第一个（注意，是已排好序的第一个）元素所在位置前一个位置的反向双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
cbegin() 和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
cend() 和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
crbegin() 和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
crend() 和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的键值对。
find(key) 在 map 容器中查找键为 key 的键值对，如果成功找到，则返回指向该键值对的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
lower_bound(key) 返回一个指向当前 map 容器中第一个大于或等于 key 的键值对的双向迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
upper_bound(key) 返回一个指向当前 map 容器中第一个大于 key 的键值对的迭代器。如果 map 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
equal_range(key) 该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的键为 key 的键值对（map 容器键值对唯一，因此该范围最多包含一个键值对）。
empty() 若容器为空，则返回 true；否则 false。
size() 返回当前 map 容器中存有键值对的个数。
max_size() 返回 map 容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同。
operator[] map容器重载了 [] 运算符，只要知道 map 容器中某个键值对的键的值，就可以向获取数组中元素那样，通过键直接获取对应的值。
at(key) 找到 map 容器中 key 键对应的值，如果找不到，该函数会引发 out_of_range 异常。
insert() 向 map 容器中插入键值对。
erase() 删除 map 容器指定位置、指定键（key）值或者指定区域内的键值对。后续章节还会对该方法做重点讲解。
swap() 交换 2 个 map 容器中存储的键值对，这意味着，操作的 2 个键值对的类型必须相同。
clear() 清空 map 容器中所有的键值对，即使 map 容器的 size() 为 0。
emplace() 在当前 map 容器中的指定位置处构造新键值对。其效果和插入键值对一样，但效率更高。
emplace_hint() 在本质上和 emplace() 在 map 容器中构造新键值对的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示键值对生成位置的迭代器，并作为该方法的第一个参数。
count(key) 在当前 map 容器中，查找键为 key 的键值对的个数并返回。注意，由于 map 容器中各键值对的键的值是唯一的，因此该函数的返回值最大为 1。

Map 是什么

Map是从键（ keykey ）到值（ valuevalue ）的映射，其内部实现是一棵以 keykey 为关键码的红黑树

Map的相关操作

头文件

  1. #include<map>

声明：

像这样：

  1. map<key的类型，value的类型>名称；

比如：

map<long long,bool>mp;
map<string,int>mp;
map<pair<int,int>,vector<int>>mp;

就像其他需要排序的数据类型一样， keykey 为一个结构体的 mapmap ，需要重载小于号

struct pos{
    int x,y,s;
    string move[100];
};
map<pos,int>mp;
bool operator <(const pos &ai,const pos &bi)
{
    return (ai.x==bi.x)?ai.y>bi.y:ai.x>bi.x;
}

[]运算符

mapmap 重载了[]运算符， map[key]map[key] 返回 keykey 到 valuevalue 的引用，时间复杂度 O(log n)O(logn)
[]操作符是 mapmap 最吸引人的地方。我们可以很方便地通过 map[key]map[key] 来得到 keykey 对应的 valuevalue ，还可以对 map[key]map[key] 进行赋值操作，改变 keykey 对应的 valuevalue 。
若查找的 keykey 不存在，则执行 map[key]map[key] 后， mapmap 会自动新建一个二元组 (key,zero)(key,zero) ，并返回 zerozero 的引用。

eg.
map<string,int>mp;
for(int i=1;i<=n;i++)
{
    string s;
    int num;
    cin>>s>>num;
    mp[s]=num;
}
for(int i=1;i<=m;i++)
{
    string s;
    cin>>s;
    cout<<mp[s]<<endl;
}

map.size()

统计 mapmap 中元素个数，函数返回一个整形变量，表示 mapmap 中元素个数，时间复杂度 O(1)O(1)

用法：名称.size();
eg.
int num=mp.size();

map.empty()

检查 mapmap 是否为空，返回一个 boolbool 型变量，1表示 mapmap 为空，否则为非空，时间复杂度 O(1)O(1)

用法：名称.empty();
eg.
if(mp.empty())
    cout<<"Mymap is Empty."<<endl;

map.clear()

清空 mapmap ，无返回值

用法：名称.clear();
eg.
mp.clear();

map.count(x)

返回 mapmap 中 keykey 为 xx 的元素个数，时间复杂度为 O(log n)O(logn)

用法：名称.count(x)
eg.
if(!mp.count(x))
    mp[x]=1;

迭代器

双向访问迭代器，不支持随机访问，支持星号解除引用，仅支持“++”，“—”这两个算术操作

引用和操作：

map<类型,类型>::iterator it;
eg.
map<int,int>::iterator it=mp.begin();
it++;
it--;

若把 it++it++ ，则 itit 将会指向“下一个”元素。这里的下一个是指在 keykey 从小到大排序的结果中，排在 itit 下一名的元素。同理，若把 it—it−− ，则 itit 会指向排在上一个的元素
“++”，“—”操作的复杂度均为 O(log n)O(logn)
对 mapmap 的迭代器解除引用后，将得到一个二元组 pair<…,…>pair<…,…>

遍历 map 及访问其中的元素

for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++)
    if(it->second==ans)     //访问二元组中第二个，即value
        cout<<it->first<<endl;      //访问key

map.find(x)

在 mapmap 中查找 keykey 为 xx 的二元组，并返回指向该二元组的迭代器，若不存在，返回 map.end()map.end() ，时间复杂度为 O(log n)O(logn)

用法：名称.find(x);
eg.
if(mp.find(s)!=mp.end())
    cout<<"Have Found!"<<endl;

map.insert(pair<…,…>)

在 mapmap 中插入，参数是 pairpair<_key_._type_,_value_._type_> ，返回插入地址的迭代器和是否插入成功的 boolbool 并成的 pairpair ，时间复杂度为 O(log n)O(logn)
PS： insertinsert 在进行插入的时候是不允许有重复的键值的，如果新插入的键值与原有的键值重复则插入无效

用法：名称.insert(pair<key的类型,value的类型>);
eg.
mp.insert(make_pair(2,3));

map.erase( 参数 )

删除，参数可以是 pairpair 或者迭代器，返回下一个元素的迭代器，时间复杂度为 O(log n)O(logn)

用法：名称.erase(参数);
eg.
map<int,int>::iterator it=mp.begin();
mp.erase(it);
mp.erase(make_pair(2,3));

STL之map