为什么我不能从std::设置为std::remove_if?(复制)

Possible Duplicate:
remove_if equivalent for std::map

可能的副本:remove_if等价于std::map

I have a set of strings:

我有一组字符串:

set <wstring> strings;
// ...

I wish to remove strings according to a predicate, e.g.:

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

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

When I attempt this, I get the following compiler error:

当我尝试此操作时，会得到以下编译错误:

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>'

The error appears to suggest that std::string doesn't have a by-value copy constructor ( which would be illegal). Is it somehow bad to use std::remove_if with std::set ? Should I be doing something else instead such as several iterations of set::find() followed by set::erase() ?

这个错误似乎表明std::string没有按值复制构造函数(这是非法的)。使用std::remove_if和std::set有什么不好吗?我是否应该做一些其他的事情，比如几次迭代set::find()，然后是set:::erase() ?

2 个解决方案

#1

std::remove_if (or std::erase) works by reassigning the values of the members of the range. It doesn't understand how std::set organizes data, or how to remove a node from its internal tree data structure. Indeed, it's impossible to do so using only references to nodes, without having the set object itself.

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

The standard algorithms are designed to have transparent (or at least consistently easy-to-remember) computational complexities. A function to selectively remove elements from a set would be O(N log N), due to the need to rebalance the tree, which is no better than a loop calling my_set.remove() . So, the standard doesn't provide it, and that is what you need to write.

标准的算法被设计成具有透明(或者至少是一致容易记住的)计算复杂性。有选择地从集合中删除元素的函数是O(N log N)，因为需要重新平衡树，这不比调用my_set.remove()的循环更好。标准没有提供，这就是你需要写的。

On the other hand, a naively hand-coded loop to remove items from a vector one-by-one would be O(N^2), whereas std::remove_if is O(N). So the library does provide a tangible benefit in that case.

另一方面,一个天真地一个一个手工编写循环把物品从一个向量是O(N ^ 2),而std::remove_if是O(N)。在这种情况下，图书馆确实提供了实实在在的好处。

A typical loop (C++03 style):

典型的循环(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 ( )
    }
}

Edit (4 years later!): i ++ looks suspicious there. What if erase invalidates i before the post-increment operator can update it? This is fine, though, because it's an overloaded operator++ rather than the built-in operator. The function safely updates i in-place and then returns a copy of its original value.

编辑(4年后!):i +在那里看起来可疑。如果在后增量操作符可以更新之前擦除无效i，该怎么办?不过，这没问题，因为它是一个重载操作符++，而不是内置操作符。函数安全地更新i，然后返回原始值的副本。

#2

The error message says

错误消息说

no operator found which takes a left-hand operand of type 'const std::basic_string<_Elem,_Traits,_Ax>'

没有找到使用'const std::basic_string<_Elem，_Traits，_Ax>'的左手操作数的运算符

Note the const. The compiler is correct that std::wstring doesn't have an operator= which can be called on a const object.

注意const。编译器是正确的，std::wstring没有可以在const对象上调用的运算符=。

Why is the string const? The answer is that the values in a std::set are immutable, because values in a set are ordered, and changing a value could change its ordering in the set, invalidating the set.

为什么弦是弦?答案是std::set中的值是不可变的，因为集合中的值是有序的，而改变一个值可以改变它在集合中的顺序，使集合无效。

Why is the compiler trying to copy a value of the set?

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

std::remove_if (and std::remove) don't actually erase anything (nor can they, because they don't have the container, only iterators). What they do is to copy all values in the range which don't match the criterion to the beginning of the range, and return an iterator to the next element after the matching elements. You are then supposed to manually erase from the returned iterator to the end of the range. Since a set keeps its elements in order, it would be wrong to move any elements around, so remove_if cannot be used on a set (or any other associative container).

remove_if(和std::remove)不会删除任何内容(它们也不能删除任何内容，因为它们没有容器，只有迭代器)。它们所做的是复制范围内的所有值，这些值与范围的起始值不匹配，并在匹配元素之后返回一个迭代器到下一个元素。然后，应该从返回的迭代器中手动删除到范围的末尾。由于集合保持其元素的顺序，所以移动任何元素都是错误的，因此remove_if不能用于集合(或任何其他关联容器)。

In short, you do have to use a loop of std::find_if and set::erase, like so:

简而言之，您必须使用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);
  }
}

#1