Suppose there is class Heavy with a bunch of user-defined compound class members. One of that, let's name it m_hashMap, has std::unordered_map<unsigned int, std::vector<CompoundClass>> structure. Let we have also void Heavy::foo() const; function which is reading all the members of Heavy traversing through all container members as well, including m_hashMap. The strange behavior that I met during running the code at different times is that m_hashMap is being traversed with different ordering in foo(), whereas the size and all the elements inside it were the same. No explicit hashing function was provided. What can be the reasons for such behavior?

CodePudding user response：

Two unordered_map can have different internal bucket layout even with the same set of elements. You can use the begin, end, bucket_count, bucket_size and bucket methods to monitor or determine whether the internal bucket layout of m_hashMap is the same in different execution. For example:

template <class T>
void printState(unordered_map<unsigned int, T> &m) {
    int n_buckets = m.bucket_count();
    for(int i = 0; i < n_buckets; i  ) {
        cout << "Bucket " << i << ": ";
        for(auto iter = m.begin(i), enditer = m.end(i); iter != enditer; iter  ) {
            cout << iter->first << " ";
        }
        cout << "\n";
    }
}

printState(m_hashMap);

CodePudding user response：

The internal representation of an unordered_map is its own business, and it can rebalance itself (or whatever else it likes to do) when it sees fit, even while appearing const to the outside.

As the name says, you cannot rely on the order being stable. The mere execution of an iteration (or a search) can trigger a change in the internal representation that results in a different perceived 'order'.

If you are relying on an order, you need to use an ordered map.