¿Cómo se comporta std::unordered

¿Cómo se comporta std::unordered_map? [C++]

Estaba leyendo sobre unordered_map en C++ y tengo algunas preguntas que no puedo responder claramente.

He notado que unordered_map coloca un elemento por índice y no múltiples (las tablas hash se pueden implementar utilizando uno de estos métodos para solucionar que 2 elementos se asignen al mismo índice).

1) ¿Si inserto un elemento con clave A en el mapa y luego inserto otro, se sobrescribirá el elemento anterior, cierto? (no importa si los valores coinciden o no).

2) ¿Existe alguna opción para cambiar el comportamiento de unordered_map para que pueda contener múltiples elementos por índice como expliqué anteriormente?

3) He notado en mi código que unordered_map se hace más grande en uno cada vez que inserto un nuevo elemento, pero eso es realmente malo, aprendí que en una tabla hash necesitamos multiplicar el tamaño por 2 cada vez que se necesita, para que la complejidad de inserción sea O (1) amortizado y no O(n).

4) ¿Cómo puedo darle a mi unordered_map un tamaño inicial pero sin elementos? Es decir, sé que alcanzará el tamaño de 1000, así que en lugar de hacerlo más grande varias veces y hacer copias pesadas, podemos hacerlo de una vez.

davy.ai

June 18, 2023 at 12:01 pm

Si un elemento con la clave A ya está presente en el unordered_map y se inserta otro elemento con la misma clave, anulará el valor anterior asociado con esa clave. Sin embargo, si las claves son diferentes, se agregará el nuevo elemento al mapa.
No, el comportamiento de unordered_map no se puede cambiar para permitir múltiples elementos por índice, ya que el propósito de la estructura de datos es proporcionar complejidad de tiempo constante para búsqueda, inserción y eliminación. Si necesita múltiples elementos por índice, puede considerar el uso de una estructura de datos diferente, como una tabla hash que utiliza encadenamiento.
La tasa de crecimiento de unordered_map depende de la implementación y puede variar entre compiladores. Sin embargo, en general, la complejidad para insertar un elemento en un unordered_map es O (1) amortizado. Esto significa que aunque a veces puede tomar más tiempo que O (1) para insertar un elemento, en promedio, la complejidad es constante.
Puede especificar el tamaño inicial de unordered_map utilizando el constructor que toma un parámetro de capacidad inicial. Por ejemplo, puede crear un unordered_map vacío que puede contener hasta 1000 elementos usando el siguiente código:

std :: unordered_map <int, std="" ::="" string=""> myMap (1000);

Esto asignará memoria para el número especificado de cubos, pero no insertará ningún elemento. Sin embargo, tenga en cuenta que esto no evita que unordered_map crezca más allá de la capacidad inicial si inserta más de 1000 elementos. En ese caso, unordered_map se redimensionará según sea necesario.</int,>

Answer

davy.ai

June 18, 2023 at 12:01 pm
1. Si un elemento con la clave A ya está presente en el unordered_map y se inserta otro elemento con la misma clave, anulará el valor anterior asociado con esa clave. Sin embargo, si las claves son diferentes, se agregará el nuevo elemento al mapa.
2. No, el comportamiento de unordered_map no se puede cambiar para permitir múltiples elementos por índice, ya que el propósito de la estructura de datos es proporcionar complejidad de tiempo constante para búsqueda, inserción y eliminación. Si necesita múltiples elementos por índice, puede considerar el uso de una estructura de datos diferente, como una tabla hash que utiliza encadenamiento.
3. La tasa de crecimiento de unordered_map depende de la implementación y puede variar entre compiladores. Sin embargo, en general, la complejidad para insertar un elemento en un unordered_map es O (1) amortizado. Esto significa que aunque a veces puede tomar más tiempo que O (1) para insertar un elemento, en promedio, la complejidad es constante.
4. Puede especificar el tamaño inicial de unordered_map utilizando el constructor que toma un parámetro de capacidad inicial. Por ejemplo, puede crear un unordered_map vacío que puede contener hasta 1000 elementos usando el siguiente código:
```
std :: unordered_map <int, std="" ::="" string=""> myMap (1000);
```
Esto asignará memoria para el número especificado de cubos, pero no insertará ningún elemento. Sin embargo, tenga en cuenta que esto no evita que unordered_map crezca más allá de la capacidad inicial si inserta más de 1000 elementos. En ese caso, unordered_map se redimensionará según sea necesario.</int,>

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

¿Cómo se comporta std::unordered_map? [C++]

Answer

davy.ai