Contenedor más rápido de C++: valores únicos

Question

Estoy escribiendo una aplicación de correo electrónico que interactúa con una base de datos MySQL. Tengo dos tablas que están obteniendo mis datos, uno de los cuales contiene anulaciones, y el otro es una tabla de usuarios estándar. A partir de ahora, estoy creando un vector de punteros para enviar por correo electrónico los objetos, y almacenar todos los correos electrónicos no suscritos, inicialmente. Luego tengo un bucle de SQL estándar en el que estoy verificando para ver si el correo electrónico no está en el vector de cancelación de suscripción, y luego lo agrego al vector de envío de correo electrónico global. Mi pregunta es, ¿hay una manera más eficiente de hacer esto? Tengo que buscar en el vector sudes para cada correo electrónico en mi sistema, hasta 50 mil diferentes. ¿Hay una mejor estructura para buscar? Y, ¿una mejor estructura para mantener una colección única de valores? ¿Quizás uno que simplemente descartaría el valor si ya lo contiene?

Answer 1

Si la implementación de su biblioteca C++ Standard lo admite, considere utilizar std::unordered_set o std::hash_set.

También puede usar std::set, aunque su sobrecarga puede ser mayor (depende del costo de generar un hash para el objeto en comparación con el costo de comparar dos de los objetos varias veces).

Si usted hace uso de un contenedor basado nodo como set o unordered_set, usted también consigue la ventaja de que la eliminación de elementos es relativamente barato en comparación con la eliminación de una vector.

Answer 2

Almacene sus direcciones de correo electrónico en std::set o use std::set_difference().

Answer 3

1. Tareas como esta (establecer manipulaciones) son mejor dejarlas para lo que significa llevarlas a cabo - ¡la base de datos!

   E.g. algo a lo largo de las líneas de:

   SELECT email FROM all_emails_table e WHERE NOT EXISTS (
       SELECT 1 FROM unsubscribed u where e.email=u.email 
   ) 
   

2. Si desea un algoritmo, se puede hacer esto mediante la recuperación rápida tanto en la lista de mensajes de correo electrónico y una lista de unsubscriptions como listas ordenadas. Luego puede revisar la lista de correo electrónico (que está ordenada), y mientras lo hace, se desliza a lo largo de la lista de cancelación de suscripción. La idea es que mueva 1 hacia adelante en cualquier lista que tenga el elemento "más grande" actual. Este algo es O (M + N) en lugar de O (M * N) como su actual

3. O bien, puede haga un mapa hash que se correlacione desde la dirección de correo electrónico no suscrita a 1. Luego, haga find() llamadas en ese mapa que para implementaciones correctas de hash son O (1) para cada búsqueda. Desafortunadamente, no hay un estándar Hash Map en C++. this SO question for existing implementations (par de ideas que hay de STL hash_map y Boost y/o TR1 std::tr1::unordered_map SGI)

   indica que se añadirá a la norma Uno de los comentarios en ese puesto:. "con esto en mente, el Informe Técnico Biblioteca estándar de C++ introducido los contenedores asociativos no ordenadas, que se implementan utilizando tablas hash, y ahora se han añadido a la Borrador de Trabajo del estándar de C++ ".

Answer 4

La mejor manera de hacer esto está dentro de MySQL, creo. Puede modificar el esquema de su tabla de usuarios con otra columna, una columna BIT, para "se anula la suscripción". Mejor aún: agregue una columna DATETIME para "fecha eliminada" con un valor predeterminado de NULL.

Si se utiliza una columna BIT, la consulta se convierte en algo así como:

SELECT * FROM `users` WHERE `unsubscribed` <> 0b1; 

Si se utiliza una columna DATETIME, la consulta se convierte en algo así como:

SELECT * FROM `users` WHERE `date_unsubscribed` IS NULL;