How a std::unordered_map search algorithm is implemented?

Question

I understand that if it is necessary to implement a search in an ordered set, then we compare the data of each "cell" of the binary tree, which is the structure of the ordered set using the "<" operator of the appropriate type, but I don’t understand how everything works in the case of std::unordered_map.
Where can I find any article or so on how everything is arranged and / or see the code directly?

Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key.

[this](https://en.cppreference.com/w/cpp/container/unordered_map) helps? — yaodav, Jul 05 '20 at 13:52
@yaodav in the edit I provided a quote about the placement of elements, could you tell me what size bucket has and search inside bucket is it an brute force of all elements inside? — Gaurav Goswami, Jul 05 '20 at 14:10
@GauravGoswami [here](http://www.cplusplus.com/reference/unordered_map/unordered_map/max_load_factor/) you can read about the max bucket size, and [here](http://www.cplusplus.com/reference/unordered_map/unordered_map/bucket_size/) about the actual size — yaodav, Jul 05 '20 at 14:18
Maybe my answer [here](https://stackoverflow.com/a/30567466/410767) will help...? As for "what size bucket has" -> that's a bit vague: you can generally expect each `unordered_map` bucket to be an iterator, and the size of a pointer (at least during optimised builds); "search inside bucket is it a brute force for all elements inside" -> yes. — Tony Delroy, Jul 05 '20 at 14:51

score 1 · Accepted Answer · answered Sep 11 '20 at 12:32

You can search through a std::unordered_map for a key with a code like below: (here key variable equals to the key you are searching):

if (your_map.find(key) != your_map.end()) {
    ...
}

If you want to search for a value you can use for loop like this:

for (const auto& pair : your_map) {
    if (pair.second == the_value_you_are_finding) {
        ...
        break;
    }
}

But if you want to know how does your program searchs through the unordered map or how the functions used above are implemented then you have to see the source code of your C++ Standard Library as it depends on your library.

How a std::unordered_map search algorithm is implemented?

1 Answers1