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

[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]

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

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52476

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-03-04
                 CC|                            |fdumont at gcc dot gnu.org
     Ever Confirmed|0                           |1

--- Comment #1 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-03-04 11:28:05 UTC ---
Thanks a lot Daniel. Thus I suspect the issue may be very old, maybe even
dating back to the tr1 code (we should double check that by avoiding any use of
fancy C++11 features like initializer lists in the testcase), because, if I
remember correctly, up to 4.7 we changed minor details as regards the core
algorithms.

Time to fix it!

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

[daniel.kruegler at googlemail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52476

--- Comment #2 from Daniel Krügler <daniel.kruegler at googlemail dot com> 2012-03-04 16:10:19 UTC ---
(In reply to comment #1)
> (we should double check that by avoiding any use of
> fancy C++11 features like initializer lists in the testcase)

I rewrote the testcase in C++03 form and based on TR1 unordered map:

//------
#include <tr1/unordered_map>
#include <iostream>
#include <utility>

typedef std::tr1::unordered_multimap<int, int> map_type;

void printHashTable(const map_type& map)
{
  for (unsigned i = 0; i < map.bucket_count(); ++i) {
    std::cout << "b[" << i << "]:" << std::endl;
    for (map_type::const_local_iterator 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()
{
  typedef std::pair<int, int> P;
  const P input1[] = {
    P(0,0),
    P(1,0),
    P(2,0),
    P(3,0),
    P(4,0),
    P(1,1)
  };
  map_type dict(input1, input1 + sizeof(input1)/sizeof(input1[0]));
  printHashTable(dict);

  const P input2[] = {
    P(3,1),
    P(3,2),
    P(5,0)
  };
  dict.insert(input2, input2 + sizeof(input2)/sizeof(input2[0]));
  printHashTable(dict);

  dict.max_load_factor(0.5);
  printHashTable(dict);
}
//------

The incorrect runtime behaviour is unchanged compared to the original form.
This means, one could actually remove the [C++11] tag from the bug title.

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

[daniel.kruegler at googlemail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52476

--- Comment #3 from Daniel Krügler <daniel.kruegler at googlemail dot com> 2012-03-04 16:28:02 UTC ---
(In reply to comment #2)
> This means, one could actually remove the [C++11] tag from the bug title.

I withdraw this suggestion: In TR1 (N1836) there did no exist the reordering
constraints, actually the new constraint were added with:

http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#518

[Bug libstdc++/52476] [DR 518] Unordered multimap reorders equivalent elements

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52476

--- Comment #4 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-03-05 01:09:15 UTC ---
Ah, thanks, that explains a lot.

[Bug libstdc++/52476] [DR 518] Unordered multimap reorders equivalent elements

[fdumont at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52476

--- Comment #5 from François Dumont <fdumont at gcc dot gnu.org> 2012-03-16 21:03:24 UTC ---
Author: fdumont
Date: Fri Mar 16 21:03:15 2012
New Revision: 185476

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=185476
Log:
2012-03-15  François Dumont  <fdumont@gcc.gnu.org>

    PR libstdc++/52476
    * include/bits/hashtable.h (_Hashtable<>::_M_rehash_aux): Add.
    (_Hashtable<>::_M_rehash): Use the latter.
    * testsuite/23_containers/unordered_multimap/insert/52476.cc: New.
    * testsuite/23_containers/unordered_multiset/insert/52476.cc: New.

Added:
   
trunk/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/52476.cc
   
trunk/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/52476.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/hashtable.h

[Bug libstdc++/52476] [DR 518] Unordered multimap reorders equivalent elements

[fdumont at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52476

--- Comment #6 from François Dumont <fdumont at gcc dot gnu.org> 2012-04-09 19:12:23 UTC ---
Author: fdumont
Date: Mon Apr  9 19:12:18 2012
New Revision: 186249

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=186249
Log:
2012-04-09  François Dumont  <fdumont@gcc.gnu.org>

    PR libstdc++/52476
    * include/bits/hashtable.h (_Hashtable<>::_M_rehash_aux): Add.
    (_Hashtable<>::_M_rehash): Use the latter.
    * testsuite/23_containers/unordered_multimap/insert/52476.cc: New.
    * testsuite/23_containers/unordered_multiset/insert/52476.cc: New.

Added:
   
branches/gcc-4_7-branch/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/52476.cc
   
branches/gcc-4_7-branch/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/52476.cc
Modified:
    branches/gcc-4_7-branch/libstdc++-v3/ChangeLog
    branches/gcc-4_7-branch/libstdc++-v3/include/bits/hashtable.h

[Bug libstdc++/52476] [DR 518] Unordered multimap reorders equivalent elements

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52476

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.7.1

[Bug libstdc++/52476] [DR 518] Unordered multimap reorders equivalent elements

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52476

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED

--- Comment #7 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-04-10 16:55:04 UTC ---
Fixed for 4.7.1.