The sentence in bold below in the book "Standard Library" by Nikolay Yosuttis, I do not understand

I am reading The Standard Library, Second Edition, by Nikolai Yosuttis. On page 183 we have:

Examples of using unordered maps and multiframes

The example provided for multiframes on page 179 also works for unordered multimap if you replace map

with unordered_map

in the include directive and multimap

with unordered_multimap

in the container declaration:

#include <unordered_map>
...
unordered_multimap<int,string> coll;
...

      

The only difference is that the order of the elements is undefined. However, on most platforms, items will still be sorted because the default hash function is the modulo operator.

I emphasized the bold part that I don't understand. My first impression when I read this was that the author says that both programs (the one on page 179, see below) and above) should print city names in the same order on most platforms. But that doesn't happen in clang and GCC. See Live Examples map

and unordered_map

at GCC. The same results were obtained in clang.

After thinking for a while, I interpreted the author saying that city names are printed in the same order for almost all platforms when processed with unordered_map

, and the output seems to confirm this. But even so, I find it difficult to accept this interpretation, since different implementations will probably use different hash functions!

Below you will find an example on page 179 mentioned above:

#include <map>
#include <string>
#include <iostream>
using namespace std;
int main()
{
    multimap<int,string> coll; // container for int/string values
    // insert some elements in arbitrary order
    // - a value with key 1 gets inserted twice
    coll = { {5,"tagged"},
             {2,"a"},
             {1,"this"},
             {4,"of"},
             {6,"strings"},
             {1,"is"},
             {3,"multimap"} };
    // print all element values
    // - element member second is the value
    for (auto elem : coll) {
        cout << elem.second << ’ ’;
    }
    cout << endl;
}

      

+3


source to share


3 answers


I think this is useless at best.

The common default hash function for int

is to use itself int

unchanged. So if the hash table has more codes than the largest integer, and duplicates are added in the same order, most implementations (by accident) output the pairs in sorted order.

However, generally speaking, for objects with some ordering, this is not the case when H (A) H (B), if A <B. H (.) Is a hash function. It is also not usually the case that MAX (H (X)) <= bucket count.



Thus, the book does point to the peculiarities of a rather contrived special case. Why do I think this is useless? Presenting the random properties of contrived special cases may accidentally lead readers to think they are examples of a broader function.

Hashmap entries are not returned in any useful order. They are not returned in the order they were placed. They are not returned in reverse order. They don't come back in sorted order. They don't come back in any order. [Sam I].

If an example is helpful, it would be an example that they won't revert to order.

+6


source


I think the confusion comes from the fact that we are talking about 2 hash functions.

The first is a function that gets the number from the key. This is std :: hash by default , but can also be supplied as a parameter std::unorderded_map

.



Another function is one that takes this number and returns the bucket index, which takes that number and returns a number in the range 0 - bucket_count() - 1

. This is one of the implemented implementations, but it is almost always modulo %

, because it is the simplest and has no negative impact if the original hash function is evenly distributed, and std::hash

is user-defined.

+1


source


The statement is nonsense. On certain platforms, under certain circumstances, the order of items in (usually small) unordered_multimap

will be the same as in multimap

. However, what is really useful to the programmer is a guarantee, such as "This container is sorted." This is not guaranteed for unordered_(multi)map

either unordered_(multi)set

. In fact, a useful guarantee of ordering unordered associative containers that support equivalent keys (use terms from the standard) is that records with an equivalent key are always contiguous, for example. AACBBBD or BBBAADC are valid orders, but ABACBBD are not. It is for this reason that these containers support the operation equal_range

, just like their sorted cousins. Even then (in C ++ 11)multimap

has a stronger guarantee for these records because they are not only contiguous, but also appear in insertion order, which might not be the case unordered_multimap

. In fact, for performance reasons, they may appear in reverse insertion order. But don't rely on that either ...

+1


source







All Articles