Was nutzt emplace_hint in der Karte?

Angenommen, Sie möchten ein Element nur dann in eine Map einfügen, wenn der Schlüssel noch nicht vorhanden ist. Sie könnten natürlich auch insert aufrufen, nehmen aber weiter an, dass die Operation teuer oder irreversibel ist (z. B. von einem nicht kopierbaren Objekt aus).

In diesem Fall müssen Sie die Suche von der Einfügung trennen. Hier kommt der Hinweis in Verbindung mit lower_bound :

Der Trick ist, dass lower_bound den Iterator zurückgibt, wo der Schlüssel wäre wäre, wenn er in der Map wäre, unabhängig davon, ob er tatsächlich dort ist. Die Zeitkomplexität der angedeuteten Einfügung ist konstant, wenn der Hinweis korrekt ist.

Es hat keinen Sinn, die angedeutete Einfügung mit einem falschen Iterator zu verwenden (d. h. einer, der nicht als Untergrenze für den gegebenen Schlüssel erhalten wurde).

Beachten Sie, dass eine angedeutete Einfügung nur für bestellte assoziative Container funktioniert. Die ungeordneten Container bieten auch diese Überladungen, aber sie haben keine Wirkung, da es keinen Weg gibt, einen brauchbaren Hinweis für ungeordnete Container zu erhalten.

  

Ich verstehe, dass map :: emplace_hint verwendet wird, um ein Schlüssel / Wert-Paar an einer bestimmten Stelle in der Karte zu platzieren.

Nein, ist es nicht.

Wie Sie sagen, können Sie die Position der Elemente nicht selbst steuern. Die Karte entscheidet das.

Dieser Hinweis soll dem Compiler sagen, wo Sie denken die Karte wird sich entscheiden, es zu setzen, so dass die Karte nicht ganz so lange damit verbringen muss, das herauszufinden.

Wenn Sie beispielsweise bereits wissen (weil es Ihr Programm ist!), dass ein neues Element definitiv beim "Start" der Karte endet, können Sie dieses Wissen an den Container weitergeben. Es muss dann nur überprüft werden, dass Sie Recht haben, anstatt den gesamten Baum zu durchsuchen, um schließlich selbst zu dieser Schlussfolgerung zu kommen.

Wenn Ihr Hinweis falsch ist, ändert das nichts daran, wo das Element landet, aber Sie geben der Karte mehr Arbeit.