C++ map容器用法详解（附带实例）

map 是一种基于红黑树（无须深入理解红黑树的原理）的关联容器，支持快速插入、查找和删除操作，并能保持内部元素的有序性。

在 map 中，每个元素都由一个键和与之关联的值组成。可以将 map 类比为一个箱子：你给它一件物品（变量），它会返回给你对应的另一件物品（另一个变量）。我们无须深究 map 的底层结构，只需了解如何正确使用它以及相关操作的时间复杂度即可。

C++ map的结构

在 map 中，一个键（key）唯一确定了一个 <key, value> 键-值对（key-value pair）。得益于其内部的特殊结构，各项操作的效率表现出色，如下图所示：

C++ map的初始化

在使用 map 之前，需要引入对应的头文件。如果已经包含万能头文件（如 <bits/stdc++.h>），则无须再引入与 map 相关的头文件。例如：

#include <map>
// #include <bits/stdc++.h>        // 万能头文件中已包含map
using namespace std;              // map位于std命名空间中

我们可以通过以下方式声明一个 map，其中 T_key 和 T_value 是数据类型，可以是 int、double、char 等基本数据类型，也可以是自定义的结构体。需要注意的是，当使用自定义结构体作为键时，必须重载小于（<）运算符。

通常情况下，我们只需声明一个空的 map，然后向其中插入键-值对：

map<T_key, T_value> mp;  // T_key和T_value为数据类型
map<int, int> mp_int;    // 声明一个键-值对类型为<int,int>的map

如果要使用自定义的结构体作为键，则需要重载小于号运算符。示例代码如下：

// 定义结构体 Node
struct Node {
    int x, y;
    // 重载小于运算符，用于 map 排序
    bool operator<(const Node &u) const {
        return x == u.x ? y < u.y : x < u.x;
    }
};

// 声明一个键-值对类型为 <Node, int> 的 map
map<Node, int> mp_Node_int;

在 map 中，每个键（key）唯一对应一个值（value）。不同的键可以对应相同的值，这类似于函数中的自变量和因变量的关系。

C++ map的基本操作

下表列出了 map 常用的方法及其时间复杂度。

表：map 常用的方法及其时间复杂度

方法	作用	时间复杂度
insert({key, value})	向 map 中插入一个键-值对 <key,value>	O(log n)
erase(key)	删除 map 中指定的键-值对	O(log n)
find(key)	查找 map 中指定键对应的键-值对的迭代器	O(log n)
operator[key]	查找 map 中指定键对应的值	O(log n)
count(key)	查找 map 中键的数量，由于键是唯一的，故只返回 0 或 1	O(log n)
size()	返回 map 中键-值对的数量	O(1)
clear()	清空 map 中的所有键-值对	O(n)
empty()	判断 map 是否为空	O(1)
begin()	返回 map 中第一个键-值对的迭代器	O(1)
end()	返回 map 中最后一个键-值对的下一个迭代器	O(1)

在执行取值运算（[] 运算符）时，必须确保键存在，否则可能产生错误。通常可以通过以下两种方法来判断键是否存在：

map<int, int> mp;          // map 的声明

// 方法一：通过 find() 函数判断，返回键-值对的迭代器；如果未找到，返回 end()
if (mp.find(key) != mp.end()) {
    cout << mp[key] << '\n';
}

// 方法二：通过 count 判断键是否存在
if (mp.count(key)) {
    cout << mp[key] << '\n';
}

遍历 map 中的所有键-值对的两种方法如下：

map<int, int> mp;

// 方法一：使用 auto 关键字进行遍历（推荐）
for (auto &i : mp) {
    cout << i.first << " " << i.second << '\n';
}

// 方法二：使用迭代器进行遍历（不推荐）
for (map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it) {
    cout << it->first << " " << it->second << '\n';
}

需要注意的是，STL 中还有一种名为 unordered_map 的数据结构，它是基于哈希表而不是红黑树来实现的。虽然它的平均时间复杂度更低（接近 O(1)），但在特殊情况下可能退化到 O(n) 。因此，除非明确要求或性能瓶颈特别明显，通常直接使用 map 即可满足要求。

C++ map实际应用

【实例】 StarryCoding P59气球数量。空中有 n 个气球，每个气球都有一个颜色 coli（用字符串表示）。你的任务是计算每种颜色的气球数量，并按照气球出现的顺序进行排序输出。

输入格式：
第一行包含一个整数 T，表示样例的数量（1≤T≤10）。

对于每个样例：

• 第一行包含一个整数 n，表示气球的总数（1≤n≤100）。
• 接下来的 n 行，每行包含一个表示颜色的字符串 coli（1≤∣coli∣≤50）。
• 字符串仅包含小写英文字母。

输出格式：
对于每个样例，按顺序输出每种颜色的气球的数量。

样例如下：


本题中运用了 string 类型。这种类型非常简单，可以直接作为 map 的键（key），这是一个常用的用法。

我们可以利用 map 给每种颜色对应一个数量，具体思路如下：每输入一个气球的数据时，更新 map 中对应的内容。如果map中不存在对应的键，则说明该颜色第一次出现，同时记录到向量中。

输出时，只需按照向量中记录的顺序，逐一输出颜色和数量。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;          // 样例数
    cin >> t;
    while (t--) {
        int n;      // 每个样例的气球数量
        cin >> n;

        map<string, int> mp;   // 记录颜色及其数量
        vector<string> v;      // 按顺序记录出现过的颜色

        for (int i = 1; i <= n; ++i) {
            string col;
            cin >> col;

            // 如果颜色 col 已经出现过，则直接将对应的数量 ++
            // 如果没有出现过，则这个颜色 col 的气球数量为 1
            if (mp.count(col))
                ++mp[col];
            else {
                mp[col] = 1;
                v.push_back(col);   // 记录颜色出现的顺序
            }
        }

        // 按照向量中的元素自动按照出现的顺序进行排序
        for (auto &col : v)
            cout << col << ' ' << mp[col] << '\n';
    }
    return 0;
}