分配时unordered_map的顺序更改 [英] Order of unordered_map changes on assignment

问题描述

我对此行为很好奇.我发现分配unordered_map会更改无序映射的内部顺序，而不会进行任何插入/删除:

I'm curious about this behaviour. I found that assigning an unordered_map changes the internal order of the unordered map, without any insertion/deletion:

unordered_map<int, string> m1;
unordered_map<int, string> m2;
unordered_map<int, string> m3;

m1[2] = "john";
m1[4] = "sarah";
m1[1] = "mark";

m2 = m1;
m3 = m2;

for(auto it = m1.begin(); it != m1.end(); ++it) {
    cout << it->second << " ";
}
cout << endl;
for(auto it = m2.begin(); it != m2.end(); ++it) {
    cout << it->second << " ";
}
cout << endl;
for(auto it = m3.begin(); it != m3.end(); ++it) {
    cout << it->second << " ";
}
cout << endl;

输出:

mark sarah john 
john sarah mark 
mark sarah john

我知道unordered_map上没有任何特定的顺序，这是因为内部是一个哈希表，因此元素插入可以在任何地方结束，并且重新哈希将所有元素混合在一起.

I know that there isn't any specific order maintained on an unordered_map due to the fact that internally is a hash table, so an element insertion can end anywhere and a re-hash will mix it all.

但是，这里的顺序在分配后就改变了.我希望顺序是一样的，因为我认为它只会复制底层存储.

However, here the order is changing just after an assignment. I expected the order to be the same, as I thought it would just copy the underlying storage.

我认为的第一个解释是unordered_map可能正在利用副本将新地图重新哈希化为更优化的布局.但是，我尝试在m2的新地图(m3)上重复分配，并且m2的顺序未保留在m3中.

The first explanation I thought was that maybe unordered_map is taking advantage of the copy to re-hash the new map into a more optimal arrangement. However, I tried to repeat an assignment on a new map (m3) from m2 and the order of m2 is not preserved in m3.

为什么分配地图会改变顺序?

Why does assigning the map change the order?

我的编译器是Apple LLVM版本8.1.0(clang-802.0.42)

My compiler is Apple LLVM version 8.1.0 (clang-802.0.42)

推荐答案

这是 libc ++的实现细节:

    _LIBCPP_INLINE_VISIBILITY
    unordered_map& operator=(const unordered_map& __u)
    {
#ifndef _LIBCPP_CXX03_LANG
        __table_ = __u.__table_;
#else
        if (this != &__u) {
            __table_.clear();
            __table_.hash_function() = __u.__table_.hash_function();
            __table_.key_eq() = __u.__table_.key_eq();
            __table_.max_load_factor() = __u.__table_.max_load_factor();
            __table_.__copy_assign_alloc(__u.__table_);
            insert(__u.begin(), __u.end());
        }
#endif
        return *this;
    }

^{来自libc ++的 unordered_map 标头}

如果我们假设您使用的是C ++ 11或更高版本，则这基本上可以通过清除旧的哈希表，然后将__u的元素插入此向量中来实现.

If we assume you are using C++11 or greater, then this basically works by clearing the old hashtable, then inserting the elements of __u into this vector.

这意味着当您这样做时:

That means that when you do:

m2 = m1;

它大致等效于以下代码:

It's roughly equivalent to the following code:

m2.clear();
m2.max_load_factor(m1.max_load_factor());
m2.insert(m1.begin(), m1.end());

当您使用 libstdc ++ 作为其operator=的实现时，不会发生这种情况只是= default(请参阅libstdc ++的

This doesn't happen when you use libstdc++, as its implementation of operator= is just = default (see libstdc++'s unordered_map header)

这篇关于分配时unordered_map的顺序更改的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！