C++中的std::set::erase与std::remove_if的用法

Question

这段代码出现了 Visual Studio 的 error C3892 错误。如果我将 std::set 更改为 std::vector，它就能正常工作。

std::set<int> a;
a.erase(std::remove_if(a.begin(), a.end(), [](int item)
{
    return item == 10;
}), a.end());

怎么回事？为什么我不能在std::set中使用std::remove_if？

- herolover

---

可能是Erase-remove idiom with std::set failing with constness-related error的重复问题。 - legends2k

Answer 1

您不能使用std::remove_if()处理具有const部分的序列。 std::set<T>元素的顺序由T const对象组成。实际上，昨天我们在标准C++委员会中讨论了这个问题，并且支持创建专门处理从容器中erase()对象的算法。它看起来像这样（也请参见N4009）：

template <class T, class Comp, class Alloc, class Predicate>
void discard_if(std::set<T, Comp, Alloc>& c, Predicate pred) {
    for (auto it{c.begin()}, end{c.end()}; it != end; ) {
        if (pred(*it)) {
            it = c.erase(it);
        }
        else {
            ++it;
        }
    }
}

它可能实际上会委托给一个算法，将逻辑分派到上面的逻辑中，因为相同的逻辑对于其他基于节点的容器也是相同的。

对于您特定的用途，您可以使用

a.erase(10);

但是，这仅适用于您想要删除键时，而上述算法适用于任意谓词。另一方面，a.erase(10) 可以利用 std::set<int> 的结构，并且时间复杂度为 O(log N)，而算法的时间复杂度为 O(N)（其中 N == s.size()）。

- Dietmar Kühl

Answer 2

从C++20开始，您可以针对具有 erase() 方法的容器使用std::erase_if，就像Kühl解释的那样。

// C++20 example:
std::erase_if(setUserSelection, [](auto& pObject) {
                                     return !pObject->isSelectable();
                                });

请注意，这也包括std::vector，因为它有一个erase方法。不再需要链式调用a.erase(std::remove_if(... :)

- Ben

---

这应该是最新的答案！ - Anonymous

Answer 3

std::remove_if 会重新排列元素，因此不能与 std::set 一起使用。但是你可以使用 std::set::erase：

std::set<int> a;
a.erase(10);

- juanchopanza

---

好的，谢谢。但是，这是个问题吗？让它重新排序。因为复杂性的原因？ - herolover

@herolover std::set 是有序的，而且它的排序是为了实现对数级别的查找（它是一棵二叉搜索树）。因此它与复杂度有关。 - juanchopanza

@herolover std::set 的元素顺序是由比较函数预先确定的，您无法更改顺序，否则容器将无法正常工作。 - Erbureth