2012-10-10 121 views
6

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].C++ std :: map o std :: set - insertar de manera eficiente duplicados

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 []?

+1

Un 'conjunto 'sería más adecuado ya que no necesita un valor asociado con cada elemento. Voy a adivinar que revisar y luego insertar en el conjunto será más lento que simplemente insertar porque esencialmente tendrías que hacer dos búsquedas clave en el primero. – GWW

+3

Por definición, cualquiera de ellos comprobará * por usted * cuando realice la inserción. Es decir. ellos harán lo que de otro modo harían con algún otro contenedor: verificar la existencia. Personalmente, iría con el set a menos que intencionalmente estés mapeando algo con otra cosa. – WhozCraig

+3

¿Los datos están siempre ordenados? Porque parece que desea [std :: unique] (http://msdn.microsoft.com/en-us/library/9f5eztca (v = vs.100) .aspx), no es un contenedor nuevo –

Respuesta

9

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.

0

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.

7

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.

+0

* "' insert() '[...] hace un' find() '[pero si no se encuentra] inserta ..." * - el formato de estilo de código de 'find()' podría tomarse por algunos lectores como una llamada a la llamada a la API 'find()', mientras que las implementaciones 'insert (x)' literalmente no usarán '.find (x)' ya que cuando no está presente no hay registro de (iterator to) donde se abandonó la búsqueda, que es necesaria para omitir otro árbol O (logN) para la inserción real. Podrías acercarte con 'lower_bound' seguido de' insert' sobrecarga usando un iterador 'hint', pero las implementaciones' insert' manejarán esto internamente para un rendimiento óptimo. –

2

¿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 
0

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.

Cuestiones relacionadas