Rimuovere i duplicati da una lista <int>

Question

Utilizzando algoritmi STL (per quanto possibile), come remove_if() e list::erase, c'è un bel modo per rimuovere i duplicati da un elenco definito come segue:

list<int> l;

Si prega di notare che list::unique() funziona solo se la duplicazione si verifica in elementi consecutivi. Nel mio caso, tutti i duplicati devono essere eliminati indipendentemente dalla loro posizione nell'elenco. Inoltre, rimuovere i duplicati significa preservare solo una copia di ciascun elemento nel risultato finale.

MODIFICA: l'opzione per l.sort() seguita da l.unique() non può essere utilizzata poiché distruggerà l'ordine della lista.

Answer 1

Utilizzando la funzione list::remove_if membro, un set hash temporanea, e l'espressione lambda.

Answer 2

Se preservare l'ordine della lista non è importante, si può solo fare list.sort(); list.unique();

Se l'ordine è importante, utilizzare il suggerimento di Rup: ​​

list<int>::iterator iter = l.begin(); 
set<int> elements; 
while (iter != l.end()) { 
    if (elements.find(*iter) != elements.end()) 
    iter = l.erase(iter); 
    else { 
    elements.insert(*iter); 
    ++iter; 
    } 
} 

Answer 3

Ha detto che voleva utilizzare l'erase- rimuovere linguaggio, ecco un modo possibile, utilizzando un oggetto funzione:

struct Unifier{ 
    set<int> foundElements; 

    bool operator()(int & a){ 
     if(foundElements.find(a) != foundElements.end()){ 
      return true; 
     }else{ 
      foundElements.insert(a); 
      return false; 
     } 
    } 
}; 


int main(){ 
    list<int> v; 

    v.push_back(5); 
    v.push_back(4); 
    v.push_back(5); 
    v.push_back(3); 
    v.push_back(5); 
    v.push_back(3); 

    copy (v.begin(), v.end(), ostream_iterator<int>(cout," ")); 

    Unifier u; 
    v.remove_if(u); 

    cout << endl << "After:" << endl; 
    copy (v.begin(), v.end(), ostream_iterator<int>(cout," ")); 

} 

---

Aggiornamento: il codice precedente presenta un bug sottile. Secondo C++ 11 [algorithms.general]/10:

[Nota: se non diversamente specificato, gli algoritmi che accettano oggetti funzione come argomenti sono autorizzati a copiare liberamente tali oggetti funzione. I programmatori per i quali l'identità dell'oggetto è importante dovrebbero prendere in considerazione l'utilizzo di una classe wrapper che punta a un oggetto di implementazione non protetto, ad esempio reference_wrapper<T> (20.8.3) o una soluzione equivalente. Nota -end]

non sembra esserci nessun "altrimenti specificato" per std::list::remove_if, quindi questo codice potrebbe non riuscire a rimuovere tutti i duplicati perché può creare copie del predicato alla partenza, e quindi utilizzare diverse copie del predicato per diverse parti della lista. Example of this actually happening for std::remove_if.

Una semplice correzione per C++ 11 è quello di sostituire v.remove_if(u) con:

v.remove_if(reference_wrapper<decltype(u)>(u)); 

In C++ 03 non sono sicuro se la citazione di cui sopra era presente; ma se fosse una correzione, sarebbe necessario rendere statico lo foundElements o il refactor Unifier in modo che tutte le copie di esso facciano riferimento a una singola istanza di foundElements.

Link to related question