C++ std :: map o std :: set - insertar de manera eficiente duplicados

Question

Tengo un montón de datos llenos de duplicados y quiero eliminar los duplicados. Ya sabes, por ejemplo [1, 1, 3, 5, 5, 5, 7] se convierte en [1, 3, 5, 7].

Parece que puedo usar std :: map o std :: set para manejar esto. Sin embargo, no estoy seguro de si es más rápido (a) simplemente insertar todos los valores en el contenedor, o (b) verificar si ya existen en el contenedor y solo insertar si no lo hacen: ¿los insertos son muy eficientes? Incluso si hay una mejor manera ... ¿puedes sugerir una manera rápida de hacer esto?

Otra pregunta: si los datos que estoy almacenando en ellos no son tan triviales como enteros, y en su lugar es una clase personalizada, ¿cómo logra std :: map almacenar correctamente (hash?) Los datos para una rápida acceso a través del operador []?

Answer 1

std::map no utiliza hash. std::unordered_map, pero eso es C++ 11. std::map y std::set ambos usan un comparador que usted proporciona. Las plantillas de clase tienen los valores predeterminados para este comparador, que se reduce a una comparación de operator<, pero puede proporcionar la suya propia.

Si no necesita una clave y un valor para almacenar (parece que no) debe usar un std::set, ya que es más apropiado.

El estándar no dice qué estructuras de datos map sy set s usan bajo el capó, solo que las acciones de certificación tienen ciertas complejidades de tiempo. En realidad, la mayoría de las implementaciones que conozco usan un árbol.

Se hace sabios tiempo-complejidad-ninguna diferencia si se utiliza o operator[]insert, pero me gustaría utilizar insert o operator[] antes de que hiciera un search seguido de un insert si no se encuentra el elemento. Lo último implicaría dos búsquedas separadas para insertar un elemento en el conjunto.

Answer 2

Suponiendo que la estrategia de implementación común para std::map y std::set, es decir árboles de búsqueda binaria equilibrados, tanto la inserción como la búsqueda tienen que hacer un recorrido de árbol para encontrar el lugar donde debería estar la clave. Por lo tanto, la búsqueda fallida seguida de la inserción sería aproximadamente el doble de lenta que la inserción.

¿Cómo logra el std :: map almacenar correctamente (¿hash?) Los datos para un acceso rápido a través del operador []?

Por medio de una función de comparación que se especifica (o std::less, que funciona si sobrecarga operator< en su tipo personalizado). En cualquier caso, std::map y std::set son no tablas hash.

Answer 3

Un insert() en cualquiera de los contenedores asociados hace un find() para ver si el objeto existe y luego inserta el objeto. Simplemente insertando los elementos en un std::set<T> debería deshacerse de los duplicados de forma razonablemente eficiente.

Dependiendo del tamaño de la unidad y la relación de los duplicados de valores únicos, puede ser más rápido para poner los objetos en std::vector<T>, std::sort() a continuación, y luego usar std::unique() junto con std::vector<T>::erase() para deshacerse de los duplicados.

Answer 4

¿Cuántas veces deberías hacerlo?

Si inserto es habitual:

//*/ 
std::set<int> store; 
/*/ 
// for hash: 
std::unordered_set<int> store; 
//*/ 
int number; 

if (store.insert(number).second) 
{ 
    // was not in store 
} 

Si se llena una vez:

std::vector<int> store; 
int number; 

store.push_back(number); 
std::sort(store.begin(),store.end()); 
store.erase(std::unique(store.begin(),store.end()),store.end()); 

// elements are unique 

Answer 5

std::set y std::map ambos están implementados como árbol negro rojo hasta donde yo sé. Y probablemente usar solo la inserción sería más rápido (ambos porque duplicaría el tiempo de búsqueda).

También map y set usan operator <. Siempre y cuando su clase haya definido operator <, podrá usarlos como claves.