bucket_count y bucket_size en unordered_map en C++ – Part 1

Unordered_map es un contenedor asociado que almacena elementos formados por la combinación de clave-valor y un valor mapeado. El valor de la clave se utiliza para identificar de forma única el elemento y el valor asignado es el contenido asociado con la clave. Tanto la clave como el valor pueden ser de cualquier tipo predefinido o definido por el usuario. 

Cubo: Internamente, unordered_map se implementa mediante una tabla hash , por lo que un cubo es una ranura en la tabla hash interna a la que se asignan elementos en función del valor hash de su clave. Los cubos están numerados de 0 a (bucket_count-1). Por lo tanto, esta función devuelve el cubo no. donde el elemento con clave se encuentra en unordered_map. 

Complejidad Temporal: O(1).

Sintaxis: 

unordered_map.bucket(k);
// k is the key corresponds to which
// we want to know bucket number.

Valor devuelto: El número de orden del balde correspondiente a la clave k.

Hay dos funciones más con respecto al cubo: 

1. std::bucket_count: esta función se utiliza para contar el número total. de cubos en unordered_map. No se requiere ningún parámetro para pasar a esta función. 

Complejidad Temporal: O(1).

Sintaxis:  

unordered_map.bucket_count();

Valor de retorno: el número del depósito presente en la tabla hash de unordered_map.

2. std::bucket_size: esta función cuenta el número de elementos presentes en cada depósito de unordered_map. 

Complejidad de tiempo: Lineal en el tamaño del cubo.

Sintaxis:  

unordered_map.bucket_size(i); 
// 'i' is the bucket number in which we want 
// to find no. of elements. (i < bucket_count)

Valor de retorno: el número de elementos presentes en el depósito ‘i’.

// C++ program to demonstrate the use of std::bucket
#include <bits/stdc++.h>
using namespace std;
 
// Driver Code
int main()
{
    // Declaring umap to be of <string, double> type
    // key will be of string type and mapped value will
    // be of double type
    unordered_map<string, double> umap;
 
    // inserting values by using [] operator
    umap["PI"] = 3.14;
    umap["root2"] = 1.414;
    umap["log10"] = 2.302;
    umap["loge"] = 1.0;
    umap["e"] = 2.718;
 
    // Display bucket no. where key, value pair is located
    // using bucket(key)
    for (auto& x : umap) {
        cout << "(" << x.first << ", " << x.second << ")";
        cout << " is in bucket= " << umap.bucket(x.first)
             << endl;
    }
    cout << endl;
 
    // Count the no.of buckets in the unordered_map
    // using bucket_count()
    int n = umap.bucket_count();
    cout << "umap has " << n << " buckets.\n\n";
 
    // Count no. of elements in each bucket using
    // bucket_size(position)
    for (int i = 0; i < n; i++) {
        cout << "Bucket " << i << " has "
             << umap.bucket_size(i) << " elements.\n";
    }
 
    return 0;
}

(loge, 1) is in bucket= 5
(e, 2.718) is in bucket= 4
(log10, 2.302) is in bucket= 4
(PI, 3.14) is in bucket= 0
(root2, 1.414) is in bucket= 3

umap has 7 buckets.

Bucket 0 has 1 elements.
Bucket 1 has 0 elements.
Bucket 2 has 0 elements.
Bucket 3 has 1 elements.
Bucket 4 has 2 elements.
Bucket 5 has 1 elements.
Bucket 6 has 0 elements.

También podemos imprimir todos los elementos presentes en cada cubo del unordered_map. 

// C++ program to print all elements present in each bucket
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    // Declaring umap to be of <string, double> type
    // key will be of string type and mapped value
    // will be of double type
    unordered_map<string, double> umap;
 
    // inserting values by using [] operator
    umap["PI"] = 3.14;
    umap["root2"] = 1.414;
    umap["log10"] = 2.302;
    umap["loge"] = 1.0;
    umap["e"] = 2.718;
 
    unsigned n = umap.bucket_count();
 
    // Prints elements present in each bucket
    for (unsigned i = 0; i < n; i++) {
        cout << "Bucket " << i << " contains: ";
        for (auto it = umap.begin(i); it != umap.end(i);
             it++)
            cout << "(" << it->first << ", " << it->second
                 << ") ";
        cout << "\n";
    }
    return 0;
}

Bucket 0 contains: (PI, 3.14) 
Bucket 1 contains: 
Bucket 2 contains: 
Bucket 3 contains: (root2, 1.414) 
Bucket 4 contains: (e, 2.718) (log10, 2.302) 
Bucket 5 contains: (loge, 1) 
Bucket 6 contains: 

Uso de depósito en std::unordered_map: hay una serie de algoritmos que requieren que los objetos se conviertan en una cierta cantidad de depósitos, y luego se procesa cada depósito. Digamos que desea encontrar duplicados en una colección. Hace un hash de todos los elementos de la colección, luego, en cada cubo, compara los elementos por pares. Un ejemplo un poco menos trivial es el algoritmo Apriori para encontrar conjuntos de elementos frecuentes.

Este artículo es una contribución de Akash Gupta . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.