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

map和set的区别和底层实现是什么?map取值的 find,[],at方法的区别

目录

一、map 和 set 的区别

1. 基本定义

2. 底层实现

3. 存储内容

4. 常用操作

5. 有序性

二、map 的取值方法:find(),[],和 at()

1. find()

2. operator[]([] 操作符)

3. at()


一、mapset 的区别

1. 基本定义

  • map:一种关联容器,存储的是键值对(key-value pairs),每个键对应唯一的值。键是唯一的,不允许重复。常见的用法是 std::map<Key, Value>.
  • set:一种集合容器,存储的是唯一的键(key),不存储值。元素是唯一的,且不可重复。常见的用法是 std::set<Key>.

2. 底层实现

  • mapset:底层通常使用**红黑树(Red-Black Tree)**实现,红黑树是一种自平衡的二叉查找树,能够保证增删查改操作的时间复杂度为 O(log n)。
    • map 中,红黑树的节点存储键值对,按键排序。
    • set 中,红黑树的节点只存储键,按键排序。
  • unordered_mapunordered_set:底层使用**哈希表(Hash Table)**实现,通过哈希函数将键映射到不同的桶,增删查改操作的平均时间复杂度为 O(1),最坏情况下为 O(n)。

3. 存储内容

  • map:存储键值对,键唯一,值可以重复或不同。
    • 例如:map<int, string> m; m[1] = "one"; m[2] = "two";
  • set:只存储唯一的键,不存储值。
    • 例如:set<int> s; s.insert(1); s.insert(2);

4. 常用操作

  • map:可以通过键来查找值(例如 m[key]),插入或删除键值对。
  • set:可以插入、删除和查找键(例如 s.insert(key)s.find(key))。

5. 有序性

  • mapset:两者都按照键进行排序(使用比较函数,如 <)。
  • unordered_mapunordered_set:无序,元素排列顺序由哈希函数决定。

二、map 的取值方法:find()[],和 at()

map 中,可以使用多种方法来访问存储的值,每种方法的行为略有不同。

1. find()

  • 功能:用于查找指定键是否存在。如果存在,返回指向该元素的迭代器;如果不存在,返回 map.end()
  • 用法
std::map<int, std::string> m = {{1, "one"}, {2, "two"}};
auto it = m.find(1);  // 返回指向键为1的迭代器
if (it != m.end()) {
    std::cout << it->second << std::endl;  // 输出 "one"
}
  • 特点
    • 不会插入新元素,如果键不存在,仅返回 end()
    • 时间复杂度为 O(log n)。

2. operator[][] 操作符)

  • 功能:通过键来访问值。如果键存在,返回对应的值;如果键不存在,会创建一个新的键值对,并初始化值(通常为值类型的默认构造值,如 0、空字符串等)。
  • 用法
std::map<int, std::string> m;
m[1] = "one";  // 插入键1的元素,并赋值为"one"
std::cout << m[2];  // 键2不存在,插入键2,值初始化为空字符串
  • 特点
    • 如果键不存在,会创建新元素并初始化,这种行为可能导致意外的元素插入。
    • 适合用于需要修改或赋值的场景。
    • 时间复杂度为 O(log n)。

3. at()

  • 功能:通过键来访问值。如果键存在,返回对应的值;如果键不存在,抛出 std::out_of_range 异常。
  • 用法
std::map<int, std::string> m = {{1, "one"}};
std::cout << m.at(1);  // 输出 "one"
std::cout << m.at(2);  // 抛出 std::out_of_range 异常

特点

  • 不会插入新元素,仅在键存在时返回值。
  • 适合用于确定键一定存在的场景,否则需要异常处理。
  • 时间复杂度为 O(log n)。


http://www.kler.cn/a/290958.html

相关文章:

  • leetcode之hot100---240搜索二维矩阵II(C++)
  • 多个Echart遍历生成 / 词图云
  • 猫头虎分享:读孙凝晖院士《人工智能与智能计算的发展》有感
  • javaScriptBOM
  • CH340系列芯片驱动电路·CH340系列芯片驱动!!!
  • 电源芯片MPQ2179A(TI)
  • GitLab 是什么?GitLab使用常见问题解答
  • 论文浅尝 | TaxoLLaMA: 用基于WordNet的模型来解决多个词汇语义任务(ACL2024)
  • 微信小程序npm扩展能力探究
  • Linux性能监控神器:深入nmon详解与使用
  • 经验笔记:Maven 与 Gradle —— Java 构建工具对比
  • 每日一练4:牛牛的快递(含链接)
  • @DateTimeFormat和@JsonFormat的区别和使用场景
  • 前端工程化之【模块化规范】
  • 黑马JavaWeb开发笔记15——用JAVA进行Web开发时候的请求、响应流程,B\S架构、C\S架构(概述)
  • log4j漏洞原理以及复现
  • 【JUC】12-CAS
  • Nordic Collegiate Programming ContestNCPC 2021
  • Linux基础 -- 获取CPU负载信息
  • 在react 中还有另外一种three.js 渲染方式
  • 生活因科技而美好:一键解锁PDF处理的无限可能
  • 算法打卡 Day29(回溯算法)-复原 IP 地址 + 子集 + 子集 Ⅱ
  • Gin框架中的全局中间件与中间件传值
  • IDEA 安装lombok插件不兼容的问题及解决方法
  • 【弱监督时间动作定位】Probabilistic Vision-Language Representation for WSTAL 论文阅读
  • Linux shell调试:高效定位错误提高脚本可靠性