Requisito previo : std::mapa , std::mapa_desordenado
Cuando se trata de eficiencia, existe una gran diferencia entre mapas y mapas desordenados.
Debemos conocer el funcionamiento interno de ambos para decidir cuál utilizar.
Diferencia :
| map | unordered_map --------------------------------------------------------- Ordering | increasing order | no ordering | of keys(by default) | Implementation | Self balancing BST | Hash Table | like Red-Black Tree | search time | log(n) | O(1) ->Promedio | | O(n) -> Tiempo de inserción en el peor de los casos | log(n) + Reequilibrio | Igual que la búsqueda Hora de eliminación | log(n) + Reequilibrio | Igual que buscar>
Utilice std::map cuando
- Necesitas datos ordenados.
- Tendría que imprimir/acceder a los datos (en orden).
- Necesita predecesor/sucesor de elementos.
- Consulte las ventajas de BST sobre Hash Tabl e para conocer más casos.
CPP
cómo determinar el tamaño del monitor
lista de arreglo
// CPP program to demonstrate use of std::map> #include> int> main()> {> >// Ordered map> >std::map<>int>,>int>>orden;> >// Mapping values to keys> >order[5] = 10;> >order[3] = 500;> >order[20] = 100;> >order[1] = 1;> >// Iterating the map and> >// printing ordered values> >for> (>auto> i = order.begin(); i> >!= order.end(); i++) {> >std::cout << ' : ' '
'; } }> |
>
>Producción
1 : 1 3 : 500 5 : 10 20 : 100>
Utilice std::unordered_map cuando
- Debe llevar la cuenta de algunos datos (Ejemplo: cadenas) y no es necesario realizar ningún pedido.
- Necesita acceso a un solo elemento, es decir, sin recorrido.
CPP
mapa hash
gigabyte vs megabyte
// CPP program to demonstrate use of> // std::unordered_map> #include> int> main()> {> >// Unordered map> >std::unordered_map<>int>,>int>>orden;> >// Mapping values to keys> >order[5] = 10;> >order[3] = 500;> >order[20] = 100;> >order[1] = 1;> >// Iterating the map and> >// printing unordered values> >for> (>auto> i = order.begin();> >i != order.end(); i++)> >{> >std::cout << ' : ' '
'; } }> |
>
>Producción
1 : 1 20 : 100 3 : 500 5 : 10>
Veamos las diferencias en forma de tabla:
| mapa | mapa_desordenado | |
| 1. | el mapa se define en el archivo de encabezado #include | unordered_map está definido en el archivo de encabezado #include |
| 2. | Es implementado por árbol rojo-negro . | Se implementa mediante una tabla hash. |
| 3. | Es lento. | Es rápido. |
| 4. | Complejidad del tiempo para operaciones es O(log N) | La complejidad del tiempo para las operaciones es O(1) |
| 5. | El mapa se utiliza para almacenar elementos como pares clave y valor en orden ordenados por clave. | unordered_map se utiliza para almacenar elementos como pares clave-valor en orden no ordenado. |