注意！ C ++实现std ::映射:: merge :: std :: set :: Visual Studio 2017中的合并::危险错误

如果您在MS Visual Studio 2017中使用C ++ 17标准-请注意：当前版本在std :: map :: merge和std :: set：merge的实现中包含一个严重的错误。 详细信息-下切。

错误如何显现？

1. std :: map :: merge和std :: set :: merge而不是标准的N * log（size（）+ N））的复杂度，其中N是添加部分的大小，结果约为N平方。
2. 如果在合并的帮助下添加了具有足够数量元素的容器，则在销毁所得容器时，我们会发生堆栈溢出。
3. 合并运行后，容器进入错误状态，因此其他表现形式也是可能的。

微软怎么说？

该错误报告是大约两个月前由我发送给Microsoft的。
在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的值，可以获得不同的结果-要么执行缓慢，要么崩溃。

怎么办

修改您的代码，并用手动插入替换合并调用。 或升级到VS 2019。
如果编译后的代码已经交给客户了……哦……