[Bug libstdc++/53115] New: _Hashtable::_M_rehash_aux(false_type) is broken

["tat_13 at mail dot ru" <gcc-bugzilla at gcc dot gnu dot org>]

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

             Bug #: 53115
           Summary: _Hashtable::_M_rehash_aux(false_type) is broken
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: critical
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: tat_13@mail.ru


Function _Hashtable::_M_rehash_aux, added in rev. libstdc++/52476, is broken
for not unique keys (unordered_multiset and unordered_multimap).

Scheduled checking after series of equal elements is performed after inserting
of next different element. This can lead to invalid bucket links and broken
equal_range/count.

Below is simple example that demonstrates this bug.

#include <stdio.h>
#include <unordered_set>

typedef std::unordered_multiset<int> TMap;

int main()
{
    TMap x;

    x.insert(10);
    x.insert(10);
    x.insert(10);
    x.insert(10);
    x.insert(10);
    x.insert(24);
    x.insert(25);
    x.insert(2);
    x.insert(2);
    x.insert(1);

    printf("count=%u\n", x.count(2));

    x.insert(10);

    printf("count=%u\n", x.count(2));

    return 0;
}

Output is:

count=2
count=0