eliminar duplicados de una lista <int>

Question

Usando algoritmos STL (lo más posible) como remove_if() y list::erase, ¿hay una buena manera de eliminar los duplicados de una lista definida de la siguiente manera:

list<int> l;

Atención: que list::unique() solo funciona si se produce duplicación en elementos consecutivos. En mi caso, todos los duplicados deben ser eliminados independientemente de su posición en la lista. Además, eliminar duplicados significa preservar solo una copia de cada elemento en el resultado final.

EDITAR: La opción a l.sort() seguida de no se puede utilizar, ya que eso destruirá el orden de la lista.

Answer 1

Uso de la función list::remove_if miembro, un conjunto hash temporal, y la expresión lambda.

std::list<int> l; 
std::unordered_set<int> s; 

l.remove_if([&](int n) { 
    return (s.find(n) == s.end()) ? (s.insert(n), false) : true; 
}); 

Answer 2

Si preservar el orden de la lista no es importante, sólo puede hacer list.sort(); list.unique();

Si la orden es importante, utilice la sugerencia de 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

Dijo que quería utilizar el Borrar: eliminar idioma, así que aquí tiene una forma posible, utilizando un objeto función:

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," ")); 

} 

---

Actualización: El código anterior tiene un error sutil. Según C++ 11 [algorithms.general]/10:

[Nota: A menos que se especifique lo contrario, los algoritmos que toman los objetos de función como argumentos están autorizados a copiar los objetos función libremente. Los programadores para quienes la identidad del objeto es importante deberían considerar el uso de una clase contenedora que apunte a un objeto de implementación no copiado, como reference_wrapper<T> (20.8.3), o alguna solución equivalente. nota -fin]

No parece haber ninguna "se especifique lo contrario" para std::list::remove_if, por lo que este código puede fallar para eliminar todos los duplicados, ya que puede crear copias del predicado al principio, y luego usar diferentes copias de la predicado para diferentes partes de la lista. Example of this actually happening for std::remove_if.

Una solución simple para C++ 11 es reemplazar v.remove_if(u) con:

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

En C++ 03 No estoy seguro de si la cita anterior estaba presente; pero si fuera entonces una solución sería hacer que foundElements sea estático, o refactorizar Unifier para que todas las copias de él hagan referencia a una sola instancia de foundElements.

Link to related question