Cosa c'è di sbagliato in `std :: set`?

Question

In l'altro argomento Stavo cercando di risolvere questo problema. Il problema era rimuovere i caratteri duplicati da a std::string.

std::string s= "saaangeetha";

Poiché l'ordine non era importante, quindi ho risolto s prima, e poi usato std::unique e infine ridimensionò per ottenere il risultato desiderato:

aeghnst

È corretto!

---

Ora voglio fare lo stesso, ma allo stesso tempo voglio intatto l'ordine dei personaggi. Significa che voglio questo output:

sangeth

Quindi ho scritto questo:

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

Che dà questo output:

saangeth

Questo è, a si ripete, sebbene altre ripetizioni sparissero. Cosa c'è di sbagliato nel codice?

Comunque io Cambia il mio codice un po ': (vedi il commento)

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

Produzione:

sangeth

Problema andato!

Allora cosa c'è di sbagliato nella prima soluzione?

Inoltre, se non faccio variabile il membro unique Tipo di riferimento, quindi Il problema non va.

Cosa c'è che non va std::set o is_repeated funttore? Dov'è esattamente il problema?

Noto anche che se il is_repeated Functor viene copiato da qualche parte, quindi anche ogni membro di esso viene copiato. Non vedo il problema qui!

Answer 1

In GCC (libstdc ++), remove_if è implementato essenzialmente come

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

Nota che il tuo predicato è passato per valore a find_if, quindi la struttura, e quindi l'insieme, modificata all'interno find_if non verrà propagato al chiamante.

Poiché il primo duplicato appare a:

  saaangeetha
//  ^

L'iniziale "sa" sarà mantenuto dopo il find_if chiamata. Nel frattempo, il predicateIl set è vuoto (gli inserimenti all'interno find_if sono locali). Pertanto il ciclo successivamente manterrà il 3 ° a.

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

Answer 2

I funttori dovrebbero essere progettati in un modo in cui una copia di un funtor è identica al funtore originale. Cioè, se si crea una copia di un functor e quindi esegui una sequenza di operazioni, il risultato dovrebbe essere lo stesso indipendentemente da quale funtor utilizzi o anche se si interrompe i due funzioni. Ciò fornisce all'implementazione STL la flessibilità di copiare i funttori e passarli in giro mentre ritiene opportuno.

Con il tuo primo funtor, questa affermazione non è valida perché se copio il tuo funtor e poi lo chiamo, le modifiche apportate al suo set memorizzato non si riflettono nel funtore originale, quindi la copia e l'originale si funzionano in modo diverso. Allo stesso modo, se prendi il tuo secondo funtore e non lo fai memorizzare il suo set su riferimento, le due copie del functor non si comporteranno in modo identico.

Il motivo per cui funziona la versione finale di Functor, tuttavia, è perché il fatto che il set sia archiviato per riferimento significa che qualsiasi numero di copie di Tue Functor si comporterà in modo identico l'uno con l'altro.

Spero che sia di aiuto!

Answer 3

Non proprio una risposta, ma come un altro bocconcino interessante da considerare, questo funziona, anche se utilizza il funtore originale:

#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: non credo che influisca su questo comportamento, ma ho anche corretto una piccola scorrimento nel tuo functor (operatore () apparentemente dovrebbe prendere un parametro di tipo T, non char).

Answer 4

Suppongo che il problema possa risiedere in quanto il is_repeated functor viene copiato da qualche parte all'interno dell'implementazione di std::remove_if. In tal caso, viene utilizzato il costruttore di copie predefinito e questo a sua volta chiama std::set Copia costruttore. Finisci con due is_repeated funzioni probabilmente usate in modo indipendente. Tuttavia, poiché i set in entrambi sono oggetti distinti, non vedono i cambiamenti reciproci. Se giri il campo is_repeated::unique A un riferimento, quindi il funtor copiato utilizza ancora il set originale che è quello che si desidera in questo caso.

Answer 5

Le lezioni di functor dovrebbero essere funzioni pure e non avere uno stato proprio. Vedi l'articolo 39 in Scott Meyer Efficace STL Prenota per una buona spiegazione su questo. Ma l'essenza è che la tua classe functor può essere copiata 1 o più volte all'interno dell'algoritmo.

Answer 6

Le altre risposte sono corrette, in quanto il problema è che il funtor che stai usando non lo è copiabile sicuro. In particolare, lo STL fornito con GCC (4.2) implementa std::remove_if come combinazione di std::find_if Per individuare il primo elemento da eliminare seguito da un std::remove_copy_if Per completare l'operazione.

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 in [1] significa che il primo elemento trovato viene aggiunto alla copia di Functor e ciò significa che il primo "A" andrà perso nell'oblio. Il funtore viene anche copiato in [2] e va bene se non fosse dovuto al fatto che l'originale per quella copia è un funtore vuoto.

Answer 7

A seconda dell'attuazione di remove_if può fare copie del tuo predicato. Refactor il tuo funtore e rendilo apolidi o usa Boost.ref a "per passare riferimenti ai modelli di funzione (algoritmi) che di solito prendono copie dei loro argomenti", come così:

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