C++ map multimap

### C++ 中 `std::map` 和 `std::multimap` 的区别及用法 #### 定义与基本概念 `std::map` 是一种关联容器，用于存储键值对（key-value pairs），其中每个键都是唯一的。它基于红黑树实现，因此提供了高效的查找、插入和删除操作[^1]。 相比之下，`std::multimap` 也是一种关联容器，但它允许同一个键存在多个映射值。换句话说，在 `std::multimap` 中，相同的键可以对应不同的值[^2]。 --- #### 主要区别 | 特性 | `std::map` | `std::multimap` | |---------------------|------------------------------------|-------------------------------------| | **唯一键约束** | 键必须唯一 | 同一键可有多个对应的值 | | **内部结构** | 基于平衡二叉搜索树 | 类似 `std::map` | | **迭代器行为** | 迭代器指向单个键值对 | 可能返回具有相同键的多个键值对 | --- #### 使用方法 以下是两个容器的基本使用方式： ```cpp #include <iostream> #include <map> int main() { std::map<int, std::string> myMap; myMap[1] = "Apple"; myMap[2] = "Banana"; for (const auto& pair : myMap) { std::cout << pair.first << ": " << pair.second << "\n"; } return 0; } ``` 对于 `std::multimap`，由于允许多个键的存在，其访问逻辑稍显复杂。下面是一个简单的例子展示如何遍历重复键的值： ```cpp #include <iostream> #include <map> int main() { std::multimap<int, std::string> myMultiMap; myMultiMap.insert({1, "Red"}); myMultiMap.insert({1, "Green"}); myMultiMap.insert({2, "Blue"}); for (const auto& pair : myMultiMap) { std::cout << pair.first << ": " << pair.second << "\n"; } // 查找特定键的所有条目 int keyToFind = 1; auto range = myMultiMap.equal_range(keyToFind); for (auto it = range.first; it != range.second; ++it) { std::cout << "Key " << keyToFind << " maps to " << it->second << "\n"; } return 0; } ``` 上述代码展示了如何通过 `equal_range()` 方法获取指定键的所有映射项。 --- #### 性能比较 两者都提供 O(log n) 时间复杂度的操作性能，但由于 `std::multimap` 支持多值映射，可能在某些场景下需要额外处理来管理冗余数据。 ---