Perhatian! Bug berbahaya dalam implementasi C ++ std :: map :: merge dan std :: set :: merge di Visual Studio 2017

Jika Anda menggunakan standar C ++ 17 di MS Visual Studio 2017 - hati-hati: versi saat ini berisi bug penting dalam implementasi std :: map :: merge dan std :: set :: merge. Detail - di bawah potongan.

Bagaimana bug bermanifestasi?

1. Kompleksitas std :: map :: merge dan std :: set :: merge alih-alih standar N * log (size () + N)), di mana N adalah ukuran dari bagian yang ditambahkan, ternyata sekitar N kuadrat.
2. Jika sebuah wadah dengan jumlah elemen yang cukup besar ditambahkan dengan bantuan penggabungan, setelah penghancuran dari wadah yang dihasilkan, kita mendapatkan stack overflow.
3. Wadah datang ke kondisi yang salah setelah penggabungan berjalan, sehingga manifestasi lain dimungkinkan.

Apa yang dikatakan Microsoft?

Laporan bug dikirim oleh saya ke Microsoft hampir 2 bulan yang lalu.
Dalam Visual Studio 2019 Pembaruan 2 Pratinjau 2 seharusnya diperbaiki.

Tetapi dalam versi Visual Studio 2017 15.9.12 saat ini belum diperbaiki sejauh ini, dan menilai dari laporan terbaru, tunggu lama ...

Bug adalah tanda warna yang salah dari node yang ditambahkan dalam implementasi red-ebony.

Bagaimana cara mereproduksi?

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

Memvariasikan nilai mainSize, Anda bisa mendapatkan hasil yang berbeda - baik eksekusi lambat, atau crash.

Apa yang harus dilakukan

Merevisi kode Anda dan mengganti panggilan gabung dengan penyisipan manual. Atau tingkatkan ke VS 2019.
Dan jika kode yang dikompilasi sudah ke pelanggan ... Ohhh ...