¿Qué pasa con `std :: set`?

Question

En the other topic estaba tratando de resolver el problema this. El problema era eliminar los caracteres duplicados de std::string.

std::string s= "saaangeetha"; 

Dado que el orden no era importante, así que ordenan s primero, y luego se usa std::unique y, finalmente, cambiar de tamaño para obtener the desired result:

aeghnst 

Eso es correcto!

---

Ahora quiero hacer lo mismo, pero al mismo tiempo quiero que el orden de los caracteres esté intacto. Medios, quiero esta salida:

sangeth 

Así que escribió this:

template<typename T> 
struct is_repeated 
{ 
    std::set<T> unique; 
    bool operator()(T c) { return !unique.insert(c).second; } 
}; 
int main() { 
    std::string s= "saaangeetha"; 
    s.erase(std::remove_if(s.begin(), s.end(), is_repeated<char>()), s.end()); 
    std::cout << s ; 
} 

que da a esta salida:

saangeth 

Es decir, a se repite, aunque otras repeticiones desaparecido. ¿Qué está mal con el código?

De todos modos yo change my code un poco: (ver el comentario)

template<typename T> 
struct is_repeated 
{ 
    std::set<T> & unique; //made reference! 
    is_repeated(std::set<T> &s) : unique(s) {} //added line! 
    bool operator()(T c) { return !unique.insert(c).second; } 
}; 
int main() { 
    std::string s= "saaangeetha"; 
    std::set<char> set; //added line! 
    s.erase(std::remove_if(s.begin(),s.end(),is_repeated<char>(set)),s.end()); 
    std::cout << s ; 
} 

Salida:

sangeth 

problema ha ido!

¿Qué pasa con la primera solución?

Además, si no hago la variable de miembro unique tipo de referencia, entonces the problem doesn't go.

¿Qué ocurre con std::set o is_repeated functor? ¿Dónde exactamente está el problema?

También observo que si el functor is_repeated se copia en alguna parte, entonces también se copiará cada miembro. ¡No veo el problema aquí!

Answer 1

In GCC (libstdc++), remove_if se implementa esencialmente como

template<typename It, typename Pred> 
    It remove_if(It first, It last, Pred predicate) { 
     first = std::find_if(first, last, predicate); 
    //         ^^^^^^^^^ 
     if (first == last) 
     return first; 
     else { 
     It result = first; 
     ++ result; 
     for (; first != last; ++ first) { 
      if (!predicate(*first)) { 
    //   ^^^^^^^^^ 
       *result = std::move(*first); 
       ++ result; 
      } 
     } 
     } 
    } 

en cuenta que su predicado se pasa por valor a find_if, por lo que la estructura, y por lo tanto el conjunto, modificada dentro find_if no se propagarán de nuevo a llamador.

Desde la primera duplicada aparece en:

saaangeetha 
//^

El "sa" inicial se mantendrá después de la llamada find_if. Mientras tanto, el conjunto predicate está vacío (las inserciones dentro de find_if son locales). Por lo tanto, el ciclo posterior mantendrá el 3 a.

sa | angeth 
// ^^ ^^^^^^ 
// || kept by the loop in remove_if 
// || 
// kept by find_if 

Answer 2

Supongo que el problema podría residir en que el functor is_repeated se copia en algún lugar dentro de la implementación de std::remove_if. Si ese es el caso, se usa el constructor de copia predeterminado y esto a su vez llama al constructor de copias std::set. Usted termina con dos funtores is_repeated posiblemente usados ​​de manera independiente. Sin embargo, como los conjuntos en ambos son objetos distintos, no ven los cambios mutuos. Si convierte el campo is_repeated::unique en una referencia, entonces el functor copiado todavía usa el conjunto original que es lo que quiere en este caso.

Answer 3

Se supone que los funtores deben diseñarse de manera que una copia de un funtor sea idéntica a la del functor original. Es decir, si hace una copia de un functor y luego realiza una secuencia de operaciones, el resultado debería ser el mismo sin importar qué functor use, o incluso si intercala los dos funtores. Esto le da a la implementación de STL la flexibilidad de copiar los funtores y pasarlos como lo crea conveniente.

Con su primer functor, este reclamo no se cumple porque si copio su functor y luego lo llamo, los cambios que realice en su conjunto almacenado no se reflejan en el functor original, por lo que la copia y el original funcionarán de manera diferente . Del mismo modo, si toma su segundo funtor y lo hace no almacena su conjunto por referencia, las dos copias del funtor no se comportarán de manera idéntica.

No obstante, la razón por la que funciona la versión final del functor es porque el hecho de que el conjunto se almacene por referencia significa que cualquier cantidad de copias del funtor de tue se comportarán idénticamente entre sí.

Espero que esto ayude!

Answer 4

No es realmente una respuesta, pero como otro dato interesante a tener en cuenta, que esto hace el trabajo, a pesar de que utiliza el funtor el original:

#include <set> 
#include <iostream> 
#include <string> 
#include <algorithm> 
#include <iterator> 

template<typename T> 
struct is_repeated { 
    std::set<T> unique; 
    bool operator()(T c) { return !unique.insert(c).second; } 
}; 
int main() { 
    std::string s= "saaangeetha"; 
    std::remove_copy_if(s.begin(), s.end(), 
         std::ostream_iterator<char>(std::cout), 
         is_repeated<char>()); 
    return 0; 
} 

Editar: no creo que afecta a este comportamiento, pero También corrigió un deslizamiento menor en su functor (el operador() aparentemente debería tomar un parámetro de tipo T, no char).

Answer 5

Las clases de funcionador deben ser funciones puras y no tener un estado propio. Ver el artículo 39 en el de Scott Meyer. Effective STL libro para una buena explicación sobre esto. Pero la esencia de esto es que tu clase de funtor puede ser copiada una o más veces dentro del algoritmo.

Answer 6

Las otras respuestas son correctas, ya que el problema es que el functor que está utilizando no es copiable seguro. En particular, el STL que viene con gcc (4.2) implementa std::remove_if como una combinación de std::find_if para localizar el primer elemento para eliminar seguido de std::remove_copy_if para completar la operación.

template <typename ForwardIterator, typename Predicate> 
std::remove_if(ForwardIterator first, ForwardIterator end, Predicate pred) { 
    first = std::find_if(first, end, pred); // [1] 
    ForwardIterator i = it; 
    return first == last? first 
      : std::remove_copy_if(++i, end, fist, pred); // [2] 
} 

La copia en [1] significa que el primer elemento que se encuentra se añade a la copia de la funtor y que significa que la primera 'a' se pierde en el olvido. El funtor también se copia en [2], y eso estaría bien si no fuera porque el original para esa copia es un funtor vacío.

Answer 7

Según la implementación de remove_if puede hacer copias de su predicado.De cualquier refactorizar su funtor y hacerlo sin estado o utilizar Boost.Ref a "para pasar referencias a funcionar plantillas (algoritmos) que suele tener copias de sus argumentos", así:

#include <set> 
#include <iostream> 
#include <string> 
#include <algorithm> 
#include <iterator> 

#include <boost/ref.hpp> 
#include <boost/bind.hpp> 

template<typename T> 
struct is_repeated { 
    std::set<T> unique; 
    bool operator()(T c) { return !unique.insert(c).second; } 
}; 

int main() { 
    std::string s= "saaangeetha"; 
    s.erase(std::remove_if(s.begin(), s.end(), boost::bind<bool>(boost::ref(is_repeated<char>()),_1)), s.end()); 
    std::cout << s; 

    return 0; 
}