unordered_multiset y sus usos

Hemos discutido sobre unordered_set en nuestra publicación anterior, el problema con unordered_set es que no es posible almacenar entradas duplicadas en esa estructura de datos. Por ejemplo, si ya tenemos algún valor v en unordered_set, insertar v nuevamente no tendrá ningún efecto. 
Para manejar esta duplicación, se debe usar unordered_multiset, también puede almacenar elementos duplicados. Internamente, cuando se inserta un valor existente, la estructura de datos aumenta su recuento asociado con cada valor. Como el recuento de cada valor se almacena en unordered_multiset, ocupa más espacio que unordered_set (si todos los valores son distintos). 
La implementación interna de unordered_multiset es la misma que la de unordered_set y también usa una tabla hash para buscar, solo el valor de conteo está asociado con cada valor en el anterior. Debido al hash de los elementos, no tiene un orden particular de almacenamiento de los elementos, por lo que todos los elementos pueden venir en cualquier orden, pero los elementos duplicados se juntan. Todas las operaciones en unordered_multiset toman un tiempo constante en promedio, pero pueden llegar a ser lineales en el peor de los casos. 
Unordered_multiset admite muchas funciones que se muestran en el siguiente código: 
 

// C++ program to demonstrate various function
// of unordered_multiset
#include <bits/stdc++.h>
using namespace std;
 
// making typedef for short declaration
typedef unordered_multiset<int>::iterator umit;
 
// Utility function to print unordered_multiset
void printUset(unordered_multiset<int> ums)
{
    //  begin() returns iterator to first element of set
    umit it = ums.begin();
    for (; it != ums.end(); it++)
        cout << *it << " ";
    cout << endl;
}
 
//  Driver program to check all function
int main()
{
    //  empty initialization
    unordered_multiset<int> ums1;
 
    //  Initialization by intializer list
    unordered_multiset<int> ums2 ({1, 3, 1, 7, 2, 3,
                                   4, 1, 6});
 
    //  Initialization by assignment
    ums1 = {2, 7, 2, 5, 0, 3, 7, 5};
 
    //  empty() function return true if set is empty
    // otherwise false
    if (ums1.empty())
        cout << "unordered multiset 1 is empty\n";
    else
        cout << "unordered multiset 1 is not empty\n";
 
    //  size() function returns total number of elements
    // in data structure
    cout << "The size of unordered multiset 2 is : "
         << ums2.size() << endl;
 
    printUset(ums1);
 
    ums1.insert(7);
 
    printUset(ums1);
 
    int val = 3;
 
    // find function returns iterator to first position
    // of  val, if exist otherwise it returns iterator
    // to end
    if (ums1.find(val) != ums1.end())
        cout << "unordered multiset 1 contains "
             << val << endl;
    else
        cout << "unordered multiset 1 does not contains "
             << val << endl;
 
    //  count function returns total number of occurrence in set
    val = 5;
    int cnt = ums1.count(val);
    cout << val << " appears " << cnt
         << " times in unordered multiset 1 \n";
 
    val = 9;
 
    //  if count return >0 value then element exist otherwise not
    if (ums1.count(val))
        cout << "unordered multiset 1 contains "
             << val << endl;
    else
        cout << "unordered multiset 1 does not contains "
             << val << endl;
 
    val = 1;
 
    // equal_range returns a pair, where first is iterator
    // to first position of val and second it iterator to
    // last position to val
    pair<umit, umit> erange_it = ums2.equal_range(val);
    if (erange_it.first != erange_it.second)
        cout << val << " appeared atleast once in "
                        "unoredered_multiset \n";
 
 
    printUset(ums2);
 
    // erase function deletes all instances of val
    ums2.erase(val);
 
    printUset(ums2);
 
    // clear function deletes all entries from set
    ums1.clear();
    ums2.clear();
 
    if (ums1.empty())
        cout << "unordered multiset 1 is empty\n";
    else
        cout << "unordered multiset 1 is not empty\n";
}

Producción : 

unordered multiset 1 is not empty
The size of unordered multiset 2 is : 9
3 0 5 5 7 7 2 2 
3 0 5 5 7 7 7 2 2 
unordered multiset 1 contains 3
5 appears 2 times in unordered multiset 1 
unordered multiset 1 does not contains 9
1 appeared atleast once in unoredered_multiset 
6 4 2 7 3 3 1 1 1 
6 4 2 7 3 3 
unordered multiset 1 is empty

Como podemos ver, la mayor parte de la operación funciona de manera similar a la de unordered_set, pero algunas cosas a tener en cuenta son: 
la función equal_range (val) devuelve un par de tipos donde el primer iterador apunta a la primera posición de val y el segundo apunta a la última posición de val en datos estructura. 
La función erase (val) elimina todas sus instancias de la estructura de datos, por ejemplo, si algún valor v ha ocurrido t veces en unordered_multiset y cuando se llama a erase, v se elimina por completo, lo que no es un comportamiento esperado muchas veces.
Podemos eliminar solo una copia de algún valor usando la función de búsqueda y la versión de borrado del iterador, ya que la función de búsqueda devuelve el iterador a la primera posición del valor encontrado, podemos pasar este iterador para borrar en lugar del valor real para eliminar solo una copia, el código para hacer esto se muestra a continuación: 
 

//  C++ program to delete one copy from unordered set
#include <bits/stdc++.h>
using namespace std;
 
//  making typedef for short declaration
typedef unordered_multiset<int>::iterator umit;
 
//  Utility function to print unordered_multiset
void printUset(unordered_multiset<int> ums)
{
    // begin() returns iterator to first element of
    // set
    umit it = ums.begin();
    for (; it != ums.end(); it++)
        cout << *it << " ";
    cout << endl;
}
 
//  function to delete one copy of val from set
void erase_one_entry(unordered_multiset<int>& ums,
                    int val)
{
    //  find returns iterator to first position
    umit it = ums.find(val);
 
    //  if element is there then erasing that
    if (it != ums.end())
       ums.erase(it);
}
 
//  Driver program to check above function
int main()
{
    //  initializing multiset by initializer list
    unordered_multiset<int> ums ({1, 3, 1, 7, 2, 3,
                                 4, 1, 6});
 
    int val = 1;
    printUset(ums);
    erase_one_entry(ums, val);
    printUset(ums);
}

Producción :

6 4 2 7 3 3 1 1 1 
6 4 2 7 3 3 1 1 

Métodos de unordered_multiset: 
 

• insert() : inserta nuevos elementos en unordered_multiset. Por lo tanto, aumenta el tamaño del contenedor.
• begin() : devuelve un iterador que apunta al primer elemento del contenedor o al primer elemento de uno de sus cubos.
• end() : devuelve un iterador que apunta a la posición inmediatamente después del último elemento en el contenedor o a la posición inmediatamente después del último elemento en uno de sus cubos.
• vacío() : devuelve verdadero si el contenedor unordered_multiset está vacío. De lo contrario, devuelve falso.
• find() : devuelve un iterador que apunta a la posición que tiene el elemento val.
• cbegin() : devuelve un iterador constante que apunta al primer elemento del contenedor o al primer elemento de uno de sus cubos.
• cend() : devuelve un iterador constante que apunta a la posición inmediatamente después del último elemento en el contenedor o a la posición inmediatamente después del último elemento en uno de sus cubos.
• equal_range() : devuelve el rango en el que todos los elementos son iguales a un valor dado.
• emplace() : inserta un nuevo elemento en el contenedor unordered_multiset.
• clear() : borra el contenido del contenedor unordered_multiset.
• count() : devuelve el recuento de elementos en el contenedor unordered_multiset que es igual a un valor dado.
• size() : el método size() de unordered_multiset se utiliza para contar el número de elementos de unordered_set con los que se llama.
• max_size : max_size() de unordered_multiset toma la cantidad máxima de elementos que el contenedor unordered_multiset puede contener.
• swap() : intercambia el contenido de dos contenedores unordered_multiset.
• erase() : se utiliza para eliminar un solo elemento o todos los elementos con un valor definido o un rango de elementos que van desde el inicio (incluido) hasta el final (exclusivo).
• cubo() – Devuelve el número de cubo en el que se encuentra un elemento dado. El tamaño del depósito varía de 0 a bucket_count-1.
• bucket_size() : devuelve el número de elementos en el depósito que tiene el elemento val.
• reserve() : la función reverse() de unordered_multiset establece el número de cubos en el contenedor (bucket_count) en el más apropiado para contener al menos n elementos.
• max_bucket_count() : devuelve el número máximo de cubos que puede tener el contenedor de conjuntos múltiples sin ordenar.
• load_factor() : devuelve el factor de carga actual en el contenedor unordered_multiset.
• max_load_factor() : devuelve el factor de carga máximo del contenedor unordered_multiset.
• bucket_count() : devuelve el número total de cubos en el contenedor unordered_multiset.
• hash_function() : esta función hash es una función unaria que toma un solo argumento y devuelve un valor único de tipo size_t basado en él.
• rehash() : establece el número de cubos en el contenedor en N o más.
• key_eq() – Devuelve un valor booleano según la comparación.
• emplace_hint() : inserta un nuevo elemento en el contenedor unordered_multiset.
• get_allocator : esta función obtiene el objeto asignador almacenado y devuelve el objeto asignador que se utiliza para construir el contenedor.
• operator = – El ‘=’ es un operador en C++ STL que copia (o mueve) un conjunto múltiple sin ordenar a otro conjunto múltiple sin ordenar y un conjunto múltiple sin ordenar::operator= es la función de operador correspondiente.

Artículos recientes sobre unordered_multiset
Este artículo es una contribución de Utkarsh Trivedi. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.