1.59、map和set的区别和底层实现是什么？

存储结构不同

• • set只存储键（key），即元素本身就是关键字，且元素唯一且有序。
• • map存储键值对（key-value），键唯一且有序，值是与键关联的数据。

元素唯一性和修改权限

• • set中的元素是唯一且不可修改的（迭代器指向的元素是const），因为修改元素会破坏排序规则。
• • map允许修改value，但不允许修改key（key是const），因为key决定元素在红黑树中的位置，修改key相当于删除再插入，破坏结构。

访问方式

• • set不支持通过下标访问，只能通过迭代器遍历或查找。
• • map支持通过key下标访问（operator[]），不存在的key会插入默认值元素。

底层实现细节

红黑树特性

• • 红黑树是一种自平衡的二叉搜索树，节点带有红/黑色标记，保证树的高度为，从而保证操作效率。
• • 其性质包括根节点为黑色，红色节点不能连续出现，任意路径黑色节点数相同等，确保平衡。
• • 插入和删除时通过颜色调整及左旋、右旋操作维持平衡。

为什么用红黑树

• • 保证元素有序，方便范围查询、顺序遍历等操作。
• • 保证插入、删除、查找的时间复杂度均为，避免普通二叉搜索树退化成链表的风险。

与哈希容器区别

• • unordered_map/unordered_set底层用哈希表，查找平均为，但无序，且在哈希冲突严重时退化为链表或红黑树。
• • map/set提供有序数据结构，适合需要排序或范围操作的场景。

总结

本文首发于【讳疾忌医-note】公众号，未经授权，不得转载。
（加入我的知识星球，免费获取账号，解锁所有文章。）