public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libstdc++/52476] New: [C++11] Unordered multimap reorders equivalent elements
@ 2012-03-04 10:57 daniel.kruegler at googlemail dot com
  2012-03-04 11:28 ` [Bug libstdc++/52476] " paolo.carlini at oracle dot com
                   ` (7 more replies)
  0 siblings, 8 replies; 9+ messages in thread
From: daniel.kruegler at googlemail dot com @ 2012-03-04 10:57 UTC (permalink / raw)
  To: gcc-bugs

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]


^ permalink raw reply	[flat|nested] 9+ messages in thread
end of thread, other threads:[~2012-04-10 16:55 UTC | newest]

Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-03-04 10:57 [Bug libstdc++/52476] New: [C++11] Unordered multimap reorders equivalent elements daniel.kruegler at googlemail dot com
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

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).