Programa para implementar Enstringmiento Separado en C++ STL sin el uso de punteros

Requisito previo: Enstringmiento separado , STL en C++

Este artículo implementa el enstringmiento separado en hashing con la ayuda de STL en C++ sin el uso de punteros .

Enfoque: Cree una array de vectores para obtener una array dinámica (redimensionable) para cada índice hash en lugar de usar una lista vinculada para hacer lo mismo . Ahora es más fácil trabajar en el conjunto de datos sin usar la lista enlazada. Este simple truco es mucho más fácil de implementar y es más eficiente. En este enfoque:

1. El constructor de la clase inicializa el tamaño del Hash.
2. Los elementos se insertan en el Hash según la expresión:

   Vector[i % n].push_back(i);
   where:
       Vector = the array of vectors used for hash
       i = current element to be hashed
       n = size of the hash
   

   

   Enstringmiento separado usando STL

   Algoritmo: El algoritmo para el enfoque se menciona a continuación:

   1. Inicialice el tamaño (digamos n ) de los vectores.
   2. Al agregar un elemento, realice los siguientes pasos:
      1. Obtenga el valor de x=”[valor] MOD n “.
      2. Retrasa el valor de este elemento en v[x].
   3. Para la Eliminación, seguimos estos pasos:
      1. Obtenga el valor de x=”[valor] MOD n “.
      2. Busque el elemento que se eliminará en v[x].
      3. Si lo encuentra, elimine el elemento usando el método erase() .
      4. Si no se encuentra el elemento a eliminar, imprima «¡Elemento no encontrado!»
   4. Imprime el hash.

   Implementación

   // C++ Program to implement Separate // Chaining in C++ STL without // the use of pointers    #include <bits/stdc++.h> using namespace std;    // Container for our data-set class SeperateHash {        // Data members are kept private     // since they are accessed using methods private:     int n;     vector<vector<int> > v;        // Methods are kept public public:     // Initialising constructors as the     // minimum required memory will be     // allocated after which compiler     // will not report flag error     SeperateHash(int n)     {         // Constructor to initialize         // the vector of vectors         v = vector<vector<int> >(n);            // Here, we will allocate         // memory of the unnamed_memory         // to the object. This snippet         // of code won't work for now.         // Program will work whenever         // constructor gets initialized         this->n = n;     }        int getHashIndex(int x)     {         return x % n;     }        void add(int x)     {         // Adding the element according         // to hash index         v[getHashIndex(x)].push_back(x);     }        void del(int x)     {         int i = getHashIndex(x);            // Scan for the element to be removed         for (int j = 0; j < v[i].size(); j++) {                // Erase if present otherwise             // print no element found!             if (v[i][j] == x) {                 v[i].erase(v[i].begin() + j);                 cout << x << " deleted!" << endl;                 return;             }         }            cout << "No Element Found!" << endl;     }     void displayHash()     {         // Display the contents         for (int i = 0; i < v.size(); i++) {             cout << i;             for (int j = 0; j < v[i].size(); j++)                 cout << " -> " << v[i][j];             cout << endl;         }     } };    // Driver Code int main() {     // Array to be used     int arr[] = { 12, 3, 23, 4, 11,                   32, 26, 33, 17, 19 };        // Sending the size     // for separate chaining     SeperateHash obj(10);        // Inserting elements in     // the container accordingly     for (int i = 0; i < 10; i++)         obj.add(arr[i]);        // Display the initial hash     cout << "Initial Hash:\n";     obj.displayHash();        // Removing the element     // from the container     cout << "\nRemoving 23 from Hash: ";     obj.del(23);     cout << endl;        // Display the final hash     cout << "Final Hash:\n";     obj.displayHash();     return 0; }

   Producción:

   Initial Hash:
   0
   1 -> 11
   2 -> 12 -> 32
   3 -> 3 -> 23 -> 33
   4 -> 4
   5
   6 -> 26
   7 -> 17
   8
   9 -> 19
   
   Removing 23 from Hash: 23 deleted!
   
   Final Hash:
   0
   1 -> 11
   2 -> 12 -> 32
   3 -> 3 -> 33
   4 -> 4
   5
   6 -> 26
   7 -> 17
   8
   9 -> 19
   

   Ventajas de usar este enfoque:

   1. No necesitamos iterar a través de las entradas como lo necesitamos con las listas enlazadas.
   2. Depuración más fácil del código.
   3. Más fácil de implementar ya que el enfoque convencional tiene posibilidades de marcar la falla de segmentación con errores lógicos menores.
   4. Poder de aplicar métodos STL sobre los datos que proporciona una ventaja en la programación competitiva.