std :: set :: insert, ¿qué tan mal puedo insinuar?

Question

Estoy haciendo muchas inserciones de std::pair<int, int> en un std::set, y me está tomando más tiempo de lo que quisiera. Cuando escribí el código, me figuré que usaría el formulario itector de sugerencia de insertar más adelante si resultara ser un cuello de botella; bueno, ahora está perfilado y es es un cuello de botella. Entonces quiero usar la sugerencia del iterador.

Sin embargo, no siempre sabré una buena posición para insertar mis pares. Normalmente los inserto en lotes (un lote en este caso es del orden del 0.01% del tamaño de entrada total, duplicados incluidos) de orden creciente, pero cuando se inserta un lote, no sé dónde debería estar el siguiente comienzo. ¿Cómo se usa la pista? ¿La inserción hace algo así como una búsqueda binaria desde la posición sugerida? ¿Qué tan malo sería usar una mala pista, por lo general?

Answer 1

Sugiero simplemente leer lo que lee el compilador: el archivo de encabezado para #include <set>. En mi sistema (GNU libstdC++ 4.5.1) que puede leer el siguiente texto explica por sí mismo:

/** 
    * @brief Attempts to insert an element into the %set. 
    * @param position An iterator that serves as a hint as to where the 
    *     element should be inserted. 
    * @param x Element to be inserted. 
    * @return An iterator that points to the element with key of @a x (may 
    *   or may not be the element passed in). 
    * 
    * This function is not concerned about whether the insertion took place, 
    * and thus does not return a boolean like the single-argument insert() 
    * does. Note that the first parameter is only a hint and can 
    * potentially improve the performance of the insertion process. A bad 
    * hint would cause no gains in efficiency. 
    * 
    * For more on @a hinting, see: 
    * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html 
    * 
    * Insertion requires logarithmic time (if the hint is not taken). 
    */ 
    iterator 
    insert(iterator __position, const value_type& __x) 
    { return _M_t._M_insert_unique_(__position, __x); } 

Para llevar:

1. Un mal indicio causaría ninguna ganancia en eficiencia
2. Inserción es O(log n)
3. Puede leer aún más acerca de insertion hints in the GNU libstdc++ manual.

Answer 2

Una sugerencia es bueno si es la indirecta derecha - la posición de usar para una inserción. Funciona si inserta objetos secuencialmente, por ejemplo.

Si la sugerencia no es correcta, no tiene ningún efecto y obtiene una inserción no insinuada.

Answer 3

Si comprueba el archivo bits/stl_tree.h (en GNU libstdC++), encontrará que la función de miembro _M_insert_unique con un argumento de sugerencia muestra un nodo a la izquierda de la sugerencia, luego un nodo a la derecha y luego realiza una llamada predeterminada la rutina de inserción ordinaria.

Llama al key_compare al menos una vez (si el conjunto no está vacío) y como máximo tres veces. Pasar de un nodo al siguiente o anterior es una cuestión de seguir un puntero desde (IIRC) std::set y sus amigos son threaded trees.

Entonces, qué mala es una mala pista depende de la rutina de comparación y de si el asignador de std::set empaqueta los nodos en la memoria.

Answer 4

Si está construyendo el conjunto de una vez antes de usarlo, puede usar un vector y ordenarlo antes de usarlo. Puede utilizar los algoritmos binary_search, lower_bound, upper_bound y equal_range en un vector ordenado para búsquedas rápidas. También puede usar merge o inplace_merge para combinar vectores ordenados, y set_difference, set_intersection y set_union para realizar otras operaciones de conjunto común.