代码之家  ›  专栏  ›  技术社区  ›  Morpheus

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

  •  4
  • Morpheus  · 技术社区  · 6 年前

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

    [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;
    

    2 回复  |  直到 6 年前
        1
  •  6
  •   lubgr    6 年前

    不,是 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";
    
        2
  •  5
  •   eerorika    6 年前

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

    begin .


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


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