¿Qué hay de malo en `std :: set`?

Question

En el otro tema Estaba tratando de resolver este problema. El problema era eliminar los personajes duplicados de un std::string.

std::string s= "saaangeetha";

Dado que la orden no era importante, así que ordené s primero y luego usado std::unique y finalmente lo cambia de tamaño para obtener el resultado deseado:

aeghnst

¡Eso es correcto!

---

Ahora quiero hacer lo mismo, pero al mismo tiempo quiero intacto el orden de los personajes. Significa que quiero esta salida:

sangeth

Entonces escribí este:

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 esta salida:

saangeth

Eso es, a se repite, aunque otras repeticiones se fueron. ¿Qué le pasa al código?

De todos modos yo Cambiar mi código 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 ;
}

Producción:

sangeth

¡Problema se fue!

Entonces, ¿qué hay de malo en la primera solución?

Además, si no hago la variable del miembro unique Tipo de referencia, entonces El problema no va.

Lo que está mal con std::set o is_repeated Funcor? ¿Dónde está exactamente el problema?

También noto que si el is_repeated El functor se copia en algún lugar, entonces cada miembro también se copia. ¡No veo el problema aquí!

Answer 1

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

Tenga en cuenta que se pasa su predicado por valor a find_if, entonces la estructura, y por lo tanto el conjunto, modificado en el interior find_if no se propagará a la persona que llama.

Dado que el primer duplicado aparece en:

  saaangeetha
//  ^

La inicial "sa" se mantendrá después del find_if llamar. Mientras tanto, el predicateEl conjunto está vacío (las inserciones dentro find_if son locales). Por lo tanto, el bucle luego mantendrá el 3er a.

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

Answer 2

Se supone que los functores están diseñados de una manera en la que una copia de un functor es idéntica al functor original. Es decir, si realiza una copia de un functor y luego realiza una secuencia de operaciones, el resultado debe ser el mismo sin importar qué functor use, o incluso si intercalas los dos functores. Esto le da a la implementación STL la flexibilidad de copiar functores y pasarlos como lo considera adecuado.

Con su primer functor, esta afirmación no se mantiene porque si copio su functor y luego lo llamo, los cambios que realiza 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 functor y hace que no almacene su conjunto por referencia, las dos copias del functor no se comportarán de manera idéntica.

Sin embargo, la razón por la que su versión final del functor funciona es porque el hecho de que el conjunto se almacene por referencia significa que cualquier cantidad de copias de tue Funcionar se comportarán de manera idéntica entre sí.

¡Espero que esto ayude!

Answer 3

No es realmente una respuesta, pero como otro dato interesante a tener en cuenta, esto funciona, a pesar de que usa el functor 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 afecte este comportamiento, pero también he corregido un resbalón menor en su functor (operador () aparentemente debería tomar un parámetro de tipo T, no char).

Answer 4

Supongo que el problema podría estar en el sentido de que el is_repeated el functor 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 std::set Copiar constructor. Terminas con dos is_repeated Functores posiblemente utilizados de forma independiente. Sin embargo, como los conjuntos en ambos son objetos distintos, no ven los cambios mutuos. Si giras el campo is_repeated::unique A una referencia, entonces el functor copiado todavía usa el conjunto original, que es lo que desea en este caso.

Answer 5

Las clases de functores deben ser funciones puras y no tener estado propio. Ver artículo 39 en Scott Meyer's STL efectivo Reserve para una buena explicación sobre esto. Pero lo esencial es que su clase de functores se puede copiar 1 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 copiado 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 un 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 encontrado se agrega a la copia del functor y eso significa que el primer 'A' se perderá en el olvido. El functor también se copia en [2], y eso estaría bien si no fuera porque el original para esa copia es un functor vacío.

Answer 7

Dependiendo de la implementación de remove_if puede hacer copias de su predicado. Refactorizar su functor y hacerlo apátrate o usar Impulso.ref a "para pasar referencias a plantillas de funciones (algoritmos) que generalmente tomarían copias de sus argumentos", como 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;
}