为什么我不能使用std::remove_if从std::set中删除字符串？

Question

可能是重复问题：
remove_if等效于std::map吗？

我有一组字符串：

set <wstring> strings;
// ...

我希望能够根据谓词（predicate）删除字符串，例如：

std::remove_if ( strings.begin(), strings.end(), []( const wstring &s ) -> bool { return s == L"matching"; });

尝试此操作时，我收到以下编译器错误：

c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\algorithm(1840): error C2678: binary '=' : no operator found which takes a left-hand operand of type 'const std::basic_string<_Elem,_Traits,_Ax>' 

这个错误似乎表明std::string没有按值复制构造函数（这是不合法的）。

使用std::remove_if和std::set是否有问题？我应该做些其他事情，比如多次迭代set::find()然后再调用set::erase()吗？

- Benj

---

你的简单示例可以被 strings.erase(L"matching"); 替换。人们会认为你实际的谓词不是那么琐碎。 - Robᵩ

@Robᵩ 是的，那只是一个例子，我确实需要一个函数对象。 - Benj

Answer 1

std::remove_if（或者std::erase）通过重新分配范围成员的值来工作。它不理解std::set如何组织数据，也不知道如何从内部树形数据结构中删除节点。事实上，仅使用对节点的引用而没有set对象本身是不可能做到这一点的。

标准算法旨在具有透明（或至少是易于记忆）的计算复杂度。从set中选择性删除元素的函数将是O（N log N），因为需要重新平衡树，这与调用my_set.remove()的循环没有任何区别。所以，标准库并没有提供它，这就是你需要编写的内容。

另一方面，一个朴素手写的循环一个接一个地从vector中移除项目将是O(N^2)，而std::remove_if是O(N)。因此，在这种情况下，库确实提供了实际的好处。

一个典型的循环（C++03风格）：

for ( set_t::iterator i = my_set.begin(); i != my_set.end(); ) {
    if ( condition ) {
        my_set.erase( i ++ ); // strict C++03
        // i = my_set.erase( i ); // more modern, typically accepted as C++03
    } else {
        ++ i; // do not include ++ i inside for ( )
    }
}

编辑（4年后！）：i ++ 看起来有点可疑。如果 erase 在后缀自增运算符更新之前使 i 无效，会怎样？尽管如此，这是可以的，因为它是一个重载的 operator++ 而不是内置运算符。该函数安全地原地更新 i ，然后返回其原始值的副本。

- Potatoswatter

---

@Rook 有这样的概念，但它并不是一个解决方法。问题在于 std::remove_if 被指定为 O(N)，而不是 O(N) 的实现不能按照法律的规定称为 std::remove_if。您可以在自己的命名空间中提供自己的实现。然而，这个重载会与 std 中的重载冲突。最好还是写一个循环。 - Potatoswatter

@Rook：在这种情况下，问题不在于迭代器，而是容器的value_type。std::remove_if通过解引用迭代器来修改值，但是std::set中的value_type是一个常量对象。 - David Rodríguez - dribeas

remove_if 应该被称为 shuffle_to_the_front_unless：这样就很容易看出它不可能用于集合，并且它不会对任何使用它的容器进行结构性更改。正如您所说，迭代器从来不会这样做。 - Steve Jessop

啊，我粗心地假设了迭代器返回一个常量引用。回过头来看，值类型是常量的确很明显。 - Rook

你也可以像这个例子一样使用i = my_set.erase(i);。 - Timmmm

Answer 2

错误信息提示：

没有找到左操作数为类型 'const std::basic_string<_Elem,_Traits,_Ax>' 的运算符

注意 const。编译器正确指出了 std::wstring 没有一个能在常量对象上调用的 operator=。

为什么字符串是 const？答案是因为 std::set 中的值是不可变的，因为集合中的值是有序的，改变一个值可能会改变它在集合中的排序，从而使集合无效。

为什么编译器试图复制集合中的值？

std::remove_if（以及 std::remove）实际上不会删除任何元素（也不能，因为它们没有容器，只有迭代器）。它们所做的是将范围内与条件不匹配的所有值复制到范围的开头，并返回指向匹配元素之后的下一个元素的迭代器。然后，您应该手动从返回的迭代器到范围的末尾进行擦除。由于集合保持其元素有序，因此移动任何元素都是错误的，所以不能在集合（或任何其他关联容器）上使用 remove_if。

简而言之，您必须使用 std::find_if 循环和 set::erase，如下所示：

template<class V, class P>
void erase_if(std::set<V>& s, P p)
{
  std::set<V>::iterator e = s.begin();
  for (;;)
  {
    e = std::find_if(e, s.end(), p);
    if (e == s.end())
      break;
    e = s.erase(e);
  }
}

- ymett

---

实际上，一个库可以通过使用特殊的知识，即根节点实际上位于容器对象内部，来提供与std::set兼容的std :: remove_if。但是，它将无法满足O(N)运行时要求。 - Potatoswatter

哎呀，是 end() 节点，而不是根节点，但你懂我的意思。 - Potatoswatter

+1，你很好地解释了推理，并提供了一个不错的替代方案，但我可能会将该函数命名为erase_if。 - Benjamin Lindley

@Benjamin Lindley 好的，你说得对，已经修改了。 - ymett

@Potatoswatter 这也是不一致的 - 它的行为会与其他容器上的 remove_if 非常不同。 - ymett

@ymett 不会，唯一的区别就是运行时复杂度。remove_if 是一个稳定的算法，因此元素不会被重新排序。它也不会给序列元素赋值，而是改变序列本身，但这个方面在标准中根本没有明确规定。 - Potatoswatter