头文件

#include<map>

初始化

//map<key,value>xx
map<string,string> mp;
map<string,int> mp;

方法函数
知道了如何定义初始化可变数组，下面就需要知道如何添加，删除，修改数据。

相关方法函数如下：

注意：
查找元素是否存在时，可以使用
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;
}

12345678910111213

3️⃣ 添加元素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"});
1

4️⃣访问元素4️⃣

4.1.下标访问：(大部分情况用于访问单个元素)

mp["菜哇菜"] = "强哇强";
cout << mp["菜哇菜"] << "\n";//只是简写的一个例子，程序并不完整
12

4.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对应键和值
123

5 与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;
}

/******************** 哈希表 开放定址法 ********************/

原文章：(75条消息) C++STL之map详解_c++stlmap_行码棋的博客-CSDN博客