unordered_multimap element output order is weird-CodePudding

We know that unordered_multimap does not sort elements.(Probably...I'm Noob:) So the order of elements in unordered_multimap is by order of input. Now I inputed 5 simplest letter that A,B,C,D,E. First please guess elements output in which order? Is same at input order A B C D E? Is the reverse of input order E D C B A? It is ridiculous E D C A B!!! I tested many input. Alaways reverse order and the last two elements is order. I can't understand it.

    int main()
{
    unordered_multimap<char, int> window;
    window.insert(make_pair('A',1));
    window.insert(make_pair('B',1));
    window.insert(make_pair('C',1));
    window.insert(make_pair('D',1));
    window.insert(make_pair('E',1));
    for (unordered_multimap<char, int>::iterator it = window.begin(); it != window.end(); it  )
        cout<<it->first<<endl;
    return 0;
}

CodePudding user response：

the order of elements in unordered_multimap is by order of input

NOPE! The name is unordered; there is no useful, predictable ordering involved at all. Under the hood, they're implemented as hash tables, and the nature of hash tables means that the iteration ordering depends on the hash values of the keys (which are frequently unrelated to their sort order), the size of the underlying table (which resizes as more keys are inserted) and the order in which keys were inserted or deleted. The hashing rules for most built-in types are implementation-defined, so they'll change from compiler to compiler.

Don't rely on any ordering in unordered_map; if you need ordering, you'll have to impose it yourself, or use third-party hash table structures similar to Java's LinkedHashMap that integrate a linked list structure with a hash table to get insertion-ordered iteration.

CodePudding user response：

refer to unordered_multimap

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.

By the way, because unordered_multimap supports equivalent keys, the storage order of the same key is not guaranteed to be ordered.

The iteration order of this container is not required to be stable (so, for example, std::equal cannot be used to compare two std::unordered_multimaps), except that every group of elements whose keys compare equivalent (compare equal with key_eq() as the comparator) forms a contiguous subrange in the iteration order, also accessible with equal_range().