number of calls to hash function in unordered_set

Frank Tetzel s1445051@mail.zih.tu-dresden.de
Tue Jun 12 07:52:00 GMT 2018


> > It seems to always be (inserted_elements * 2) - 1.
> > When adding 2 elements, it hashes 3 times. When adding 1 element, it
> > only hashes once. What is happening here? Why is the hash calculated
> > twice? What is so special about the last or first element?  
> 
> https://gcc.gnu.org/onlinedocs/libstdc++/manual/unordered_associative.html#containers.unordered.cache 
> answers part of the question (libc++ on the other hand seems to have 
> chosen always to cache the hash).
> 
> The other part is related to how the elements are linked in the hash 
> table, note that the hashes computed are 0 1 0 2 1 3 2 4 3 5 4 6 5 7
> 6... Reading the code seems best to understand what is going on.
> 

Thank you for the link to the documentation. That also explains why
removing "noexcept" on the hash function enables caching.

I will try to step through the code and understand it. Reading STL is
always not so easy...

Thanks for the pointers.



More information about the Gcc-help mailing list