Главная

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

2019-06-10 в 17:32, admin, рубрики: c++, c++17, std::map::merge, std::set::merge., Visual Studio, 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, можно получать разные результаты — либо только медленное выполнение, либо еще и крах.