Set vs. Hashset in C++

1. Set vs. Hashset in C++
2. In C++ eingestellt
3. Hashset in C++
4. Hauptunterschiede zwischen einem Set und einem Hashset in C++
5. Fazit

Ein set in C++ fungiert als Container, um Datenelemente zu speichern und bei Bedarf abzurufen. In ähnlicher Weise dient ein Hashset, genauer gesagt unordered_set in C++, einem ähnlichen Zweck wie Sätze zum Speichern von Datenelementen.

In diesem Artikel werden wir ein set und ein unordered_set im Detail besprechen.

Set vs. Hashset in C++

Ein set ist ein assoziativer Container, der zum Speichern von Datenelementen verwendet wird, während ein unordered_set ebenfalls ein assoziativer Container ist, der zum Speichern von Datenelementen für unsere zukünftigen Anforderungen verwendet wird. Wie unterscheiden sich dann diese beiden Datenstrukturen von Vektoren, Karten und anderen Containerobjekten?

Die Antwort ist einfach. Das set und ein unordered_set speichern eindeutige Datenelemente.

Daher lassen sie keine doppelten Elemente zu. Andere Datenstrukturen wie Vektoren und Karten ermöglichen jedoch auch die Speicherung doppelter Elemente.

Diese beiden Datenstrukturen sind in der C++-Standardvorlagenbibliothek vorhanden.

Da wir nun kurz erklären, wann das set und das unordered_set in C++ verwendet werden, wollen wir sie nun im Detail verstehen.

In C++ eingestellt

Wie bereits erwähnt, ist ein set ein assoziativer Container, der eindeutige Datenelemente sortiert speichert. Sie können sie jedoch in beliebiger Reihenfolge speichern, aber sobald Sie sie aus dem set abrufen, werden die Elemente nur sortiert zurückgegeben.

Daher enthält ein set Definitionen zum Sortieren der versteckten Datenelemente des Benutzers.

Die sets in C++ sind als binäre Suchbäume implementiert; daher werden sie bestellt. Außerdem benötigt die Suche nach einem Element O(log n) Zeit.

Sehen wir uns an, wie man ein set in C++ implementiert.

#include <iostream>
#include <set>
using namespace std;

int main() {
  int a[] = {4, 8, 3, 6, 9, 8, 1, 3, 3};
  int size = sizeof(a) / sizeof(a[0]);
  set<int> s;
  for (int i = 0; i < size; i++) {
    s.insert(a[i]);
  }
  set<int>::iterator i;
  for (i = s.begin(); i != s.end(); i++) {
    cout << *i << " ";
  }
}

Ausgabe:

1 3 4 6 8 9

Wie Sie im obigen Codebeispiel sehen können, sind die im Array gespeicherten Elemente daher in zufälliger Reihenfolge und enthalten doppelte Elemente. Sobald sie jedoch in einer Menge s gespeichert werden, werden sie intern sortiert und auch die doppelten Elemente entfernt.

Daher ist die Ausgabe eine sortierte Gruppe von Elementen ohne Duplikate.

Hashset in C++

Das unordered_set oder Hashset in C++ bedeuten beide dasselbe. Dieses unordered_set wird auch verwendet, um eindeutige Datenelemente zu speichern, aber der einzige Unterschied zwischen einem set und einem unordered_set besteht darin, dass ein unordered_set keine Reihenfolge hat, in der die Elemente gespeichert werden, während das set speichert die Elemente in sortierter Reihenfolge.

Dieses unordered_set speichert auch keine doppelten Elemente. Sie werden jedoch mithilfe von Hash-Tabellen implementiert.

Das einzufügende Element, auch Schlüssel genannt, wird in einen Index der Hash-Tabelle gehasht und an diesem bestimmten Index gespeichert.

Da die Elemente in beliebiger Reihenfolge gespeichert werden, dauert das Abrufen von ihnen O(1) Zeit, wodurch die Suchoperation schneller zu implementieren ist.

Nehmen wir ein Beispiel für die Verwendung eines unordered_set in C++.

#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
  int a[] = {4, 8, 3, 6, 9, 8, 1, 3, 3};
  int size = sizeof(a) / sizeof(a[0]);
  unordered_set<int> s;
  for (int i = 0; i < size; i++) {
    s.insert(a[i]);
  }
  unordered_set<int>::iterator i;
  for (i = s.begin(); i != s.end(); i++) {
    cout << *i << " ";
  }
}

Ausgabe:

1 9 6 3 8 4

Wie Sie im obigen Codebeispiel sehen können, werden die Elemente daher in beliebiger Reihenfolge in der Menge gespeichert. Die vom Satz zurückgegebenen Elemente befinden sich jedoch ebenfalls in beliebiger Reihenfolge, es werden jedoch alle doppelten Elemente entfernt und nur die eindeutigen Elemente an den Benutzer zurückgegeben.

Hauptunterschiede zwischen einem Set und einem Hashset in C++

1. Die sets werden verwendet, um die Elemente in aufsteigender Reihenfolge zu speichern, während ein unordered_set die Elemente in keiner Reihenfolge speichert.
2. Die sets werden unter Verwendung der binären Suchbäume implementiert, während ein unordered_set unter Verwendung der Hash-Tabellen implementiert wird.
3. Die Suchoperation in einer Menge benötigt O(log n) Zeit, um ein Element zu suchen, während es O(1) Zeit braucht, um ein Element in einer ungeordneten_Menge zu suchen.
4. Die sets werden in die #include<set>-Header-Datei eingeschlossen, während ein unordered_set unter Verwendung der #include<unordered_set>-Header-Datei eingeschlossen wird.

Fazit

In diesem Artikel haben wir ein set und ein hashset in C++ besprochen. Diese beiden Datenstrukturen sind in der C++-STL vorhanden und werden verwendet, um eindeutige Datenelemente zu speichern.

Der Hauptunterschied zwischen den beiden besteht jedoch darin, dass ein set eine sortierte Menge von Elementen zurückgibt, während ein unordered_set die Datenelemente in keiner Reihenfolge zurückgibt.

Sie können jede der beiden verwenden, aber die Suchoperation ist in einem unordered_set schneller und benötigt fast konstant Zeit, um ein Element zu suchen; daher wird es bevorzugt.