[Bug libstdc++/52476] New: [C++11] Unordered multimap reorders equivalent elements

[daniel.kruegler at googlemail dot com]

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]