map entry goes missing after a large number of insertions

[loopless]

I have a map that is <int, void *> and a previously inserted entry goes 'missing' after a large number of insertions of other key/value pairs. The key value is 1597736, and it goes missing from the map after inserting a key of value 9861762. The size of the map is 1251645 when the problem occurs.

This happens on Linux , and not Windows oddly. I have a reproducer.

keys.txt.gz

test.zip

I am using GCC 6.3.1 on Centos 7 and compiling with
c++ test.cpp -o test

[loopless]

there is a small bug in the code that reads keys.txt , it should check of.fail() before adding the element to the map. It does not affect the validity of the reproducer.

[Tessil]

Than you very much for the report. That's a quite critical bug. The commit I made should fix the issue.

The problem came from the too high number of collisions causing the bucket_entry::m_dist_from_ideal_bucket variable to overflow (distance higher than 32767) . I fixed the issue but I really recommend to use a better hash function than std::hash<T> for integers with GCC and Clang as they use a simple identity function which can cause some problems with hash tables using open-addressing. MSVC uses a more robust hash for integer which explain why it was working on Windows.

[loopless]

Thanks for fixing it. As you say, it is fairly critical and it's going to be sort of random