From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 8015 invoked by alias); 4 Mar 2012 10:57:31 -0000 Received: (qmail 8004 invoked by uid 22791); 4 Mar 2012 10:57:30 -0000 X-SWARE-Spam-Status: No, hits=-2.8 required=5.0 tests=ALL_TRUSTED,AWL,BAYES_00 X-Spam-Check-By: sourceware.org Received: from localhost (HELO gcc.gnu.org) (127.0.0.1) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sun, 04 Mar 2012 10:57:16 +0000 From: "daniel.kruegler at googlemail dot com" To: gcc-bugs@gcc.gnu.org Subject: [Bug libstdc++/52476] New: [C++11] Unordered multimap reorders equivalent elements Date: Sun, 04 Mar 2012 10:57:00 -0000 X-Bugzilla-Reason: CC X-Bugzilla-Type: new X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: gcc X-Bugzilla-Component: libstdc++ X-Bugzilla-Keywords: X-Bugzilla-Severity: normal X-Bugzilla-Who: daniel.kruegler at googlemail dot com X-Bugzilla-Status: UNCONFIRMED X-Bugzilla-Priority: P3 X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Changed-Fields: Message-ID: X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/ Auto-Submitted: auto-generated Content-Type: text/plain; charset="UTF-8" MIME-Version: 1.0 Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-bugs-owner@gcc.gnu.org X-SW-Source: 2012-03/txt/msg00326.txt.bz2 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: unassigned@gcc.gnu.org ReportedBy: daniel.kruegler@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 #include void printHashTable(const std::unordered_multimap& 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 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]