C++STL multimap与map使用区别

33次阅读

kquote>std::map要求键唯一，每个键仅映射一个值，支持operator[]；std::multimap允许键重复，可存储多个相同键的键值对，不支持operator[]，需用equal_range访问所有值。kquote>

C++ STL中的

std::multimap

和

std::map

，它们最核心的区别在于对键（key）的唯一性处理：

std::map

坚持键的唯一性，每个键只能映射到一个值；而

std::multimap

则允许同一个键关联多个不同的值。这个看似简单的差异，却深刻地决定了它们在不同场景下的适用性与内部行为。选择哪一个，往往取决于你的数据模型是否天然允许或需要重复的键。

解决方案

在我看来，理解

std::map

和

std::multimap

的使用区别，首先要从它们各自的设计哲学说起。

std::map

就像一本严谨的字典，每个词条（键）都只对应一个唯一的解释（值）。如果你尝试给一个已经存在的词条添加新的解释，它通常会忽略你的新尝试（

insert

方法），或者直接用新的解释覆盖旧的（

operator[]

）。这种行为非常适合那些一对一映射的数据结构，比如用户ID到用户资料、商品SKU到商品详情等等，确保了数据的一致性和唯一性。

而

std::multimap

则更像一本多义词词典，同一个词条可以有多个不同的解释，并且这些解释都会被完整地保留下来。当你用一个已存在的键插入新的值时，它不会覆盖旧值，而是简单地添加一个新的键值对。这对于那些一对多关系的数据模型简直是天作之合，例如一个事件时间戳可能对应多个日志条目，或者一个关键词可能指向多篇文章。

它们两者在底层实现上，通常都基于自平衡二叉搜索树（比如红黑树），这保证了插入、删除、查找等操作的对数时间复杂度

O(logN)

。但是，由于对键唯一性的不同处理，它们在接口和实际使用中存在一些关键差异：

立即学习“k.cn/s/6e7abc4abb9f" style="text-decoration: underline !important; color: blue; font-weight: bolder;" rel="nofollow" target="_blank">C++免费学习笔记（深入）”；

operator[]

的可用性：
- std::map
  提供了
  operator[]
  ，你可以通过
```
myMap[key] = value;
```
  直接访问或修改与键关联的值。如果键不存在，
  operator[]
  会自动插入一个默认构造的新元素，这非常方便。
- std::multimap
  不提供
  
  operator[]
  
  。原因很简单：如果一个键有多个值，
  operator[]
  应该返回哪一个呢？这种歧义使得它无法提供这样的接口。所以，你不能直接通过
```
myMultimap[key]
```
  来获取或设置值。
插入行为：
- std::map
  的
```
insert({key, value})
```
  方法在键已存在时不会执行插入操作。如果你想强制更新，需要使用
```
myMap[key] = newValue;
```
  或者
```
myMap.at(key) = newValue;
```
  。
- std::multimap
  的
```
insert({key, value})
```
  方法总是会插入新的键值对，即使键已经存在。它不会覆盖任何旧值。
查找多个值：
- 对于
  std::map
  ，
```
find(key)
```
  返回的迭代器直接指向唯一的匹配项（如果存在）。
- 对于
  std::multimap
  ，当你需要查找所有与某个键关联的值时，你通常会使用
```
equal_range(key)
```
  。这个方法会返回一对迭代器，分别指向第一个匹配项和最后一个匹配项的下一个位置，你可以通过遍历这个范围来获取所有关联的值。当然，
```
lower_bound(key)
```
  和
```
upper_bound(key)
```
  也可以实现类似的功能。

这是一个简单的代码示例，展示了它们的核心行为差异：

#include <iostream> #include <map> #include <multimap> #include <string>  int main() {     // std::map 示例     std::map<int, std::string> myMap;     myMap.insert({1, "Apple"});     myMap.insert({2, "Banana"});     myMap.insert({1, "Orange"}); // 键1已存在，此插入操作会被忽略      std::cout << "std::map 键1的值 (首次插入): " << myMap[1] << std::endl; // 输出: Apple      myMap[1] = "Grape"; // 使用 operator[] 覆盖键1的值     std::cout << "std::map 键1的值 (operator[] 覆盖后): " << myMap[1] << std::endl; // 输出: Grape      std::cout << "---------------------------------" << std::endl;      // std::multimap 示例     std::multimap<int, std::string> myMultimap;     myMultimap.insert({1, "Red"});     myMultimap.insert({2, "Green"});     myMultimap.insert({1, "Blue"});  // 键1已存在，但会插入新元素     myMultimap.insert({1, "Yellow"}); // 键1已存在，再次插入新元素      std::cout << "std::multimap 键1的所有值:" << std::endl;     auto range = myMultimap.equal_range(1);     for (auto it = range.first; it != range.second; ++it) {         std::cout << "  " << it->second << std::endl;     }     // 预期输出:     //   Red     //   Blue     //   Yellow (顺序可能因插入顺序和底层实现而异，但都会被保留)      // 尝试在 multimap 上使用 operator[] 会导致编译错误     // myMultimap[1] = "Purple"; // 错误: no operator "[]" matches these operands      return 0; }

这个例子清楚地展示了

map

如何通过

operator[]

覆盖值，以及

multimap

如何保留所有重复键的值，并需要通过

equal_range

来访问它们。这是我个人在实际开发中经常需要提醒自己和同事的地方，尤其是在从

map

切换到

multimap

时，

operator[]

的缺失是一个常见的“坑”。

什么时候我们应该优先选择

std::map

而不是

std::multimap

？

选择

std::map

的场景通常非常明确：当你的数据模型中，每个键都必须是唯一的，并且你只关心与这个键关联的“唯一”值时。

数据天然具有唯一性约束： 比如，你正在管理一个用户数据库，每个用户都有一个唯一的ID。那么
```
std::map<UserID, UserProfile>
```
就是理想的选择。你不会希望同一个用户ID对应多份不同的用户资料，那会引发数据混乱。
需要快速、直接的键值访问：
std::map
提供的
operator[]
语法糖非常便捷。当你确信键存在或希望在键不存在时自动创建并初始化一个默认值时，它能让你的代码简洁高效。例如，统计词频时
```
wordCounts[word]++;
```
这种写法就非常直观。
防止意外的重复键： 如果你的业务逻辑要求键是唯一的，使用
std::map
可以天然地强制这一约束。尝试插入重复键的操作会被忽略（
```
insert
```
），或者覆盖旧值（
operator[]
），这有助于避免数据错误。
内存效率： 在每个键只对应一个值的情况下，
std::map
通常会比
std::multimap
稍微节省一些内存。因为
multimap
的节点设计可能需要考虑处理多个值的情况，或者简单来说，如果你只存一个值，
multimap
也会用一个完整的节点来存，而
map
也是一个节点，但
multimap
会为每个重复的键值对都创建一个节点，而
map
只为唯一的键创建一个节点。当然，这在现代系统中通常不是决定性因素，但值得一提。

简单来说，如果你的数据是“一对一”的关系，并且你重视键的唯一性和

operator[]

的便捷性，那么

std::map

几乎总是你的首选。

k">

k">Magick

无代码AI工具，可以构建世界级的AI应用程序。

99

k"> 查看详情

std::multimap

在实际项目中常见的应用场景有哪些？

std::multimap

的价值在于它能够优雅地处理“一对多”的关系，即同一个键可以关联多个值。在我的项目经验中，有几个场景是

std::multimap

的亮点：

事件日志或时间序列数据： 想象一个系统需要记录在特定时间点发生的所有事件。同一个时间戳（键）可能对应多个不同的日志条目（值）。
```
std::multimap<Timestamp, LogEntry>
```
可以很好地组织这些数据，并且由于其内部排序，你可以按时间顺序轻松遍历所有事件。
多对多关系建模： 在没有数据库的轻量级应用中，或者在需要内存缓存时，
multimap
可以用来表示多对多关系。例如，一个学生可以选修多门课程，一门课程也可以被多个学生选修。你可以用
```
std::multimap<StudentID, CourseID>
```
来存储学生选课信息，或者
```
std::multimap<CourseID, StudentID>
```
来存储课程被哪些学生选修。
索引系统： 构建一个简单的内存搜索引擎时，一个关键词（键）可能出现在多篇文章或文档（值）中。
```
std::multimap<Keyword, DocumentID>
```
就能有效地建立倒排索引，快速查找包含某个关键词的所有文档。
图数据结构： 在表示图的邻接列表时，一个节点（键）可能连接到多个邻居节点（值）。
```
std::multimap<NodeID, NeighborNodeID>
```
可以用来存储图的边信息，并且由于键的有序性，可以方便地按节点ID访问其所有邻居。
自定义排序与分组： 当你需要根据某个属性（键）对一组对象进行分组，并且这些对象可能共享相同的属性值时，
multimap
非常有用。它会自动根据键对所有元素进行排序，让你能轻松地迭代属于同一组的所有元素。
配置管理： 有些配置文件允许同一个配置项（键）被定义多次，每次定义都带有不同的上下文或值，并且这些定义都需要被保留和处理。
std::multimap
可以完美地处理这种需求。

这些场景的核心共同点是：数据的逻辑模型允许或要求键的重复性，并且你需要能够方便地访问与某个键关联的所有值。

从性能角度看，

multimap

与

map

在操作复杂度上有什么异同？

从理论的算法复杂度角度来看，

std::multimap

和

std::map

在核心操作上表现出高度的一致性，因为它们都基于相同的底层数据结构——平衡二叉搜索树（通常是红黑树）。

插入 (Insert) 操作：
- ```
std::map::insert()
```
  :
  O(logN)
  。如果键已存在，插入失败（不修改现有元素）。
- ```
std::map::operator[]
```
  :
  O(logN)
  。如果键不存在则插入，如果键存在则修改。
- ```
std::multimap::insert()
```
  :
  O(logN)
  。总是插入新元素，即使键已存在。从单次插入的角度看，两者的效率是相同的。
查找 (Find) 操作：
- ```
std::map::find(key)
```
  :
  O(logN)
  。返回一个迭代器指向唯一的匹配项。
- ```
std::multimap::find(key)
```
  :
  O(logN)
  。返回一个迭代器指向第一个匹配项。
- ```
std::multimap::equal_range(key)
```
  : 也是
  O(logN)
  来找到范围的边界。但如果你需要遍历所有
  k
  个与键关联的值，那么总时间复杂度是
```
O(logN + k)
```
  。这里的
  k
  是与该键关联的元素数量。
删除 (Erase) 操作：
- ```
std::map::erase(key)
```
  :
  O(logN)
  。删除与键匹配的唯一元素。
- ```
std::multimap::erase(key)
```
  : 删除所有与键匹配的元素。这实际上是先找到第一个匹配项，然后遍历并删除所有匹配项。因此，其复杂度是
```
O(logN + k)
```
  ，其中
  k
  是被删除元素的数量。
- ```
erase(iterator)
```
  : 对于两者，删除指定迭代器指向的元素，平均是
```
O(1)
```
  （摊销），最坏情况
  O(logN)
  （取决于树的重新平衡）。
遍历 (Iteration) 操作：
- 对于两者，从头到尾遍历整个容器都是
```
O(N)
```
  ，其中
```
N
```
  是容器中的元素总数。因为它们都维护了元素的有序性。

异同点总结：

核心复杂度相同： 大多数基本操作的理论时间复杂度都是
O(logN)
，这得益于底层平衡二叉搜索树的效率。
处理重复键的开销：
multimap
在处理重复键时，例如查找或删除一个键的所有关联值，其复杂度会额外包含一个
```
+k
```
的项，其中
k
是与该键关联的元素数量。这意味着如果一个键有非常多的重复值，那么处理这个键的成本会更高。
内存开销：
multimap
由于为每个键值对都创建一个独立的节点，如果存在大量重复键，它的内存开销可能会比
```
map<Key, vector<Value>>
```
这种结构更大。后者为每个键只存储一个
```
vector
```
对象，即使
```
vector
```
中包含很多值，其内部管理方式可能更紧凑。不过，
multimap
的优势在于它自动维护了所有元素的排序，且单个元素的插入/删除通常更高效。
operator[]

的缺失：
multimap
缺乏
operator[]
导致不能进行常量时间或摊销常量时间的“存在即访问，不存在即插入”的便捷操作。这在某些场景下可能会让代码显得稍微冗长，需要使用
```
find
```
或
```
insert
```
结合迭代器来处理。