为什么不能使用std :: remove_if从std :: set中删除字符串？ [英] Why can't I remove a string from a std::set with std::remove_if?

问题描述

可能重复：

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.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 :: set 中使用 std :: remove_if 是否有点不好？我是否应该做其他事情，例如 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 如何组织数据，或者如何从内部树数据结构中删除节点。实际上，如果没有设置对象本身，仅使用对节点的引用是不可能的。

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.

标准算法被设计为具有透明（或至少始终易于记忆）的计算复杂性。从集中中有选择地删除元素的函数将是O（N log N），因为需要重新平衡树，这比调用<$的循环更好c $ c> 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 ++ 似乎很可疑。如果擦除使 i 无效，然后在后递增运算符可以更新它之前该怎么办？不过，这很好，因为它是重载的 operator ++ 而不是内置的运算符。该函数安全地就地更新 i ，然后然后返回其原始值的副本。

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.

这篇关于为什么不能使用std :: remove_if从std :: set中删除字符串？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！