Atenção! Bug perigoso na implementação do C ++ std :: map :: merge e std :: set :: merge no Visual Studio 2017

Se você usar o padrão C ++ 17 no MS Visual Studio 2017 - tenha cuidado: a versão atual contém um erro crítico na implementação de std :: map :: merge e std :: set :: merge. Detalhes - sob o corte.

Como um bug se manifesta?

1. A complexidade de std :: map :: merge e std :: set :: merge em vez do log N * padrão (tamanho () + N)), onde N é o tamanho da peça adicionada, resulta em N ao quadrado.
2. Se um contêiner com um número suficientemente grande de elementos foi adicionado com a ajuda da mesclagem, após a destruição do contêiner resultante, obtemos um estouro de pilha.
3. O contêiner fica em um estado incorreto após a mesclagem ser executada, portanto, outras manifestações são possíveis.

O que a Microsoft diz?

O relatório de erros foi enviado por mim à Microsoft há quase 2 meses.
No Visual Studio 2019, a Atualização 2 da Visualização 2 deveria ter sido corrigida.

Mas na versão atual do Visual Studio 2017 15.9.12 não foi corrigida até agora e, a julgar pelos relatórios mais recentes, aguarde muito tempo ...

O bug é a marcação de cor incorreta dos nós adicionados na implementação do ébano vermelho.

Como se reproduzir?

//#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; } 

Variando o valor de mainSize, você pode obter resultados diferentes - apenas execução lenta ou travamento.

O que fazer

Revise seu código e substitua as chamadas de mesclagem pela inserção manual. Ou atualize para o VS 2019.
E se o código compilado já foi para o cliente ... Ohhh ...