Ungeordnet ist manchmal besser

Manchmal kann es günstig sein, wenn nicht alles strikt sortiert ist. Diese Eigenschaft nutzt std::unordered_set aus, um einen Zugriff auf Elemente in O(1) zu ermöglichen.

Video

Quelltext

#include <iostream>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <iterator>

int main()
{
  std::set<int> s;
  std::unordered_set<int> us;

  for (int i = 0; i < 30; ++i) {
    s.insert(i);
    us.insert(i);
  }

  std::copy(s.begin(), s.end(), std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
  std::copy(us.begin(), us.end(), std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
}

Erklärung

std::set und std::unordered_set sind im Prinzip gleich verwendbar: sie speichern einmalige Elemente und bieten einen (verhältnismäßig) schnellen Zugriff darauf. Der Unterschied: in std::set liegen die Elemente sortiert vor, damit ein Zugriff in O(log n) realisiert werden kann. std::unordered_set berechnet die Elementpositionen anhand eines Hash-Verfahrens und realisiert damit den Zugriff in O(1). Der Unterschied ist für größere Mengen an Elementen durchaus bemerkenswert:

Das (orange dargestellte) std::unordered_set verlangsamt seine Performance beim Auffinden von Elementen kaum mit steigender Elementzahl im Container. std::set hingegen zeigt die wohlbekannte logarithmische Kurve, die charakteristisch für das verlangte O(log n) ist. Bei 500000 Elementen macht das schon einen Faktor > 5 aus. Allerdings ist dafür ein Preis zu zahlen: typischerweise wird ein std::unordered_set mehr Platz brauchen, da die zugrundeliegenden Hashtabellen nur dann gut funktionieren, wenn sie verhältnismäßig leer sind. Wenn der Preis für den Anwendungsfall kein Problem darstellt, dann hat man mit dieser Datenstruktur etwas, dass sich von großen Elementzahlen nicht beeindrucken lässt und immer ein recht konstantes Verhalten zeigt.