std::set 用红黑树而非哈希表，因其需保证有序性以支持升序迭代和O(log n)范围查询；红黑树在查、插、删间折中优于AVL树和B+树，且缓存友好；实际性能关键在于key类型与比较逻辑。
std::set 为什么不用哈希表实现
因为 std::set 的核心契约是「有序」——插入、遍历、lower_bound 等操作都依赖元素严格升序。哈希表（如 std::unordered_set）不维护顺序，无法支持 begin() 到 end() 的升序迭代，也不能在 O(log n) 内完成范围查询（比如所有 [a, b) 区间的元素）。
红黑树相比普通二叉搜索树的优势
普通 BST 在极端插入序列（如已排序数组）下会退化成链表，查找变成 O(n)。红黑树通过着色规则和旋转维持近似平衡：最长路径 ≤ 2 × 最短路径，从而保证最坏情况下的查找、插入、删除均为 O(log n)，且能稳定支持顺序遍历。
- 插入后最多执行 2 次旋转 + 若干颜色翻转，开销可控
- 每个节点只需 1 bit 存储颜色，空间代价极小
- 中序遍历天然有序，直接支撑
std::set::iterator的递增语义
为什么不选 AVL 树或 B+ 树
AVL 树更严格平衡（高度差 ≤ 1），查找略快，但插入/删除时平均旋转次数更多，对写多读少的场景不利；C++ 标准不要求具体实现，但主流实现（libstdc++、libc++）选红黑树，是因它在查、插、删三者间做了更实用的折中。
- B+ 树适合磁盘 I/O 场景（如数据库索引），内存中节点分支太多反而降低缓存局部性
- 红黑树单个节点小（通常仅含左右指针 + 父指针 + color），CPU cache 友好
-
std::set不需要批量范围查找优化，B+ 树优势无从发挥
实际编码中容易忽略的性能点
红黑树的 O(log n) 是基于「比较次数」，不是「内存访问次数」。若 operator< 很重（比如比较长字符串或自定义结构体深层字段），实际耗时可能远超预期。
立即学习“C++免费学习笔记（深入）”；
- 避免在
operator<中做分配、IO 或复杂计算 - 考虑用
std::string_view替代std::string作 key，减少拷贝与比较开销 -
std::set::find()和std::set::count()都是 O(log n)，但前者返回迭代器，后者只返回 0/1，别为判存在而用count()
auto it = my_set.find(key);
if (it != my_set.end()) {
// 使用 *it
}
真正影响性能的往往不是树结构本身，而是你塞进去的 key 类型和比较逻辑。
