为什么我不能使用 std::remove_if 从 std::set 中删除字符串?
可能重复:
remove_if 等效于 std::map
我有一组字符串:
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.0VCincludealgorithm(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() ?
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::remove_if(或 std::erase)通过重新分配成员的值来工作的范围.它不了解 std::set 如何组织数据，或者如何从其内部树数据结构中删除节点.实际上，如果没有 set 对象本身，只使用对节点的引用是不可能的.
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.
标准算法旨在具有透明(或至少始终易于记忆)的计算复杂性.由于需要重新平衡树，因此从 set 中选择性地删除元素的函数将是 O(N log N)，这并不比调用 my_set.remove() 的循环更好 .所以，标准没有提供，这就是你需要写的.
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.
另一方面，从 vector 中逐个删除项目的天真手工编码循环将是 O(N^2)，而 std::remove_if 是 O(N).因此，在这种情况下，图书馆确实提供了切实的好处.
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.
一个典型的循环(C++03风格):
A typical loop (C++03 style):
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 并且 then 返回其原始值的副本.
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.
相关文章