¿Por qué no puedo eliminar una cadena de un std :: set con std :: remove_if?

Question

Possible Duplicate:
remove_if equivalent for std::map

que tienen un conjunto de cadenas:

set <wstring> strings; 
// ... 

deseo de eliminar las cadenas de acuerdo con el predicado, por ejemplo:

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

Cuando intento esto, me sale el siguiente compilador 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>' 

El e rror parece sugerir que std::string no tiene un constructor de copia por valor (que sería ilegal). ¿Es de alguna manera malo usar std::remove_if con std::set? ¿Debo hacer otra cosa en su lugar, como varias iteraciones de set::find() seguido de set::erase()?

Answer 1

std::remove_if (o std::erase) funciona reasignando los valores de los miembros del rango. No comprende cómo std::set organiza datos, o cómo eliminar un nodo de su estructura interna de datos de árbol. De hecho, es imposible hacerlo utilizando solo referencias a nodos, sin tener el objeto set.

Los algoritmos estándar están diseñados para tener complejidades computacionales transparentes (o al menos consistentemente fáciles de recordar). Una función para eliminar selectivamente elementos de un set sería O (N log N), debido a la necesidad de reequilibrar el árbol, que no es mejor que un bucle llamando al my_set.remove(). Entonces, el estándar no lo proporciona, y eso es lo que necesita escribir.

Por otro lado, un bucle ingenuamente codificado a mano para eliminar elementos de un vector uno por uno sería O (N^2), mientras que std::remove_if es O (N). Entonces, la biblioteca proporciona un beneficio tangible en ese caso.

Un circuito típico (estilo 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 () 
    } 
} 

Editar (4 años más tarde!): i ++ parece sospechoso allí. ¿Qué sucede si erase invalida i antes de que el operador de incremento posterior pueda actualizarlo? Esto está bien, sin embargo, porque es un operator++ sobrecargado en lugar del operador integrado. La función actualiza con seguridad i in situ y luego devuelve una copia de su valor original.

Answer 2

El mensaje de error dice

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

Nota del const. El compilador es correcto que std::wstring no tiene un operator= que se puede invocar en un objeto const.

¿Por qué la cuerda es const? La respuesta es que los valores en un std::set son inmutables, porque los valores en un conjunto están ordenados, y cambiar un valor podría cambiar su orden en el conjunto, invalidando el conjunto.

¿Por qué el compilador intenta copiar un valor del conjunto?

std::remove_if (y std::remove) en realidad no borran nada (ni pueden, debido a que no tienen el contenedor, solo iteradores). Lo que hacen es copiar todos los valores en el rango que no coinciden con el criterio hasta el comienzo del rango, y devolver un iterador al siguiente elemento después de los elementos coincidentes. Se supone que debe borrar manualmente desde el iterador devuelto hasta el final del rango. Como un conjunto mantiene sus elementos en orden, sería incorrecto mover cualquier elemento, por lo que remove_if no se puede usar en un conjunto (o en cualquier otro contenedor asociativo).

En pocas palabras, usted tiene que utilizar un bucle de std::find_if y set::erase, así:

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); 
    } 
}