如何更快从unordered_set中移除并存储任意元素？

嘿，先给你提个关键的问题：你当前的代码存在未定义行为！当你调用set_of_ints.erase(it)之后，迭代器it就失效了，这时候再去解引用*it是完全不安全的，大概率会导致程序崩溃或者输出错误值——这是你首先要修复的点。

正确的基础实现 #

要安全地移除并存储任意元素（这里你选择的是第一个元素），正确的做法是先把元素值保存下来，再执行erase操作：

#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int> set_of_ints = {1,2,3,4,6,7,5};
    
    if (!set_of_ints.empty()) { // 先判断集合非空，避免空迭代器解引用
        int removed_val = *set_of_ints.begin();
        set_of_ints.erase(set_of_ints.begin());
        std::cout << "removed element is: " << removed_val << std::endl;
    }
    return 0;
}

关于“更快实现”的说明 #

其实你现在的思路已经是最快的方式了：

• unordered_set::begin()是平均O(1)时间复杂度，直接指向哈希表的第一个桶的第一个元素
• unordered_set::erase(iterator)也是平均O(1)时间复杂度，因为哈希表不需要移动其他元素，只需要调整桶的链表指针

没有比这更快的操作了——毕竟你要完成“移除任意元素+存储它”这两个动作，必然需要先获取元素值，再执行移除，这两个步骤都是常数时间，已经达到了理论最优。

如果是C++17及以上版本，你也可以利用erase的返回值（返回下一个有效的迭代器），但这对单个元素的移除场景没有性能提升，只是在遍历移除多个元素时有用，比如：

// 仅作扩展示例，单个元素移除不需要这么写
auto it = set_of_ints.begin();
if (it != set_of_ints.end()) {
    int removed_val = *it;
    it = set_of_ints.erase(it); // 拿到下一个迭代器
    std::cout << "removed element is: " << removed_val << std::endl;
}

总结一下：先保存值再erase是安全且最优的实现，本身已经是最快的，没有更高效的方式了。

内容的提问来源于stack exchange，提问作者Morpheus