Внимание! Опасный баг в реализации C++ std::map::merge и std::set::merge в Visual Studio 2017

Если Вы используете стандарт C++17 в MS Visual Studio 2017 — будьте осторожны: текущая версия содержит критический баг в реализации std::map::merge и std::set::merge. Подробности — под катом.

Как проявляется баг?

1. Сложность std::map::merge и std::set::merge вместо заявленной стандартом N*log(size()+N)), где N — размер добавляемой части, оказывается примерно N в квадрате.
2. Если с помощью merge был добавлен контейнер с достаточно большим количеством элементов — при уничтожении результирующего контейнера получим stack overflow.
3. Контейнер после работы merge приходит в некорректное состояние, поэтому возможны и другие проявления.

Что говорит Microsoft?

Багрепорт был отправлен мной в Microsoft почти 2 месяца назад.
В Visual Studio 2019 Update 2 Preview 2 должны были исправить.

А вот в текущей версии Visual Studio 2017 15.9.12 не исправлено до сих пор, и, судя по последним сообщениям, ждать еще долго…

Баг заключается в некорректной маркировке цвета добавленных узлов в реализации красно-чёрного дерева.

Как воспроизвести?

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

Варьируя значение mainSize, можно получать разные результаты — либо только медленное выполнение, либо еще и крах.

Что делать?

Пересмотреть свой код и заменить обращения к merge ручной вставкой. Либо перейти на VS 2019.
А если скомпилированный код уже ушёл к заказчику… Оххх…