Wann verwenden Sie std :: unordered_map :: emplace_hint?

Question

Ich weiß, wie man std::unordered_map::emplace verwendet, aber wie verwende ich emplace_hint? Weder cplusplus noch enthalten eine Reihe von Beispielen, die veranschaulichen, woher wir wissen, wo wir das Element platzieren können.

Kann jemand einige Informationen dazu liefern oder einige Beispiele/Illustrationen geben, wann wir wissen könnten, wohin das eingelagerte Element gehen sollte?

Answer 1

Was könnte ein unordered_map möglicherweise mit dem Hinweis tun? Nun, wenn der Iterator ein Element mit dem gleichen Schlüssel wie das Element anspricht, das emplace_hint wurde eingefügt werden soll, dann kann es schnell scheitern - nur ein Schlüsselvergleich ohne Hashing oder tappen durch eine Liste von Hash-kollidierenden Elementen in diesem Bucket. Aber wenn der Schlüssel nicht übereinstimmt, dann ist der Hinweis ansonsten nutzlos, weil jeder andere Schlüssel (egal wie "nah" im Wert) (probabilistisch) in einem völlig unabhängigen Bucket sein sollte (angesichts dessen, was normalerweise eine "gute" Hash-Funktion ist)), so wäre die Zeit für einen Schlüsselvergleich verschwendet worden, nur um von vorne anfangen zu müssen, als ob es ein normaler emplace wäre.

Dies kann nützlich sein, wenn Sie Elemente vorsortiert nach Schlüssel einfügen, mit dem Ziel, viele Duplikate im Prozess zu entfernen, aber der Schlüssel ist so groß, dass es einfacher ist, einen Iterator für das gerade eingefügte Element beizubehalten als eine Kopie des Schlüssels, oder vielleicht ist die Hash-Funktion besonders langsam.

Ein weiterer Vorteil der unordered_map::emplace_hint ist besser API-Kompatibilität mit map::emplace_hint, so kann Code schalten Sie den Typ Container und haben die emplace_hint s die Kompilierung nicht brechen, obwohl sie als am Ende vielleicht langsamer, wenn der Code auf emplace() als nah- geschaltet wurden but-different-key Hinweise, die mit einem map helfen, können mit einem unordered_map nutzlos sein.