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

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;

我打算在擦除之前粘贴print语句,但很多答案都讨论了这个问题.所以我按原样离开.

Answer 1

不,std::unordered_set::erase成员函数是从集合中删除元素时唯一要使用的函数,文档说:

复杂性
给定一个unordered_set的实例c:
1)平均情况:常数,最坏情况:c.size()
[...]

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

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

该函数必须找到"下一个元素".std::unordered_set将其数据存储在所谓的存储桶列表中.理想情况下,这是同一个桶列表中的下一个可用插槽,可以容纳您擦除的元素.最坏的情况是,它是其他一些桶中的最后一个可用插槽(因此它随容器的大小而缩放).这取决于容器的插入/擦除历史.你可以看看这里的libcxx实现,有一个循环遍历存储桶列表中的节点(这个机制很好地解释了@ eeroika的答案).

此外,不是那个(也来自文档erase):

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

因此,it在从集合中删除迭代器之后取消引用迭代器是未定义的行为.你可以解决它

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

set_ot_ints.erase(it);

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

Answer 2

不,没有更快的方法来删除集合中的元素erase.除非您的意图是将元素转移到另一个集合中,在这种情况下extract整体上可能更快.

元素的选择无关紧要; 除非你手边没有迭代器,否则最快的迭代器就是begin.

如果你想知道擦除可能具有线性复杂性的情况:如果桶被实现为单链表(如典型的那样),并且所有元素具有相同的键(或者键恰好具有相同的哈希值)并且擦除的元素恰好是存储桶中的最后一个,然后需要遍历整个容器.

常量平均值假定密钥的均匀分布和良好的散列函数.

但是,擦除会使迭代器无效,因此在擦除之后引导它的行为是不确定的.