http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52476
Bug #: 52476 Summary: [C++11] Unordered multimap reorders equivalent elements Classification: Unclassified Product: gcc Version: 4.7.0 Status: UNCONFIRMED Severity: normal Priority: P3 Component: libstdc++ AssignedTo: unassig...@gcc.gnu.org ReportedBy: daniel.krueg...@googlemail.com gcc 4.7.0 20120225 (experimental) and also gcc 4.6.3 perform reordering of equivalent elements of unordered_multimap in violation of the standard specification. Testcase: //--------- #include <unordered_map> #include <iostream> void printHashTable(const std::unordered_multimap<int, int>& map) { for (unsigned i = 0; i < map.bucket_count(); ++i) { std::cout << "b[" << i << "]:" << std::endl; for (auto it = map.begin(i); it != map.end(i); ++it) { std::cout << " " << map.hash_function()(it->first) << " [" << it->first << "," << it->second << "]" << std::endl; } } std::cout << "----------------------" << std::endl; } int main() { std::unordered_multimap<int, int> dict = { {0,0}, {1,0}, {2,0}, {3,0}, {4,0}, {1,1} }; printHashTable(dict); dict.insert({{3,1}, {3,2}, {5,0} }); printHashTable(dict); dict.max_load_factor(0.5); printHashTable(dict); } //--------- The observed output is: //--------- b[0]: 0 [0,0] b[1]: 1 [1,1] 1 [1,0] b[2]: 2 [2,0] b[3]: 3 [3,0] b[4]: 4 [4,0] b[5]: b[6]: ---------------------- b[0]: 0 [0,0] b[1]: 1 [1,0] 1 [1,1] b[2]: 2 [2,0] b[3]: 3 [3,2] 3 [3,1] 3 [3,0] b[4]: 4 [4,0] b[5]: 5 [5,0] b[6]: b[7]: b[8]: b[9]: b[10]: ---------------------- b[0]: 0 [0,0] b[1]: 1 [1,1] 1 [1,0] b[2]: 2 [2,0] b[3]: 3 [3,0] 3 [3,1] 3 [3,2] b[4]: 4 [4,0] b[5]: 5 [5,0] b[6]: b[7]: b[8]: b[9]: b[10]: b[11]: b[12]: b[13]: b[14]: b[15]: b[16]: b[17]: b[18]: b[19]: b[20]: b[21]: b[22]: b[23]: b[24]: b[25]: b[26]: b[27]: b[28]: ---------------------- //--------- The relevant library constraints are described in [unord.req] p6: "Mutating operations on unordered containers shall preserve the relative order of elements within each equivalent-key group unless otherwise specified." and in [unord.req] p9: "For unordered_multiset and unordered_multimap, rehashing preserves the relative ordering of equivalent elements." The actual defects in above output are the following: 1) The second output should not reorder 1 [1,1] 1 [1,0] to 1 [1,0] 1 [1,1] 2) The third output should not reorder 1 [1,0] 1 [1,1] to 1 [1,1] 1 [1,0] and it should not reorder 3 [3,2] 3 [3,1] 3 [3,0] to 3 [3,0] 3 [3,1] 3 [3,2]