Wie erreicht „std::unordered_map' eine hohe Leistung und behält gleichzeitig die Iteratorgültigkeit bei?

std::unordered_map-Implementierung: Ein genauerer Blick

Der std::unordered_map-Container in C hat Diskussionen über seine Implementierung und Effizienz ausgelöst. Um Licht in dieses Thema zu bringen, untersuchen wir, wie diese Datenstruktur realisiert wird.

Separate Verkettung mit verknüpften Listen

Im Kern verwendet unordered_map eine Technik namens separate Verkettung , auch als offenes Hashing bekannt. Dazu gehört die Verwaltung eines Arrays von Buckets, wobei jeder Bucket eine verknüpfte Liste von Elementen mit kollidierenden Hash-Schlüsseln enthält. Diese Designwahl ergibt sich aus der Anforderung im C-Standard, dass Iteratoren zu Elementen auch dann gültig bleiben, wenn andere Elemente eingefügt oder gelöscht werden.

Größenänderung und erneutes Aufwärmen

Zur Aufrechterhaltung der Leistung , unordered_map verwendet Größenänderung und erneutes Aufwärmen. Eine Größenänderung erfolgt, wenn die Anzahl der Elemente die aktuelle Bucket-Anzahl multipliziert mit dem maximalen Lastfaktor überschreitet, der standardmäßig 1,0 beträgt. Beim erneuten Aufwärmen wird eine neue Reihe von Buckets mit einer größeren Kapazität erstellt, und alle vorhandenen Elemente werden erneut aufbereitet und in den entsprechenden Buckets platziert.

Einschränkungen

Bei separater Verkettung Obwohl es für allgemeine Anwendungen effektiv ist, gibt es Einschränkungen. In bestimmten Szenarien kann geschlossenes Hashing (offene Adressierung) erhebliche Leistungsvorteile in Bezug auf Geschwindigkeit und Speichernutzung bieten. Die offene Adressierung führt jedoch zu Komplexitäten, wie z. B. der Unterscheidung zwischen freien und besetzten Positionen und der Handhabung der Kollisionsauflösung.

Die „Aufsicht“ im Standard

Die Anforderung, den Iterator beizubehalten Die Gültigkeit wurde von einigen Kritikern als „Versehen“ bezeichnet. Es war jedoch eine bewusste Entscheidung des C-Komitees, der Iteratorstabilität Priorität einzuräumen. Diese Wahl gewährleistet, dass unordered_map in Situationen verwendet werden kann, in denen Iteratoren und Referenzen während Einfüge- und Löschvorgängen intakt bleiben müssen.

Fazit

Die Implementierung von std::unordered_map bringt Allgemeingültigkeit, Leistung und Einhaltung des C-Standards in Einklang. Die separate Verkettung mit verknüpften Listen stellt die Gültigkeit des Iterators sicher, während Größenänderung und erneutes Aufwärmen die Leistung optimieren. Trotz möglicher Einschränkungen in bestimmten Szenarien bleibt unordered_map eine vielseitige und weit verbreitete Datenstruktur für die Verarbeitung hashbasierter Einfügungen und Suchvorgänge.

Das obige ist der detaillierte Inhalt vonWie erreicht „std::unordered_map' eine hohe Leistung und behält gleichzeitig die Iteratorgültigkeit bei?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!