Attention! Dangerous bug in C ++ implementation of std :: map :: merge and std :: set :: merge in Visual Studio 2017

If you use the C ++ standard in MS Visual Studio 2017 - be careful: the current version contains a critical bug in the implementation of std :: map :: merge and std :: set :: merge. Details - under the cut.

How does the bug manifest?

1. The complexity of std :: map :: merge and std :: set :: merge instead of the standard declared N * log (size () + N)), where N is the size of the added part, is approximately N squared.
2. If a container with a sufficiently large number of elements was added with the help of merge, when destroying the resulting container, we get the stack overflow.
3. The container after work merge comes to an incorrect state, therefore, other manifestations are possible.

What does Microsoft say?

Bugreport was sent to me by Microsoft almost 2 months ago.
In Visual Studio 2019 Update 2, Preview 2 should have been fixed.

But in the current version of Visual Studio 2017 15.9.12 is not fixed until now, and, judging by the latest reports, wait a long time ...

The bug is incorrect marking of the color of the added nodes in the implementation of the red-black tree.
')

How to play?

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

By varying the value of mainSize, you can get different results - either only slow execution, or else a crash.

What to do?

Revise your code and replace merge with manual insertion. Or go to VS 2019.
And if the compiled code has already gone to the customer ... Ohhh ...