11

可能重复：
remove_if 等效于 std::map

我有一组字符串：

set <wstring> strings;
// ...

我希望根据谓词删除字符串，例如：

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使用with 有什么不好的地方std::set吗？我应该做其他事情，例如几次迭代，set::find()然后是set::erase()？

4

2 回答 2

21

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

标准算法旨在具有透明（或至少始终易于记忆）的计算复杂性。由于需要重新平衡树，因此有选择地从 a 中删除元素的函数set将是 O(N log N)，这并不比循环调用更好my_set.remove()。所以，标准没有提供它，这就是你需要写的。

另一方面，一个简单的手动编码循环来逐个删除项目vector将是 O(N^2)，而std::remove_ifO(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就地更新，然后返回其原始值的副本。

于 2012-06-21T15:37:34.397 回答
10

错误消息说

未找到采用“ const std::basic_string<_Elem,_Traits,_Ax>”类型的左操作数的运算符

注意常量。编译器是正确的，std::wstring它没有operator=可以在 const 对象上调用的。

为什么字符串是常量？答案是 a 中的值std::set是不可变的，因为 set 中的值是有序的，并且更改值可能会更改其在 set 中的顺序，从而使 set 无效。

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

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

简而言之，您必须使用 and 的循环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);
  }
}
于 2012-06-21T16:02:08.733 回答