Внимание! Опасная Ошибка В Реализации 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 — размер добавляемой части, получается примерно Н в квадрате.

2. Если с помощью слияния был добавлен контейнер с достаточно большим количеством элементов, то при уничтожении полученного контейнера мы получим переполнение стека.

3. После операции слияния контейнер оказывается в неправильном состоянии, поэтому возможны и другие проявления.

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

Но текущая версия 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;
 }
 

   

Что делать?

Или переключитесь на VS 2019. А если скомпилированный код уже отправлен заказчику.

Охх.

Теги: #C++ #Visual Studio #c++17 #visual studio 2017 #std::map::merge #std::set::merge.

• Adobe Photoshop, Вероятно, Лучшее Программное Обеспечение Для Редактирования Фотографий

  19 Oct, 24

• Тыква

  19 Oct, 24

• Проблемы С Реестром Microsoft Равны Медленному Компьютеру

  19 Oct, 24

• Social Search — Сервис Для «Кражи» Клиентов Конкурентов В Социальных Сетях

  19 Oct, 24

• Указатели На Методы Класса В C++

  19 Oct, 24

• Спецпроект: Солнечная Электростанция На Автодоме. Часть 1

  19 Oct, 24

• Wikileaks Прекратил Работу

  19 Oct, 24

• Путь Профессионального Роста На Примере Доктора Быкова И Его Стажеров

  19 Oct, 24

• Невозможные Креветки, Или Антарктический Мем

  19 Oct, 24

• Netscape — Это Рождение Компании.

  19 Oct, 24