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

Question

可能重复:
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用std::set？我应该做其他事情,比如几次迭代set::find()后跟set::erase()吗？

Answer 1

std::remove_if(或std::erase)通过重新分配范围成员的值来工作.它不了解如何std::set组织数据,或如何从其内部树数据结构中删除节点.实际上,如果不使用set对象本身,则仅使用对节点的引用是不可能的.

标准算法被设计为具有透明(或至少一致易于记忆)的计算复杂性.set由于需要重新平衡树,因此选择性地从a中删除元素的函数将是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就地安全更新,然后返回其原始值的副本.

Answer 2

错误消息说

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

注意const.编译器是正确的,std::wstring没有operator=可以在const对象上调用的编译器.

为什么字符串是const？答案是a中的值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);
  }
}