Warum gibt es ein Positionsargument in der Einfügefunktion der Menge in AWL

Question

Setzen Sie das Element immer in sortierter Reihenfolge ein, daher sollte es nicht sinnvoll sein, die einzufügende Position anzugeben.

iterator insert (iterator position, const value_type& val); 

Warum gibt es ein Position Argument, ist es nützlich?

Answer 1

Das Argument wird als Hinweis auf die Einfügepositioin für std::set::insert verwendet, um die Komplexität zu verbessern, wenn es auf die richtige Position zeigt.

hint - Iterator auf die Position vor dem das neue Element eingefügt wird (da C++ 11)

Complexity
Konstante Amortisierte wenn das Einfügen in der Position geschieht kurz nach dem Hinweis, logarithmischer in der Größe des Behälters sonst.

Einer der möglichen Fälle ist das Ändern des Elements set (die Sortierreihenfolge wird nicht geändert). std::set::iterator ist Const-Iterator, dh, Sie konnten das Element nicht direkt durch eine ändern. Sie könnten (1) das Element suchen, (2) eine Kopie erstellen und die Kopie modifizieren, (3) das Element aus set entfernen, (4) die Kopie als neuen Wert einfügen. Im vierten Schritt können Sie den Iterator im 3. Schritt an std::set::insert als Hinweis übergeben.

Answer 2

Es wird als Hinweis verwendet, wo neues Element eingefügt werden sollte, auch macht es std::set Schnittstelle kompatibel mit anderen Containern, dh. std::vector:insert, so können Sie std::inserter verwenden, die assums Typ T::insert wie Betrieb hat.

Sie können auch Einsätze optimieren, indem man zuerst std::set::equal_range verwenden, wenn beide Iteratoren zurück gleich sind es bedeutet, wurde kein Element gefunden und Iteratoren Punkt dieses Element zu platzieren, wo eingefügt werden:

std::set<int> s = {0,1,2,3,5,6,7};  
auto r = s.equal_range(4); 
if (r.first == r.second) 
    s.insert(r.first, 4);