map/set vs unordered_map/unordered_set底层对比

map/set(有序关联容器):

• 底层:红黑树(平衡二叉搜索树)。
• 元素自动按键排序,默认std::less。
• 查找/插入/删除:O(log n)。
• 迭代器遍历为有序序列。
• 内存开销:每个节点额外存储颜色、parent/left/right指针(约3个指针+1字节)。
• 支持范围查询(lower_bound/upper_bound)。

unordered_map/unordered_set(无序关联容器):

• 底层:哈希表(桶数组+链表/vector解决冲突)。
• 元素无序,依赖哈希函数。
• 平均O(1),最坏O(n)(大量哈希冲突)。
• 需要提供哈希函数(std::hash)和相等比较(operator==)。
• 内存开销:桶数组(默认较多空桶)+节点存储。
• C++20后增加了contains()方法。

选择建议:需要有序遍历或范围查询用map/set;追求平均性能、无需顺序用unordered_map/set。

自定义哈希:

struct MyHash { size_t operator()(const Key& k) const { return hash<int>()(k.id); } };
unordered_set<Key, MyHash> s;