Namensräume
Varianten
Aktionen

std::unordered_set<Key,Hash,KeyEqual,Allocator>::insert

Von cppreference.com
 
C++
 
Container-Bibliothek
 
std::unordered_set
Membertypen
Memberfunktionen
Nicht-Member-Funktionen
Abzugsleitfäden (C++17)
 
std::pair<iterator,bool> insert( const value_type& value );
 (1) (seit C++11)
std::pair<iterator,bool> insert( value_type&& value );
 (2) (seit C++11)
iterator insert( const_iterator hint, const value_type& value );
 (3) (seit C++11)
iterator insert( const_iterator hint, value_type&& value );
 (4) (seit C++11)
template< class InputIt >
void einfügen( InputIt first, InputIt last );
 (5) (seit C++11)
void insert( std::initializer_list<value_type> ilist );
 (6) (seit C++11)
insert_return_type insert( node_type&& nh );
 (7) (seit C++17)
iterator insert( const_iterator hint, node_type&& nh );
 (8) (seit C++17)
template< class K >
std::pair<iterator, bool> insert( K&& obj );
 (9) (seit C++23)
template< class K >
iterator insert( const_iterator hint, K&& obj );
 (10) (seit C++23)

Fügt Element(e) in den Container ein, falls der Container noch kein Element mit einem äquivalenten Schlüssel enthält.

1,2) Fügt value ein.
3,4) Fügt value ein, wobei hint als unverbindlicher Vorschlag verwendet wird, wo die Suche beginnen soll.
5) Fügt Elemente aus dem Bereich [first, last) ein. Wenn mehrere Elemente im Bereich Schlüssel haben, die als äquivalent verglichen werden, ist nicht spezifiziert, welches Element eingefügt wird (abhängig von LWG2844).
6) Fügt Elemente aus der Initialisierungsliste ilist ein. Wenn mehrere Elemente im Bereich Schlüssel haben, die als äquivalent verglichen werden, ist nicht spezifiziert, welches Element eingefügt wird (abhängig von LWG2844).
7) Wenn nh ein leerer node handle ist, tut dies nichts. Andernfalls wird das von nh besessene Element in den Container eingefügt, wenn der Container nicht bereits ein Element mit einem Schlüssel enthält, der zu nh.key() äquivalent ist. Das Verhalten ist undefiniert, wenn nh nicht leer ist und get_allocator() != nh.get_allocator().
8) Wenn nh ein leerer node handle ist, tut dies nichts und gibt den End-Iterator zurück. Andernfalls wird das von nh besessene Element in den Container eingefügt, wenn der Container nicht bereits ein Element mit einem Schlüssel enthält, der zu nh.key() äquivalent ist, und gibt den Iterator zurück, der auf das Element mit einem Schlüssel zeigt, der zu nh.key() äquivalent ist (unabhängig davon, ob die Einfügung erfolgreich war oder fehlschlug). Wenn die Einfügung erfolgreich ist, wird nh verschoben, andernfalls behält es den Besitz des Elements. hint wird als unverbindlicher Vorschlag verwendet, wo die Suche beginnen soll. Das Verhalten ist undefiniert, wenn nh nicht leer ist und get_allocator() != nh.get_allocator().
9) Wenn *this bereits ein Element enthält, das transparent äquivalent zu obj ist, tut dies nichts. Andernfalls wird ein Objekt u vom value_type mit std::forward<K>(obj) konstruiert und dann u in *this eingefügt. Wenn equal_range(u) != hash_function()(obj) || contains(u) true ist, ist das Verhalten undefiniert. Der value_type muss aus std::forward<K>(obj) in unordered_set EmplaceConstructible sein. Diese Überladung nimmt nur an der Auflösung der Überladungen teil, wenn Hash::is_transparent und KeyEqual::is_transparent gültig sind und jeweils einen Typ bezeichnen. Dies setzt voraus, dass ein solches Hash sowohl mit dem Typ K als auch mit dem Typ Key aufrufbar ist und dass KeyEqual transparent ist, was zusammen ermöglicht, diese Funktion aufzurufen, ohne eine Instanz von Key zu konstruieren.
10) Wenn *this bereits ein Element enthält, das transparent äquivalent zu obj ist, tut dies nichts.

Andernfalls wird ein Objekt u vom value_type mit std::forward<K>(obj) konstruiert und dann u in *this eingefügt. Template:hint wird als unverbindlicher Vorschlag verwendet, wo die Suche beginnen soll. Wenn equal_range(u) != hash_function()(obj) || contains(u) true ist, ist das Verhalten undefiniert. Der value_type muss aus std::forward<K>(obj) in unordered_set EmplaceConstructible sein. Diese Überladung nimmt nur an der Auflösung der Überladungen teil, wenn

was zusammen ermöglicht, diese Funktion aufzurufen, ohne eine Instanz von Key zu konstruieren.

Wenn nach der Operation die neue Anzahl von Elementen größer ist als max_load_factor() * bucket_count(), findet ein Rehashing statt.
Wenn ein Rehashing stattfindet (aufgrund der Einfügung), werden alle Iteratoren ungültig. Andernfalls (kein Rehashing) werden Iteratoren nicht ungültig. Wenn die Einfügung erfolgreich ist, sind Zeiger und Referenzen auf das Element, die erhalten wurden, während es im Node-Handle gehalten wurde, ungültig, und Zeiger und Referenzen, die auf dieses Element erhalten wurden, bevor es extrahiert wurde, werden gültig.(seit C++17)

Inhalt

[edit] Parameter

hint - iterator, der als Vorschlag dient, wo der Inhalt eingefügt werden soll
value - Elementwert, der eingefügt werden soll
first, last - das Iteratorenpaar, das den Quell- Bereich der einzufügenden Elemente definiert
ilist - Initialisierungsliste, aus der die Werte eingefügt werden sollen
nh - ein kompatibler Node Handle
obj - ein Wert eines beliebigen Typs, der transparent mit einem Schlüssel verglichen werden kann
Typanforderungen
-
InputIt muss die Anforderungen von LegacyInputIterator erfüllen.

[edit] Rückgabewert

1,2) Ein Paar, das aus einem Iterator auf das eingefügte Element (oder auf das Element, das die Einfügung verhindert hat) und einem bool-Wert besteht, der auf true gesetzt ist, wenn und nur wenn die Einfügung stattgefunden hat.
3,4) Ein Iterator auf das eingefügte Element oder auf das Element, das die Einfügung verhindert hat.
5,6) (keine)
7) Ein Objekt von insert_return_type mit den folgenden initialisierten Membern:
  • Wenn nh leer ist, ist inserted false, position ist end(), und node ist leer.
  • Andernfalls, wenn die Einfügung stattgefunden hat, ist inserted true, position zeigt auf das eingefügte Element, und node ist leer.
  • Wenn die Einfügung fehlgeschlagen ist, ist inserted false, node hat den vorherigen Wert von nh, und position zeigt auf ein Element mit einem Schlüssel, der äquivalent zu nh.key() ist.
8) End-Iterator, wenn nh leer war, Iterator, der auf das eingefügte Element zeigt, wenn die Einfügung stattgefunden hat, und Iterator, der auf ein Element mit einem Schlüssel zeigt, der zu nh.key() äquivalent ist, wenn diese fehlgeschlagen ist.
9) Ein Paar, das aus einem Iterator auf das eingefügte Element (oder auf das Element, das die Einfügung verhindert hat) und einem bool-Wert besteht, der auf true gesetzt ist, wenn und nur wenn die Einfügung stattgefunden hat.
10) Ein Iterator auf das eingefügte Element oder auf das Element, das die Einfügung verhindert hat.

[edit] Ausnahmen

1-4) Wenn durch eine Operation eine Ausnahme ausgelöst wird, hat die Einfügung keine Auswirkung.
Dieser Abschnitt ist unvollständig
Grund: Fälle 5-10

[edit] Komplexität

1-4) Durchschnittlich: O(1), im schlimmsten Fall O(size()).
5,6) Durchschnittlich: O(N), wobei N die Anzahl der einzufügenden Elemente ist. Im schlimmsten Fall: O(N * size() + N).
7-10) Durchschnittlich: O(1), im schlimmsten Fall O(size()).

[edit] Hinweise

Die mit Hinweis eingefügte Funktion (3,4) gibt kein boolesches Ergebnis zurück, um mit der positionsbasierten Einfügung in sequenziellen Containern wie std::vector::insert kompatibel zu sein. Dies ermöglicht die Erstellung generischer Einfüger wie std::inserter. Eine Möglichkeit, den Erfolg einer Einfügung mit Hinweis zu überprüfen, ist der Vergleich von size() vor und nach der Operation.

Feature-Test-Makro Wert Std Feature
__cpp_lib_associative_heterogeneous_insertion 202311L (C++26) Heterogene Überladungen für die übrigen Memberfunktionen in geordneten und ungeordneten assoziativen Containern. (9,10)

[edit] Beispiel

Führen Sie diesen Code aus
#include <array>
#include <iostream>
#include <unordered_set>
 
std::ostream& operator<<(std::ostream& os, std::unordered_set<int> const& s)
{
    for (os << '[' << s.size() << "] { "; int i : s)
        os << i << ' ';
    return os << "}\n";
}
 
int main ()
{
    std::unordered_set<int> nums{2, 3, 4};
 
    std::cout << "1) Initially: " << nums << std::boolalpha;
    auto p = nums.insert(1); // insert element, overload (1)
    std::cout << "2) '1' was inserted: " << p.second << '\n';
    std::cout << "3) After insertion: " << nums;
 
    nums.insert(p.first, 0); // insert with hint, overload (3)
    std::cout << "4) After insertion: " << nums;
 
    std::array<int, 4> a = {10, 11, 12, 13};
    nums.insert(a.begin(), a.end()); // insert range, overload (5)
    std::cout << "5) After insertion: " << nums;
 
    nums.insert({20, 21, 22, 23}); // insert initializer_list, (6)
    std::cout << "6) After insertion: " << nums;
 
    std::unordered_set<int> other_nums = {42, 43};
    auto node = other_nums.extract(other_nums.find(42));
    nums.insert(std::move(node)); // insert node, overload (7)
    std::cout << "7) After insertion: " << nums;
 
    node = other_nums.extract(other_nums.find(43));
    nums.insert(nums.begin(), std::move(node)); // insert node with hint, (8)
    std::cout << "8) After insertion: " << nums;
}

Mögliche Ausgabe

1) Initially: [3] { 4 3 2 }
2) '1' was inserted: true
3) After insertion: [4] { 1 2 3 4 }
4) After insertion: [5] { 0 1 2 3 4 }
5) After insertion: [9] { 13 12 11 10 4 3 2 1 0 }
6) After insertion: [13] { 23 22 13 12 11 10 21 4 20 3 2 1 0 }
7) After insertion: [14] { 42 23 22 13 12 11 10 21 4 20 3 2 1 0 }
8) After insertion: [15] { 43 42 23 22 13 12 11 10 21 4 20 3 2 1 0 }

[edit] Siehe auch

 konstruiert Elemente direkt (in-place)
(public member function) [edit]
 konstruiert Elemente "in place" unter Verwendung eines Hinweises
(public member function) [edit]
 erstellt einen std::insert_iterator vom Typ, der aus dem Argument abgeleitet wird
(Funktionsvorlage) [bearbeiten]
Abgerufen von "https://cppreference.de/mwiki/index.php?title=cpp/container/unordered_set/insert&oldid=180862"