欢迎光临
我们一直在努力
        找回密码
当前位置：171主机测评 > 服务器技术 > 正文

STL中map与multimap深度解析

2026-03-16 分类：服务器技术 阅读(34) 评论(0)

好的，我们来深入剖析STL中的 map 和 multimap 容器，重点解析它们的接口使用和核心特性。

1. 基本概念与核心差异

  • map (映射):
    • 关联容器，存储键值对 (key, value)。
    • 核心特性: key 必须唯一。 即容器中任意两个元素的 key 不能相同。
    • 内部元素根据 key 自动排序（默认升序，可通过比较函数自定义）。
  • multimap (多重映射):
    • 同样是关联容器，存储键值对 (key, value)。
    • 核心特性: 允许 key 重复。 即容器中可以存在多个具有相同 key 的元素。
    • 内部元素同样根据 key 自动排序。

核心差异总结:

  • key 的唯一性: map 要求唯一，multimap 允许重复。
  • 应用场景:
    • map: 需要建立严格一对一映射关系的场景（如字典、电话簿、唯一ID映射）。
    • multimap: 需要建立一对多映射关系的场景（如一个作者对应多本书、一个班级对应多个学生）。

2. 底层数据结构：红黑树

map 和 multimap 在标准库实现中通常基于红黑树（Red-Black Tree）。

  • 红黑树特性:
    • 自平衡的二叉搜索树。
    • 插入、删除、查找操作的时间复杂度为 $O(\\log n)$。
    • 保证了元素的有序性（根据 key 排序）。
  • 影响:
    • 高效的有序查找：find(), lower_bound(), upper_bound() 等操作高效。
    • 插入和删除操作会调整树结构以保持平衡。
    • 迭代器遍历时，元素按 key 的排序顺序输出（中序遍历）。

3. 关键接口详解

3.1 插入元素
  • map 插入 (insert):
    • std::pair<iterator, bool> insert(const value_type& value);
    • 尝试插入一个键值对 (key, value)。
    • 返回值是一个 pair:
      • pair.first: 指向被插入元素的迭代器（或指向阻止插入的元素的迭代器）。
      • pair.second: bool 值，表示插入是否成功。
        • true: 插入成功（key 原本不存在）。
        • false: 插入失败（key 已存在，已有元素未被替换）。
    • 重要特性: 如果 key 已存在，插入操作不会覆盖原有的 value。
  • map 下标访问 (operator[]):
    • T& operator[](const Key& key);
    • T& operator[](Key&& key); (C++11)
    • 行为:
      • 如果 key 存在，返回其对应 value 的引用。
      • 如果 key 不存在，则插入一个新的键值对 (key, T())（值初始化），并返回新 value 的引用。
    • 注意: 这可能导致意外的元素插入。如果只想查询而不想插入，应使用 find()。
  • map 插入或赋值 (insert_or_assign) (C++17):
    • std::pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
    • 如果 key k 不存在，则插入 (k, std::forward<M>(obj))。
    • 如果 key k 已存在，则将已有元素的 value 赋值为 std::forward<M>(obj)。
    • 返回值 pair 中：
      • iterator: 指向插入或修改元素的迭代器。
      • bool: true 表示插入了新元素，false 表示赋值了已有元素。
  • map/multimap 使用 emplace (C++11):
    • template <class… Args> std::pair<iterator, bool> emplace(Args&&… args); (map)
    • template <class… Args> iterator emplace(Args&&… args); (multimap)
    • 在容器中直接构造元素（键值对），避免临时对象的构造和拷贝/移动。
    • 对于 map，返回值 pair 的含义与 insert 相同。
    • 对于 multimap，总是返回指向新插入元素的迭代器（因为 key 可重复，总能插入）。
  • multimap 插入 (insert):
    • iterator insert(const value_type& value);
    • 插入一个键值对 (key, value)。
    • 总是成功（允许 key 重复）。
    • 返回指向新插入元素的迭代器。
3.2 查找元素
  • find (查找特定 key):
    • iterator find(const Key& key);
    • const_iterator find(const Key& key) const;
    • 查找具有特定 key 的元素。
    • 返回指向找到的元素的迭代器。如果未找到，返回 end()。
    • map: 最多找到一个元素（key 唯一）。
    • multimap: 返回找到的第一个具有该 key 的元素（需配合 equal_range 或循环查找所有）。
  • count (统计特定 key 的数量):
    • size_type count(const Key& key) const;
    • 返回具有特定 key 的元素数量。
    • map: 结果只能是 0 或 1。
    • multimap: 结果可以是 0, 1, 或大于 1。
  • equal_range (查找特定 key 的范围):
    • std::pair<iterator, iterator> equal_range(const Key& key);
    • std::pair<const_iterator, const_iterator> equal_range(const Key& key) const;
    • 返回一个 pair，包含两个迭代器：
      • first: 指向第一个 key 不小于 key 的元素（即等于 key 或逻辑上第一个大于 key 的元素）。
      • second: 指向第一个 key 大于 key 的元素。
    • 对于特定 key k，[lower_bound(k), upper_bound(k)) 这个区间包含所有 key == k 的元素。
    • map: 返回的范围最多包含一个元素（first 可能等于 second）。
    • multimap: 返回的范围包含所有 key == k 的元素。
  • lower_bound / upper_bound (查找边界):
    • iterator lower_bound(const Key& key);
    • iterator upper_bound(const Key& key);
    • 含义与 equal_range 返回的 pair 中的 first 和 second 相同。
    • 常用于在有序序列中查找一个区间。
3.3 删除元素
  • erase (删除元素):
    • iterator erase(iterator pos); (C++11 前返回 void)
    • iterator erase(const_iterator pos); (C++11)
    • size_type erase(const Key& key);
    • iterator erase(const_iterator first, const_iterator last);
    • 删除单个元素（通过迭代器）、删除所有具有特定 key 的元素、删除一个迭代器范围 [first, last)。
    • 删除后返回的迭代器指向被删除元素的下一个元素（或 end()）。
    • 删除所有具有特定 key 的元素，返回被删除的元素个数。
    • map: erase(const Key& key) 返回值是 0 或 1。
    • multimap: erase(const Key& key) 返回值可能大于 1。
    • 注意: 删除元素会使指向该元素的迭代器、引用、指针失效。指向其他元素的通常保持有效。
3.4 其他重要接口
  • empty / size: 检查是否为空、获取元素数量。
  • clear: 清空容器。
  • 迭代器 (begin, end, cbegin, cend, rbegin, rend, crbegin, crend): 用于遍历容器。遍历时元素按键排序顺序输出。
  • key_comp / value_comp: 获取用于比较 key 或 value（实际比较的是 key）的函数对象副本。

4. 性能特点

  • 查找 (find, count, operator[]): $O(\\log n)$ (基于红黑树)
  • 插入 (insert, emplace): $O(\\log n)$ (查找插入位置 + 可能的树平衡调整)
  • 删除 (erase): $O(\\log n)$ (查找元素 + 可能的树平衡调整)
  • 空间复杂度: $O(n)$

5. 使用示例

#include <iostream>
#include <map>
#include <string>

int main() {
// map 示例 (唯一键)
std::map<int, std::string> studentMap;

// 插入 – 使用 insert
auto [it1, success1] = studentMap.insert({101, "Alice"});
if (success1) std::cout << "Inserted Alice\\n";

auto [it2, success2] = studentMap.insert({101, "Bob"}); // key 101 已存在，插入失败
if (!success2) std::cout << "Failed to insert Bob for key 101\\n";

// 插入 – 使用 operator[]
studentMap[102] = "Charlie"; // 插入新元素 (102, "Charlie")
std::cout << "Student 102: " << studentMap[102] << '\\n';

studentMap[101] = "Alan"; // key 101 存在，修改 value 为 "Alan"
std::cout << "Student 101 now: " << studentMap[101] << '\\n';

// 插入 – 使用 emplace
studentMap.emplace(103, "Diana");

// 查找
auto it_find = studentMap.find(102);
if (it_find != studentMap.end()) {
std::cout << "Found 102: " << it_find->second << '\\n';
}

// 遍历 (按键排序: 101, 102, 103)
for (const auto& [id, name] : studentMap) {
std::cout << id << ": " << name << '\\n';
}

// multimap 示例 (允许重复键)
std::multimap<std::string, std::string> authorBooks;

authorBooks.insert({"J.K. Rowling", "Harry Potter 1"});
authorBooks.insert({"J.K. Rowling", "Harry Potter 2"});
authorBooks.insert({"George Orwell", "1984"});
authorBooks.insert({"George Orwell", "Animal Farm"});

// 查找一个作者的所有书 – 使用 equal_range
auto range = authorBooks.equal_range("J.K. Rowling");
std::cout << "\\nBooks by J.K. Rowling:\\n";
for (auto it = range.first; it != range.second; ++it) {
std::cout << " – " << it->second << '\\n';
}

return 0;
}

https://weibo.com/tv/show/1034:5276907978293255
https://weibo.com/tv/show/1034:5276907961516059
https://weibo.com/tv/show/1034:5276907948933124
https://weibo.com/tv/show/1034:5276907936088108
https://weibo.com/tv/show/1034:5276907910922284
https://weibo.com/tv/show/1034:5276907906990117
https://weibo.com/tv/show/1034:5276907881824266
https://weibo.com/tv/show/1034:5276907881824272
https://weibo.com/tv/show/1034:5276907839881270
https://weibo.com/tv/show/1034:5276907839619097

6. 总结

  • map 提供唯一的键到值的映射，操作高效 ($O(\\log n)$)，元素有序存储。
  • multimap 允许键重复，适用于一对多的映射关系，接口与 map 类似但插入和删除行为有差异（允许多个相同 key）。
  • 两者均基于红黑树实现，保证了操作的效率和元素的有序性。
  • 理解 insert, operator[], emplace 的行为差异以及 find, count, equal_range 的用法至关重要。
  • 在需要键唯一时用 map，在需要键可重复时用 multimap。
  • https://weibo.com/tv/show/1034:5276907978293255
    https://weibo.com/tv/show/1034:5276907961516059
    https://weibo.com/tv/show/1034:5276907948933124
    https://weibo.com/tv/show/1034:5276907936088108
    https://weibo.com/tv/show/1034:5276907910922284
    https://weibo.com/tv/show/1034:5276907906990117
    https://weibo.com/tv/show/1034:5276907881824266
    https://weibo.com/tv/show/1034:5276907881824272
    https://weibo.com/tv/show/1034:5276907839881270
    https://weibo.com/tv/show/1034:5276907839619097
赞(0)
未经允许不得转载：171主机测评 » STL中map与multimap深度解析
分享到： 更多 (0)
标签：

相关推荐

评论 抢沙发

取消

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

热门标签

#人工智能(58911)#python(20004)#开发语言(16788)#java(15405)#运维(15301)#linux(14908)#大数据(14519)#服务器(13022)#算法(11735)#前端(10836)#网络(9332)#数据库(8849)#ai(8830)#c++(8140)#课程设计(6793)#学习(6733)#机器学习(6690)#区块链(5901)#OpenClaw(5387)#后端(5119)#spring boot(4989)#深度学习(4923)#c语言(4365)#毕业设计(4291)#数据结构(4187)#安全(4021)#docker(3917)#架构(3839)#javascript(3794)#大模型(3633)

热门文章

最新文章

归档

分类