Хабрахабр

Внимание! Опасный баг в реализации 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 должны были исправить.

9. А вот в текущей версии Visual Studio 2017 15. 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(); 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.
А если скомпилированный код уже ушёл к заказчику… Оххх…

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть