c++ - unordered_set - unordered_map example

Asignación previa de depósitos en un C++ std:: unordered_map

Question

Estoy usando std::unordered_map de gnu ++ 0x para almacenar una gran cantidad de datos. Quiero asignar previamente espacio para la gran cantidad de elementos, ya que puedo enlazar el espacio total utilizado.

Lo que me gustaría poder hacer es llamar:

std::unordered_map m;
m.resize(pow(2,x));

donde se conoce x

std::unordered_map no admite esto. Preferiría usar std::unordered_map si es posible, ya que eventualmente formará parte del estándar.

Algunas otras restricciones:

Necesita acceso O (1) confiable y mutación del mapa. Las funciones de hash y comparación deseadas ya no son estándar y son algo caras. La mutación O (log n) (como con std::map ) es demasiado costosa.

-> El hash costoso y la comparación también hacen que el crecimiento basado en la amortización sea demasiado costoso. Cada inserción adicional requiere operaciones O (n) de esas funciones, lo que resulta en un término cuadrático adicional en el tiempo de ejecución del algoritmo, ya que los requisitos de almacenamiento exponencial necesitan crecimientos de O (n).

Answer 1

Creo que la repetición y la reserva funcionan solo si sabe de antemano cuánta memoria tomará su valor asignado. Si el valor asignado es complicado o cambia de tamaño dinámicamente (por ejemplo, un vector), necesitará su propia implementación. Por ejemplo, si su tamaño de memoria lo permite, puede reservar el contenedor más grande que pueda existir.

Answer 2

El constructor toma un parámetro "size_type bucket_count" según http://en.cppreference.com/w/cpp/container/unordered_map/unordered_map

así que la forma más sencilla de hacer lo que dice su código de ejemplo es:

std::unordered_map m{ pow(2,x) };

Esto será más eficiente, ya que no está definido cuántos cubos se reservarán en la construcción, de lo contrario, es posible que tenga que asignar y luego desasignar cuando llame a reserva después.

Answer 3

Le sugiero que escriba su propio asignador para el std::unordered_map que asigna la memoria exactamente de la forma que desee.

Answer 4

No creo que sea importante que un mapa desordenado tenga memoria asignada previamente. Se espera que el STL sea O (n) tiempo de inserción amortizado. Ahórrese la molestia de escribir su propio asignador hasta que sepa que este es el cuello de botella de su código, en mi opinión.

Answer 5

m.rehash(pow(2,x));

si pow(2, x) es el número de cubos que desea preasignar. Tú también puedes:

m.reserve(pow(2,x));

pero ahora pow(2, x) es el número de elementos que planea insertar. Ambas funciones no hacen nada más que preasignar cubos. No insertan ningún elemento. Y ambos están destinados a ser utilizados exactamente para su caso de uso.

Nota: No está garantizado que obtenga exactamente los pow(2, x) . Algunas implementaciones utilizarán solo un número de grupos, que es una potencia de 2. Otras implementaciones usarán solo un número primo de grupos. Otros utilizarán solo un subconjunto de números primos para el número de cubos. Pero en cualquier caso, la implementación debe aceptar su sugerencia en el número de grupos que desea, y luego redondear internamente al siguiente número aceptable de grupos.

Aquí está la redacción precisa que usa el último (N4660) para especificar el argumento para rehash :

a.rehash(n) : Condiciones posteriores: a.bucket_count() >= a.size() / a.max_load_factor() and a.bucket_count() >= n .

Esta condición posterior garantiza que bucket()_count() >= n , y que load_factor() permanezca menor o igual que max_load_factor() .

Posteriormente, la reserve(n) se define en términos de rehash(n) :

a.reserve(n) : igual que a.rehash(ceil(n / a.max_load_factor())) .