当前位置: 首页 > backend >正文

unordered_map与map之间的区别和联系

unordered_map 与 map 的区别和联系

一、两者的联系
  • 都属于 C++ 标准库容器:二者均用于存储键值对(key-value pairs),允许通过键快速查找对应的值。
  • 基本功能相似:都支持插入(insert)、删除(erase)、查找(find)、修改值等操作,且键具有唯一性(不能重复)。
二、核心区别
1. 数据结构与实现原理
特性mapunordered_map
底层数据结构红黑树(平衡二叉搜索树)哈希表(哈希桶数组 + 链表 / 红黑树)
元素排序按键的有序性自动排序(默认升序)元素无序,按键的哈希值存储
2. 时间复杂度
操作mapunordered_map
查找(find)O(log n)平均 O (1),最坏 O (n)(哈希冲突严重时)
插入(insert)O(log n)平均 O (1),最坏 O (n)
删除(erase)O(log n)平均 O (1),最坏 O (n)
3. 内存占用与性能
  • map:红黑树需要额外存储节点指针和平衡因子,内存占用较高,但查找时间稳定。
  • unordered_map:哈希表需要存储哈希函数和桶数组,若哈希冲突频繁(如链表过长),性能可能下降,但平均效率更高。
4. 有序性与遍历顺序
  • map:遍历顺序与键的排序顺序一致(按红黑树中序遍历)。
  • unordered_map:遍历顺序由哈希值和桶的位置决定,与插入顺序无关,每次遍历顺序可能不同。
5. 键的要求
  • map:键需要支持比较运算符(默认用 < 排序),或用户自定义比较函数。
  • unordered_map:键需要支持哈希函数(需提供 hash<Key> 模板特化)和相等运算符(==)。
三、使用场景示例
示例 1:需要有序性的场景
#include <iostream>
#include <map>
using namespace std;int main() {// 统计单词出现次数并按字母顺序输出map<string, int> wordCount;string words[] = {"apple", "banana", "apple", "cherry", "banana", "date"};for (const string& word : words) {wordCount[word]++;  // 插入或更新计数}// 遍历map会按单词字母顺序输出cout << "按字母顺序统计单词出现次数:" << endl;for (const auto& pair : wordCount) {cout << pair.first << ": " << pair.second << endl;}return 0;
}

输出结果

按字母顺序统计单词出现次数:
apple: 2
banana: 2
cherry: 1
date: 1
示例 2:追求高效查找的场景
#include <iostream>
#include <unordered_map>
using namespace std;int main() {// 学生ID与姓名的快速映射(ID无顺序需求)unordered_map<int, string> studentMap;// 插入数据(假设ID是随机的)studentMap.insert({1003, "张三"});studentMap.insert({1001, "李四"});studentMap.insert({1002, "王五"});studentMap.insert({1005, "赵六"});// 快速查找int searchId = 1002;auto it = studentMap.find(searchId);if (it != studentMap.end()) {cout << "ID " << searchId << " 的学生姓名是:" << it->second << endl;} else {cout << "未找到ID为 " << searchId << " 的学生" << endl;}// 遍历unordered_map(顺序不确定)cout << "所有学生信息(顺序不固定):" << endl;for (const auto& pair : studentMap) {cout << "ID: " << pair.first << ", 姓名: " << pair.second << endl;}return 0;
}

可能的输出结果(每次运行顺序可能不同):

ID 1002 的学生姓名是:王五
所有学生信息(顺序不固定):
ID: 1003, 姓名: 张三
ID: 1001, 姓名: 李四
ID: 1002, 姓名: 王五
ID: 1005, 姓名: 赵六
四、选择建议
  • 优先使用 unordered_map:当需要快速查找(平均 O (1) 效率),且键的顺序无关紧要时(如缓存、哈希表场景)。
  • 使用 map
    • 当需要键的有序性(如按字母顺序排序、按数值大小排序)。
    • 当对最坏情况下的查找时间有严格要求(unordered_map 可能因哈希冲突出现 O (n) 情况)。
    • 当需要范围查找(如查找大于某个键的所有元素,map 支持迭代器范围操作)。
http://www.xdnf.cn/news/9891.html

相关文章:

  • SpringBoot 日志
  • ROS云课基础篇-02-C++-250529
  • 财管2 - 财务预测(内含增长率,可持续增长率)
  • [9-2] USART串口外设 江协科技学习笔记(9个知识点)
  • 20250529-C#知识:继承、密封类、密封方法、重写
  • Oracle 条件判断
  • <线段树>
  • 影楼精修-AI追色算法解析
  • FEMFAT许可的有效期限
  • 从融智学视角对决策态度进行定理级提炼,结合三标准数学建模
  • vue3: tmap (腾讯地图)using typescript
  • sudo apt-get update错误解决
  • Spring Boot+Activiti7入坑指南初阶版
  • 表单请求为什么需要进行 URL 编码?—详解application/x-www-form-urlencoded的正确用法
  • 从零开始的数据结构教程(五)​​动态规划(DP)
  • 数据结构 --- 顺序表
  • 安卓学习笔记-数据存储
  • [嵌入式实验]实验二:LED控制
  • Dynamics 365 Business Central AI Sales Order Agent Copilot
  • Redis 延迟队列
  • 【东枫科技】KrakenSDR 天线阵列设置
  • 1.测试过程之需求分析和测试计划
  • 【LeetCode 热题 100】最小路径和 / 最长回文子串 / 最长公共子序列 / 编辑距离
  • Ubuntu 中安装 PostgreSQL 及常规操作指南
  • JAVA与C语言之间的差异(二)
  • 1614. 括号的最大嵌套深度【 力扣(LeetCode) 】
  • 摩尔信使MThings无法生成机器码的解决方法
  • 腾讯云国际站性能调优
  • 【静电模拟】使用打火机的电子部分模拟手指静电
  • 机器学习-线性回归基础