Atencion Error peligroso en la implementación de C ++ std :: map :: merge y std :: set :: merge en Visual Studio 2017

Si usa el estándar C ++ 17 en MS Visual Studio 2017, tenga cuidado: la versión actual contiene un error crítico en la implementación de std :: map :: merge y std :: set :: merge. Detalles - debajo del corte.

¿Cómo se manifiesta un error?

1. La complejidad de std :: map :: merge y std :: set :: merge en lugar del estándar N * log (size () + N)), donde N es el tamaño de la parte agregada, resulta ser aproximadamente N al cuadrado.
2. Si se agrega un contenedor con un número suficientemente grande de elementos con la ayuda de la fusión, tras la destrucción del contenedor resultante obtenemos un desbordamiento de pila.
3. El contenedor llega a un estado incorrecto después de que se ejecuta la fusión, por lo que son posibles otras manifestaciones.

¿Qué dice Microsoft?

El informe de errores lo envié a Microsoft hace casi 2 meses.
En Visual Studio 2019 Update 2, Preview 2 debería haberse solucionado.

Pero en la versión actual de Visual Studio 2017 15.9.12 no se ha solucionado hasta ahora, y a juzgar por los últimos informes, espere mucho tiempo ...

El error es la marca de color incorrecta de los nodos agregados en la implementación de red-ebony.

¿Cómo reproducir?

//#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; } 

Variando el valor de mainSize, puede obtener diferentes resultados, ya sea solo una ejecución lenta o también bloquearse.

Que hacer

Revise su código y reemplace las llamadas de fusión con inserción manual. O actualice a VS 2019.
Y si el código compilado ya ha ido al cliente ... Ohhh ...