Error in tbb :: concurrent_unordered_multimap? Records are lost, even if single-threaded

Question

I understand that tbb::concurrent_unordered_multimap should behave like std::unordered_multimap if I use only one thread. However, this is not the case in this example:

 #include "tbb/concurrent_unordered_map.h" #include <iostream> #include <unordered_map> struct myhash { size_t operator()(const int& a) const { return 1; } }; int main() { tbb::concurrent_unordered_multimap<int, int, myhash> tbbidx; std::unordered_multimap<int, int, myhash> stdidx; for(int i = 0; i < 100; ++i) { tbbidx.insert(std::make_pair(i % 10, i)); stdidx.insert(std::make_pair(i % 10, i)); } std::cout << "tbb size " << tbbidx.size() << std::endl; std::cout << "tbb count " << tbbidx.count(0) << std::endl; std::cout << "std size " << stdidx.size() << std::endl; std::cout << "std count " << stdidx.count(0) << std::endl; } 

The result is the following:

 tbb size 100 tbb count 1 std size 100 std count 10 

If I remove myhash , I get the correct result. However, the way I understand hashmaps is that a terrible hash function should only affect performance and not correctness if the function returns the same value if x==y .

Answer 1

MDSL,

The problem is internal_insert() . The reason i / 10 worked where i % 10 not the order in which the elements were inserted into the multimap, which is a symptom of an error. internal_insert did not compare with the key, so each insert was at the end of the list (all hashes were equal, so the method just got to the end.) When i / 10 , all 0 keys were inserted, then all 1 key and so on. internal_equal_range checks for key equality and correctly finds the end of this range.

Thanks for finding the error. I add a "degenerate hash" unit test, and I still need to understand why our validators did not catch the list out of order.

Regards, Chris

(Sorry, I got the wrong equation) ...