lundi 29 juin 2015

How std::unordered_map is implemented in c++ compilers

I have not read the standard and I am a bit surprised that this question has never been specifically asked before in stack overflow.

c++ unordered_map collision handling , resize and rehash

This is a previous question opened by me and I have seen that I was having a confusion about how unordered_map is implemented. I am sure many other people shares that confusion with me. It has been mentioned that:

Every unordered_map implementation stores a linked list to external nodes in the array of buckets... No, that is not at all the most efficient way to implement a hash map for most common uses. Unfortunately, a small "oversight" in the specification of unordered_map all but requires this behavior. The required behavior is that iterators to elements must stay valid when inserting or deleting other elements

I was hoping that someone might explain the implementation and how it corresponds to the c++ standard definition (in terms of performance requirements ) and maybe even how it can be improved.

Aucun commentaire:

Enregistrer un commentaire