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

不,是 std::unordered_set::erase docs 说:

复杂性

1) 平均情况:常数,最坏情况:c.大小()
[...]

c.size() 在最坏的情况下?注意 erase 具有返回值:

返回值
1-2)最后一个删除的元素后面的迭代器。
[...]

std::unordered_set 将其数据存储在所谓的存储桶列表中。理想情况下,这是同一存储桶列表中的下一个可用插槽,该插槽容纳要擦除的元素。最坏的情况是,它是其他桶中最后一个可用的插槽(因此它会随着容器的大小而缩放)。这取决于容器的插入/擦除历史记录。你可以看一看 libcxx 实施 here ,有一个循环遍历存储桶列表中的节点(该机制由 @eeroika's answer ).

除此之外,并非如此(也可从 擦除 ):

对已擦除元素的引用和迭代器无效

所以取消对迭代器的引用 it 将其从集合中删除后,将显示未定义的行为。你可以用电脑来修理它

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

set_ot_ints.erase(it);

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

不,没有比删除集合中的元素更快的方法了 erase . 除非您打算将元素转移到另一个集合中,在这种情况下 extract 整体来说可能会更快。

begin .

如果您想知道擦除可能具有线性复杂性:如果bucket实现为单链表(这是典型的),并且所有元素都具有相同的键(或者这些键恰好具有相同的哈希值),并且擦除的元素恰好是bucket中的最后一个元素,则需要遍历整个容器。

然而,擦除会使迭代器失效,因此在擦除后通过迭代器的行为是未定义的。