c++ - 有没有更快的方法从无序集合中删除和存储元素

Question

我有一个如下所示的无序集:

[1,2,3,4,6,7,5]

我想从我的无序集中删除并存储一个元素，我不关心删除了哪个元素。

我目前正在做以下事情。有更快的方法吗？

auto it = set_of_ints.begin();
set_of_ints.erase(it);
.....
.....
std::cout << "removed element is: " << *it << std::endl;

我打算在删除之前粘贴打印语句，但许多答案都讨论了这个问题。所以我将保持原样。

Answer 1

不，std::unordered_set::erase 成员函数是唯一用于从集合中删除元素的函数，docs 说:

Complexity
Given an instance c of unordered_set:
1) Average case: constant, worst case: c.size()
[...]

那么为什么在最坏的情况下是c.size()呢？请注意，erase 有一个返回值:

Return value
1-2) Iterator following the last removed element.
[...]

函数必须找到“下一个元素”。 std::unordered_set 将其数据存储在所谓的桶列表中。理想情况下，这是与容纳您删除的元素的存储桶列表中的下一个可用插槽。最坏的情况是，它是其他某个桶中的最后一个可用插槽(因此它会随着容器的大小而缩放)。这取决于容器的插入/删除历史记录。你可以看看 libcxx 实现 here ，有一个循环遍历桶列表中的节点(该机制在 @eeroika's answer 中有很好的解释)。

---

此外，不是那样(也来自 erase 上的文档):

References and iterators to the erased elements are invalidated

因此，在将迭代器 it 从集合中删除后对其取消引用是未定义的行为。您可以通过

修复它

auto it = set_of_ints.begin();
const int value = *it;

set_ot_ints.erase(it);

std::cout << "removed element is: " << value << "\n";