Warum SGI STL nicht das Copy-and-Swap-Idiom verwenden?

Question

Vor kurzem las ich eine Antwort auf Stackoverflow über What is the copy-and-swap idiom? und wusste, dass das Copy-and-Swap-Idiom kann

Code Doppelarbeit zu vermeiden und eine starke Ausnahme Garantie bietet.

Allerdings, wenn ich in SGI STL sah dequeimplementation, fand ich, dass es nicht das Idiom nicht verwendet. Ich frage mich, warum nicht, wenn das Idiom irgendwie wie eine "Best Practice" ist?

deque& operator= (const deque& __x) { 
    const size_type __len = size(); 
    if (&__x != this) { 
     if (__len >= __x.size()) 
     erase(copy(__x.begin(), __x.end(), _M_start), _M_finish); 
     else { 
     const_iterator __mid = __x.begin() + difference_type(__len); 
     copy(__x.begin(), __mid, _M_start); 
     insert(_M_finish, __mid, __x.end()); 
     } 
    } 
    return *this; 
    }  

Answer 1

Der Code, den Sie anzeigen, reserviert Speicher nicht neu, es sei denn, der Container muss vergrößert werden, was eine erhebliche Einsparung darstellen kann. Copy-and-Swap weist immer Speicher zu, um die Kopie auszuführen, und dann den Speicher für die vorhandenen Elemente freigibt.

Betrachten Sie eine deque<vector<int>>, wo die vorhandenen Vektor Mitglieder der Deque große Kapazitäten haben.

deque<vector<int>> d(2); 
d[0].reserve(100); 
d[1].reserve(100); 

die SGI STL-Implementierung verwenden, um jedes Element zuweisen bewahrt, dass die Kapazität, so dass, wenn die Vektoren sie so ohne Zuteilung etwas tun können, um wachsen müssen:

d = deque<vector<int>>(2); 
assert(d[0].capacity() >= 100); 
assert(d[1].capacity() >= 100); 
d[0].push_back(42); // does not cause an allocation 

Copy-and-Swap würde ersetzen die vorhandenen Mitglieder mit neuen Elementen, die keine freie Kapazität haben, so dass die obigen Behauptungen fehlschlagen würden, und die push_back müsste Speicher reservieren. Dies verschwendet die Zeit, die sich freigibt und neu verteilt, anstatt den vollkommen guten Speicher zu verwenden, der bereits da ist.

Copy-and-Swap ist eine bequeme Möglichkeit, Exception-Sicherheit und Korrektheit sehr einfach, aber nicht unbedingt so effizient wie möglich zu erhalten. In Code wie der STL oder der C++ Standard Library wollen Sie nicht die Effizienz zugunsten einer etwas einfacheren Implementierung opfern, und solcher Code sollte normalerweise von Experten geschrieben werden, die in der Lage sind, Ausnahmesicherheit richtig zu machen, indem sie es "auf die harte Tour machen "Nicht nur der bequemste Weg.

Answer 2

Während Copy-and-Swap die beste Vorgehensweise ist, kann es in bestimmten Fällen mit einer Effizienzeinbuße verbunden sein. In diesem speziellen Fall nutzt der Code die Tatsache, dass, wenn dem Vektor, der zugewiesen wird, bereits genügend Speicher verfügbar ist, die Werte einfach kopiert werden können, ohne eine zusätzliche Speicherzuweisung vorzunehmen.

Answer 3

Das Idiom ist eine einfache Möglichkeit, eine starke Ausnahmegarantie zu bieten, und so ist es eine "Best Practice" im Sinne einer guten Sache, es sei denn, Sie haben einen guten Grund, dies nicht zu tun.

Es hat jedoch eine Kosten: ein zweites Objekt muss erstellt und zerstört werden. Dies kann teuer sein und, wenn dies eine große Speicherzuweisung erfordert, kann die Spitzenspeicherauslastung um viel mehr als notwendig erhöht werden. Wenn das ein Problem ist oder wenn Sie eine generische Bibliothek wie diese schreiben, sollten Sie andere Möglichkeiten finden, das Objekt zu kopieren, ohne ein temporäres Objekt zu erstellen. Ausnahmesicherheit erfordert mehr Sorgfalt als bei Verwendung der einfachen Sprache.

Answer 4

Ich denke, in diesem Fall wird dies getan, um übermäßige Neuzuweisungen zu vermeiden: copy-and-swap erfordert, dass die Kopie zugeordnet wird (wodurch Doppelspeicherung in einem Moment), dann alle Deque Speicher aufgehoben werden. Dieser Code wird nur zugewiesen, wenn copy-from größer ist und nur die Differenz benötigt wird.

Das gilt eigentlich für deque und nicht für Vektor - wie ist da: vector :: operator = implementiert?

Darüber hinaus wurde möglicherweise geschrieben, bevor das Idiom populär wurde. Und selbst jetzt wird es nicht allgemein akzeptiert.

Answer 5

Die Standard-Mandate dass std::deque<T>::operator=(const std::deque<T>&) die Grund Ausnahme Garantie bieten sollte - das heißt, dass der Behälter in einem gültigen Zustand im Fall einer Ausnahme verlassen wird, nicht die starke Garantie - die für die Nutzung der Kopie argumentieren würde /Wechsel.