Quel est le problème avec `std :: set`?

Question

Dans L'autre sujet J'essayais de résoudre cette problème. Le problème était de supprimer les caractères en double d'un std::string.

std::string s= "saaangeetha";

Puisque la commande n'était pas importante, alors j'ai trié s D'abord, puis utilisé std::unique et finalement le redimensionner pour obtenir le résultat souhaité:

aeghnst

C'est correct!

---

Maintenant, je veux faire de même, mais en même temps, je veux que l'ordre des personnages est intact. Signifie, je veux cette sortie:

sangeth

Alors j'ai écrit cette:

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

Qui donne cette sortie:

saangeth

C'est-à-dire, a est répété, bien que d'autres répétitions aient disparu. Quel est le problème avec le code?

De toute façon je changer mon code Un peu: (voir le commentaire)

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

Production:

sangeth

Problème disparu!

Alors, qu'est-ce qui ne va pas avec la première solution?

Aussi, si je ne fais pas la variable du membre unique Type de référence, alors Le problème ne se passe pas.

Qu'est-ce qui ne va pas chez std::set ou is_repeated Fonctor? Où est exactement le problème?

Je note aussi que si le is_repeated Functor est copié quelque part, puis chaque membre est également copié. Je ne vois pas le problème ici!

Answer 1

Dans GCC (libstdc ++), remove_if est mis en œuvre essentiellement comme

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

Notez que votre prédicat est passé valeur par la valeur à find_if, donc la structure, et donc l'ensemble, modifié à l'intérieur find_if ne sera pas propagé à l'appelant.

Puisque le premier double apparaît sur:

  saaangeetha
//  ^

La première "sa" sera conservé après le find_if appel. En attendant, le predicateL'ensemble est vide (les insertions à l'intérieur find_if sont locaux). Par conséquent, la boucle conservera ensuite le 3ème a.

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

Answer 2

Les fonds sont censés être conçus de manière à ce qu'une copie d'un fonctor soit identique au fonctor d'origine. Autrement dit, si vous faites une copie d'un fonctor et effectuez ensuite une séquence d'opérations, le résultat doit être le même, quel que soit le fonctor que vous utilisez, ou même si vous entrelacez les deux Fonctors. Cela donne à la mise en œuvre de la STL la flexibilité de copier des fonds et de les faire passer comme bon s’en juge.

Avec votre premier Functor, cette affirmation ne tient pas car si je copie votre fonctor, puis l'appelle, les modifications que vous apportez à son ensemble stocké ne reflètent pas dans le fonctor d'origine, donc la copie et l'original se produiront différemment. De même, si vous prenez votre deuxième Functor et ne le faites pas stocker son ensemble par référence, les deux copies du Functor ne se comporteront pas de manière identique.

La raison pour laquelle votre version finale du Functor fonctionne, cependant, est due au fait que l'ensemble est stocké par référence signifie que tout nombre de copies de Tue Functor se comportera de manière identique.

J'espère que cela t'aides!

Answer 3

Pas vraiment une réponse, mais comme une autre friandise intéressante à considérer, cela fonctionne, même s'il utilise le fonctor d'origine:

#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: Je ne pense pas que cela affecte ce comportement, mais j'ai également corrigé un mineur de glissement dans votre fonctor (opérateur () devrait apparemment prendre un paramètre de type T, pas char).

Answer 4

Je suppose que le problème pourrait résider en ce que le is_repeated Functor est copié quelque part à l'intérieur de la mise en œuvre de std::remove_if. Si tel est le cas, le constructeur de copie par défaut est utilisé et cela appelle à son tour std::set Copier le constructeur. Tu vous retrouve avec deux is_repeated Les fonds peuvent être utilisés indépendamment. Cependant, comme les ensembles de deux sont des objets distincts, ils ne voient pas les changements mutuels. Si vous tournez le champ is_repeated::unique À une référence, le Functor copié utilise toujours l'ensemble d'origine qui est ce que vous voulez dans ce cas.

Answer 5

Les classes de functor doivent être des fonctions pures et n'ont pas d'état de leur propre état. Voir l'article 39 dans Scott Meyer's STL efficace Réservez pour une bonne explication à ce sujet. Mais l'essentiel est que votre classe Functor peut être copiée 1 ou plus à l'intérieur de l'algorithme.

Answer 6

Les autres réponses sont correctes, en ce que le problème est que le fonctor que vous utilisez n'est pas copieux sûr. En particulier, le STL qui vient avec GCC (4.2) implémente std::remove_if comme une combinaison de std::find_if Pour localiser le premier élément à supprimer suivi d'un std::remove_copy_if Pour terminer l'opération.

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 copie dans [1] signifie que le premier élément trouvé est ajouté à la copie du fonctor et cela signifie que le premier «A» sera perdu dans l'oubli. Le Functor est également copié dans [2], et ce serait bien si ce n'était pas parce que l'original pour cette copie est un foncteur vide.

Answer 7

En fonction de la mise en œuvre de remove_if peut faire des copies de votre prédicat. Soit refactor votre fonctor et le rendre apatride ou utiliser Boost.ref à "pour passer des références aux modèles de fonction (algorithmes) qui prendraient généralement des copies de leurs arguments", comme ainsi:

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