Conjuntos desordenados en la biblioteca de plantillas estándar de C++ – Part 1

Un conjunto_desordenado se implementa mediante una tabla hash en la que las claves se convierten en índices de una tabla hash para que la inserción siempre sea aleatoria. Todas las operaciones en unordered_set toman un tiempo constante O (1) en un promedio que puede llegar al tiempo lineal O (n) en el peor de los casos, que depende de la función hash utilizada internamente, pero en la práctica funcionan muy bien y generalmente proporcionan un tiempo constante operación de búsqueda. 
Unordered_set puede contener claves de cualquier tipo: estructura de datos predefinida o definida por el usuario, pero cuando definimos la clave de tipo, el usuario define el tipo, debemos especificar nuestra función de comparación según las claves que se compararán.

// C++ program to demonstrate various function of unordered_set
#include <bits/stdc++.h>
using namespace std;
  
int main()
{
    // declaring set for storing string data-type
    unordered_set <string> stringSet ;
  
    // inserting various string, same string will be stored
    // once in set
  
    stringSet.insert("code") ;
    stringSet.insert("in") ;
    stringSet.insert("c++") ;
    stringSet.insert("is") ;
    stringSet.insert("fast") ;
  
    string key = "slow" ;
  
    //  find returns end iterator if key is not found,
    //  else it returns iterator to that key
  
    if (stringSet.find(key) == stringSet.end())
        cout << key << " not found" << endl << endl ;
    else
        cout << "Found " << key << endl << endl ;
  
    key = "c++";
    if (stringSet.find(key) == stringSet.end())
        cout << key << " not found\n" ;
    else
        cout << "Found " << key << endl ;
  
    // now iterating over whole set and printing its
    // content
    cout << "\nAll elements : ";
    unordered_set<string> :: iterator itr;
    for (itr = stringSet.begin(); itr != stringSet.end(); itr++)
        cout << (*itr) << endl;
}

// C++ program to find duplicate from an array using
// unordered_set
#include <bits/stdc++.h>
using namespace std;
  
// Print duplicates in arr[0..n-1] using unordered_set
void printDuplicates(int arr[], int n)
{
    // declaring unordered sets for checking and storing
    // duplicates
    unordered_set<int> intSet;
    unordered_set<int> duplicate;
  
    // looping through array elements
    for (int i = 0; i < n; i++)
    {
        // if element is not there then insert that
        if (intSet.find(arr[i]) == intSet.end())
            intSet.insert(arr[i]);
  
        // if element is already there then insert into
        // duplicate set
        else
            duplicate.insert(arr[i]);
    }
  
    // printing the result
    cout << "Duplicate item are : ";
    unordered_set<int> :: iterator itr;
  
    // iterator itr loops from begin() till end()
    for (itr = duplicate.begin(); itr != duplicate.end(); itr++)
        cout << *itr << " ";
}
  
// Driver code
int main()
{
    int arr[] = {1, 5, 2, 1, 4, 3, 1, 7, 2, 8, 9, 5};
    int n = sizeof(arr) / sizeof(int);
  
    printDuplicates(arr, n);
    return 0;
}