public inbox for gcc-bugs@sourceware.org help / color / mirror / Atom feed
From: "daniel.kruegler at googlemail dot com" <gcc-bugzilla@gcc.gnu.org> 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 [thread overview] Message-ID: <bug-52476-4@http.gcc.gnu.org/bugzilla/> (raw) 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 <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]
next reply other threads:[~2012-03-04 10:57 UTC|newest] Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top 2012-03-04 10:57 daniel.kruegler at googlemail dot com [this message] 2012-03-04 11:28 ` [Bug libstdc++/52476] " paolo.carlini at oracle dot com 2012-03-04 16:11 ` daniel.kruegler at googlemail dot com 2012-03-04 16:28 ` daniel.kruegler at googlemail dot com 2012-03-05 1:09 ` [Bug libstdc++/52476] [DR 518] " paolo.carlini at oracle dot com 2012-03-16 21:42 ` fdumont at gcc dot gnu.org 2012-04-09 19:12 ` fdumont at gcc dot gnu.org 2012-04-09 20:57 ` redi at gcc dot gnu.org 2012-04-10 16:55 ` paolo.carlini at oracle dot com
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=bug-52476-4@http.gcc.gnu.org/bugzilla/ \ --to=gcc-bugzilla@gcc.gnu.org \ --cc=gcc-bugs@gcc.gnu.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).