头文件
#include<map>初始化
//map<key,value>xx
map<string,string> mp;
map<string,int> mp;方法函数
知道了如何定义初始化可变数组，下面就需要知道如何添加，删除，修改数据。
相关方法函数如下：
| 代码 | 含义 |
|---|---|
| mp.find(key) | 返回键为key的映射的迭代器 O(logN) 注意：用find函数来定位数据出现位置，它返回一个迭代器。当数据存在时，返回数据所在位置的迭代器，数据不存在时，返回mp.end() |
| mp.erase(it) | 删除迭代器对应的键和值O(1) |
| mp.erase(key) | 根据映射的键删除键和值 O(logN) |
| mp.erase(first,last) | 删除左闭右开区间迭代器对应的键和值 O(last-first) |
| mp.size() | 返回映射的对数 O(1) |
| mp.clear() | 清空map中的所有元素 O(N) |
| mp.insert() | 插入元素，插入时要构造键值对 |
| mp.empty() | 如果map为空，返回true，否则返回false |
| mp.begin() | 返回指向map第一个元素的迭代器（地址） |
| mp.end() | 返回指向map尾部的迭代器（最后一个元素的=下一个=地址） |
| mp.rbegin() | 返回指向map最后一个元素的反向迭代器（地址） |
| mp.rend() | 返回指向map第一个元素前面(上一个）的反向迭代器（地址） |
| mp.count(key) | 查看元素是否存在，因为map中键是唯一的，所以存在返回1，不存在返回0 |
| mp.lower_bound() | 返回一个迭代器，指向键值>=key的第一个元素 |
| mp.upper_bound() | 返回一个迭代器，指向键值> key的第一个元素 |
注意：
查找元素是否存在时，可以使用
1️⃣mp.find()2️⃣mp.count()3️⃣mp[key]
但是第三种情况，如果不存在对应的key时，会自动创建一个键值对（产生一个额外的键值对空间）
所以为了不增加额外的空间负担，最好使用前两种方法
使用迭代器进行正反向遍历
⭐️ mp.begin()和mp.end()用法：
用于正向遍历map
map<int,int> mp;
mp[1] = 2;
mp[2] = 3;
mp[3] = 4;
auto it = mp.begin();
while(it != mp.end())
{
cout << it->first << " " << it->second << "\n";
it ++;
}
12345678910结果：
1 2
2 3
3 4
123⭐️ mp.rbegin()和mp.rend()
用于=逆向=遍历map
map<int,int> mp;
mp[1] = 2;
mp[2] = 3;
mp[3] = 4;
auto it = mp.rbegin();
while(it != mp.rend())
{
cout << it->first << " " << it->second << "\n";
it ++;
}
12345678910结果：
3 4
2 3
1 2二分查找lower_bound() upper_bound()
map的二分查找以第一个元素（即键为准），对键进行二分查找
返回值为map迭代器类型
#include<bits/stdc++.h>
using namespace std;
int main()
{
map<int, int> m{{1, 2}, {2, 2}, {1, 2}, {8, 2}, {6, 2}};//有序
map<int, int>::iterator it1 = m.lower_bound(2);
cout << it1->first << "\n";//it1->first=2
map<int, int>::iterator it2 = m.upper_bound(2);
cout << it2->first << "\n";//it2->first=6
return 0;
}
123456789101112133️⃣ 添加元素3️⃣
//先声明
map<string,string> mp;
12方式一：
mp["学习"] = "看书";
mp["玩耍"] = "打游戏";
12方式二：插入元素构造键值对
mp.insert(make_pair("vegetable","蔬菜"));
1方式三：
mp.insert(pair<string,string>("fruit","水果"));
1方式四:
mp.insert({"hahaha","wawawa"});
14️⃣访问元素4️⃣
4.1.下标访问：(大部分情况用于访问单个元素)
mp["菜哇菜"] = "强哇强";
cout << mp["菜哇菜"] << "\n";//只是简写的一个例子，程序并不完整
124.2.遍历访问：
方式一：迭代器访问
map<string,string>::iterator it;
for(it = mp.begin(); it != mp.end(); it++)
{
// 键 值
// it是结构体指针访问所以要用 -> 访问
cout << it->first << " " << it->second << "\n";
//*it是结构体变量 访问要用 . 访问
//cout<<(*it).first<<" "<<(*it).second;
}
123456789方式二：智能指针访问
for(auto i : mp)
cout << i.first << " " << i.second << endl;//键，值
12方式三：对指定单个元素访问
map<char,int>::iterator it = mp.find('a');
cout << it -> first << " " << it->second << "\n";
12方式四：c++17特性才具有
for(auto [x, y] : mp)
cout << x << " " << y << "\n";
//x,y对应键和值
1235 与unordered_map的比较
这里就不单开一个大目录讲unordered_map了，直接在map里面讲了。
1 内部实现原理
map ：内部用红黑树实现，具有 自动排序 （按键从小到大）功能。
unordered_map ：内部用哈希表实现，内部元素无序杂乱。
2 效率比较
map ：
- 优点：内部用红黑树实现，内部元素具有有序性，查询删除等操作复杂度为O ( l o g N ) O(logN)O(logN)
- 缺点：占用空间，红黑树里每个节点需要保存父子节点和红黑性质等信息，空间占用较大。
unordered_map ：
- 优点：内部用哈希表实现，查找速度非常快（适用于大量的查询操作）。
- 缺点：建立哈希表比较耗时。
两者方法函数基本一样，差别不大。
注意：
- 随着内部元素越来越多，两种容器的插入删除查询操作的时间都会逐渐变大，效率逐渐变低。
- 使用
[]查找元素时，如果元素不存在，两种容器都是创建一个空的元素；如果存在，会正常索引对应的值。所以如果查询过多的不存在的元素值，容器内部会创建大量的空的键值对，后续查询创建删除效率会 大大降低 。查询容器内部元素的最优方法是：先判断存在与否，再索引对应值（适用于这两种容器）
// 以 map 为例 map<int, int> mp; int x = 999999999; if(mp.count(x)) // 此处判断是否存在x这个键 cout << mp[x] << "\n"; // 只有存在才会索引对应的值，避免不存在x时多余空元素的创建 12345
模拟
/******************** 哈希表 开放定址法 ********************/
#define maxn (1<<17)
#define mask (maxn-1)
#define DataType int
#define Boolean int
#define NULLKEY (1<<30)
typedef struct {
DataType data[maxn];
}HashTable;
void HashInit(HashTable *ht) {
int i;
for(i = 0; i < maxn; ++i) {
ht->data[i] = NULLKEY;
}
}
int HashGetAddr(DataType key) {
return key & mask;
}
Boolean HashSearchKey(HashTable *ht, DataType key, int *addr) {
int startaddr = HashGetAddr(key);
*addr = startaddr;
while(ht->data[*addr] != key) {
*addr = HashGetAddr(*addr + 1);
if(ht->data[*addr] == NULLKEY) {
return 0;
}
if(*addr == startaddr) {
return 0;
}
}
return 1;
}
int HashInsert(HashTable *ht, DataType key) {
int addr = HashGetAddr(key);
int retaddr;
if ( HashSearchKey(ht, key, &retaddr ) ) {
return retaddr;
}
while(ht->data[addr] != NULLKEY)
addr = HashGetAddr(addr + 1);
ht->data[addr] = key;
return addr;
}
int HashRemove(HashTable *ht, DataType key) {
int addr;
if ( !HashSearchKey(ht, key, &addr ) ) {
return NULLKEY;
}
ht->data[addr] = NULLKEY;
return addr;
}
/******************** 哈希表 开放定址法 ********************/