Why would anyone use set instead of unordered_set?

在选择使用 set 而不是 unordered_set 的时候，主要考虑以下几个因素：

1. 元素排序

• set：set 是基于红黑树实现的，它能自动将元素排序。这意味着，当你需要有序的数据时，set 是一个很好的选择。

• unordered_set：unordered_set 基于哈希表实现，它不保证元素的顺序。如果元素的顺序不重要，那么使用 unordered_set 可以提供更快的访问速度。

2. 性能

• 查找、插入、删除操作：
  • set：这些操作通常具有对数时间复杂度（O(log n)），因为它是基于树的结构。
  • unordered_set：这些操作平均具有常数时间复杂度（O(1)），但是在最坏情况下可能退化到线性时间复杂度（O(n)），尤其是在哈希冲突较多时。

应用实例：

假设你正在处理一个人员名单，这个名单需要按照姓氏字母顺序展示，那么使用 set 是非常合适的，因为你插入数据的同时，set 已经帮你完成了排序。而如果你是在做一个频繁检查某个元素是否存在的操作，如在一个大型数据集中快速查找某个用户是否存在，unordered_set 的哈希表结构会提供更快的查找速度。

3. 功能特性

• 迭代器的稳定性：
  • set：set 的迭代器是稳定的，即使添加或删除元素，指向其他元素的迭代器也不会失效。
  • unordered_set：在进行重新哈希时（比如扩容时），迭代器可能会失效。

这种特性决定了在需要维护元素顺序的同时对数据集进行遍历、添加或删除操作时，set 更为适宜。

总结：

选择 set 还是 unordered_set 主要取决于你的具体需求，是否需要元素排序，以及你对操作性能的要求。在需要排序的场景下使用 set，在追求最高性能且元素顺序不重要的场景下使用 unordered_set。这样的选择可以帮助你更高效地实现目标功能，并优化整体性能表现。