c++ - example - std set count

¿Qué está mal con `std:: set`?

Question

En el otro tema estaba tratando de resolver este problema. El problema fue eliminar los caracteres duplicados de una std::string .

std::string s= "saaangeetha";

Como el orden no era importante, ordené primero s , luego usé std::unique y finalmente lo cambié de tamaño para obtener el resultado deseado :

aeghnst

¡Eso es correcto!

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

sangeth

Así que escribí 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 ;
}

Lo que da esta salida:

saangeth

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

De todos modos cambio un poco mi código : (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 ido

Entonces, ¿qué está mal con la primera solución?

Además, si no hago el tipo de referencia unique variable miembro, el problema no desaparece .

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

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

Answer 1

Dependiendo de la implementación de remove_if puedes hacer copias de tu predicado. Refactorice su functor y haga que no tenga estado o use Boost.Ref para "pasar referencias a plantillas de función (algoritmos) que normalmente tomarían 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;
}

Answer 2

Las clases de funciones deben ser funciones puras y no tener un estado propio. Vea el artículo 39 del libro Effective STL de Scott Meyer para una buena explicación sobre esto. Pero lo esencial es que su clase de functor puede copiarse una o más veces dentro del algoritmo.

Answer 3

Las otras respuestas son correctas, ya que el problema es que el functor que está utilizando no es seguro para copiar . En particular, la STL que viene con gcc (4.2) implementa std::remove_if como una combinación de std::find_if para ubicar el primer elemento a 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 encontrado se agrega a la copia del functor y eso significa que la primera ''a'' se perderá en el olvido. El functor también se copia en [2], y estaría bien si no fuera porque el original de esa copia es un functor vacío.

Answer 4

No es realmente una respuesta, pero como otro dato interesante a considerar, esto funciona, a pesar de que utiliza el funtor 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;
}

Edit: no creo que afecte a este comportamiento, pero también he corregido un error menor en su functor (operator () aparentemente debería tomar un parámetro de tipo T, no char ).

Answer 5

Se supone que los funcionales se diseñan de una manera en la que una copia de un funcional es idéntica a la del 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é funtor utilice, o incluso si intercala los dos functores. Esto le da a la implementación de STL la flexibilidad para copiar los funtores y pasarlos como mejor le parezca.

Con su primer functor, esta afirmación no es válida porque si copio su funtor y luego lo llamo, los cambios que realice en su conjunto almacenado no se reflejarán en el funtor original, por lo que la copia y el original tendrán un rendimiento diferente. De manera similar, 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 número de copias de tue functor se comportarán de manera idéntica entre sí.

¡Espero que esto ayude!

Answer 6

Supongo que el problema podría radicar 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 a std::set copy constructor. Usted termina con dos functores is_repeated posiblemente utilizados de forma independiente. Sin embargo, como los conjuntos en ambos son objetos distintos, no ven los cambios mutuos. Si convierte 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 7

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 su predicado se pasa por valor a find_if , por lo que la estructura y, por lo tanto, el conjunto modificado dentro de find_if no se propagará de nuevo al llamante.

Desde el primer duplicado aparece en:

 saaangeetha
// ^

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

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