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

habr.png

Если Вы используете стандарт 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 
#include 
#include 
#include 
#include 


const size_t mainSize = 50'000;
const size_t additionSize = mainSize;


auto getMainMap()
{
  std::map result;
  while( result.size() < mainSize )
    result.emplace(result.size(), "SomeText");

  return result;
}


auto getAdditionMap()
{
  std::map 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(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(end - start).count()
              << std::endl;
  } // <---- and stack overflow here because of incorrect mainMap after merge

  return 0;
}

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

Что делать?


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

© Habrahabr.ru