Achtung! Gefährlicher Fehler in der C ++ - Implementierung std :: map :: merge und std :: set :: merge in Visual Studio 2017

Wenn Sie den C ++ 17-Standard in MS Visual Studio 2017 verwenden, seien Sie vorsichtig: Die aktuelle Version enthält einen kritischen Fehler bei der Implementierung von std :: map :: merge und std :: set :: merge. Details - unter dem Schnitt.

Wie manifestiert sich ein Fehler?

1. Die Komplexität von std :: map :: merge und std :: set :: merge anstelle des Standard-N * -Protokolls (Größe () + N)), wobei N die Größe des hinzugefügten Teils ist, beträgt ungefähr N im Quadrat.
2. Wenn ein Container mit einer ausreichend großen Anzahl von Elementen mit Hilfe der Zusammenführung hinzugefügt wurde, kommt es bei Zerstörung des resultierenden Containers zu einem Stapelüberlauf.
3. Der Container wird nach dem Ausführen der Zusammenführung in einen falschen Zustand versetzt, sodass andere Manifestationen möglich sind.

Was sagt Microsoft?

Der Bugreport wurde von mir vor fast 2 Monaten an Microsoft gesendet.
In Visual Studio 2019 Update 2 sollte Vorschau 2 behoben sein.

Aber in der aktuellen Version von Visual Studio 2017 wurde 15.9.12 noch nicht behoben, und nach den neuesten Berichten zu warten, warten Sie lange ...

Der Fehler ist die falsche Farbmarkierung der hinzugefügten Knoten bei der Implementierung von Rot-Ebenholz.

Wie reproduziere ich?

//#include "pch.h" #include <chrono> #include <string> #include <iostream> #include <map> #include <set> const size_t mainSize = 50'000; const size_t additionSize = mainSize; auto getMainMap() { std::map<size_t, std::string> result; while( result.size() < mainSize ) result.emplace(result.size(), "SomeText"); return result; } auto getAdditionMap() { std::map<size_t, std::string> result; while ( result.size() < additionSize ) result.emplace(mainSize + result.size(), "SomeAdditionText"); return result; } int main() { { auto mainMap = getMainMap(); auto addition = getAdditionMap(); auto start = std::chrono::steady_clock::now(); for ( auto const &elem : addition ) mainMap.emplace(elem); auto end = std::chrono::steady_clock::now(); std::cout << "manual insertion with copy: " << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << std::endl; } { auto mainMap = getMainMap(); auto addition = getAdditionMap(); auto start = std::chrono::steady_clock::now(); mainMap.merge(addition); auto end = std::chrono::steady_clock::now(); std::cout << "std::map::merge: " << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << std::endl; } // <---- and stack overflow here because of incorrect mainMap after merge return 0; } 

Wenn Sie den Wert von mainSize variieren, können Sie unterschiedliche Ergebnisse erzielen - entweder nur langsame Ausführung oder auch Absturz.

Was zu tun ist?

Überarbeiten Sie Ihren Code und ersetzen Sie Zusammenführungsaufrufe durch manuelles Einfügen. Oder aktualisieren Sie auf VS 2019.
Und wenn der kompilierte Code bereits an den Kunden gegangen ist ... Ohhh ...