std::unordered_set<Key,Hash,KeyEqual,Allocator>::emplace_hint
| template< class... Args > iterator emplace_hint( const_iterator hint, Args&&... args ); |
(seit C++11) | |
Fügt ein neues Element in den Container ein und verwendet hint als Vorschlag, wo das Element platziert werden soll.
Die Konstruktoren des Schlüssels und des Wertes werden mit exakt denselben Argumenten aufgerufen, die an die Funktion übergeben wurden, weitergeleitet mit std::forward<Args>(args)....
Wenn nach der Operation die neue Anzahl von Elementen größer ist als max_load_factor() * bucket_count(), findet ein Rehashing statt.
Wenn Rehashing stattfindet (aufgrund der Einfügung), werden alle Iteratoren ungültig. Andernfalls (kein Rehashing) werden Iteratoren nicht ungültig.
Inhalt |
[bearbeiten] Parameter
| hint | - | iterator, der als Vorschlag dient, wo das neue Element eingefügt werden soll |
| args | - | Argumente, die an den Konstruktor des Elements weitergeleitet werden |
[bearbeiten] Rückgabewert
Ein Iterator zu dem eingefügten Element oder zu dem Element, das die Einfügung verhindert hat.
[bearbeiten] Ausnahmen
Wenn aus irgendeinem Grund eine Ausnahme ausgelöst wird, hat diese Funktion keine Auswirkungen (starkes Ausnahmesicherheitsgarantie).
[bearbeiten] Komplexität
Im Durchschnitt amortisiert konstant, im schlimmsten Fall linear zur Größe des Containers.
[bearbeiten] Beispiel
#include <chrono> #include <cstddef> #include <functional> #include <iomanip> #include <iostream> #include <unordered_set> const int n_operations = 100'500'0; std::size_t set_emplace() { std::unordered_set<int> set; for (int i = 0; i < n_operations; ++i) set.emplace(i); return set.size(); } std::size_t set_emplace_hint() { std::unordered_set<int> set; auto it = set.begin(); for (int i = 0; i < n_operations; ++i) { set.emplace_hint(it, i); it = set.end(); } return set.size(); } std::size_t set_emplace_hint_wrong() { std::unordered_set<int> set; auto it = set.begin(); for (int i = n_operations; i > 0; --i) { set.emplace_hint(it, i); it = set.end(); } return set.size(); } std::size_t set_emplace_hint_corrected() { std::unordered_set<int> set; auto it = set.begin(); for (int i = n_operations; i > 0; --i) { set.emplace_hint(it, i); it = set.begin(); } return set.size(); } std::size_t set_emplace_hint_closest() { std::unordered_set<int> set; auto it = set.begin(); for (int i = 0; i < n_operations; ++i) it = set.emplace_hint(it, i); return set.size(); } double time_it(std::function<std::size_t()> set_test, const char* what = nullptr, double ratio = 0.0) { const auto start = std::chrono::system_clock::now(); const std::size_t setsize = set_test(); const auto stop = std::chrono::system_clock::now(); const std::chrono::duration<double, std::milli> time = stop - start; if (what != nullptr && setsize > 0) std::cout << std::setw(8) << time << " for " << what << " (ratio: " << (ratio == 0.0 ? 1.0 : ratio / time.count()) << ")\n"; return time.count(); } int main() { std::cout << std::fixed << std::setprecision(2); time_it(set_emplace); // cache warmup const auto x = time_it(set_emplace, "plain emplace"); time_it(set_emplace_hint, "emplace with correct hint", x); time_it(set_emplace_hint_wrong, "emplace with wrong hint", x); time_it(set_emplace_hint_corrected, "corrected emplace", x); time_it(set_emplace_hint_closest, "emplace using returned iterator", x); }
Mögliche Ausgabe
146.88ms for plain emplace (ratio: 1.00) 168.20ms for emplace with correct hint (ratio: 0.87) 168.78ms for emplace with wrong hint (ratio: 0.87) 166.58ms for corrected emplace (ratio: 0.88) 168.27ms for emplace using returned iterator (ratio: 0.87)
[bearbeiten] Siehe auch
| konstruiert Elemente direkt (in-place) (public member function) | |
| fügt Elemente ein oder Knoten(seit C++17) (public member function) |
