我对这种行为很好奇。我发现分配 unordered_map
会更改无序映射的内部顺序,而无需任何插入/删除操作:
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
没有维护任何特定的顺序,因为它内部是一个哈希表,所以元素插入可以在任何地方结束,重新哈希会混合它全部。
但是,这里的顺序在分配后立即发生变化。我希望顺序相同,因为我认为它只会复制底层存储。
我想到的第一个解释是 unordered_map
可能正在利用拷贝将新 map 重新散列为更优化的排列。但是,我尝试在 m2 的新 map (m3) 上重复赋值,但 m3 中未保留 m2 的顺序。
为什么分配 map 会改变顺序?
我的编译器是 Apple LLVM 版本 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; }
From libc++'s unordered_map header
如果我们假设您使用的是 C++11 或更高版本,那么这基本上是通过清除旧哈希表,然后将 __u
的元素插入到此 vector 中来实现的。
这意味着当你这样做时:
m2 = m1;
大致相当于下面的代码:
m2.clear();
m2.max_load_factor(m1.max_load_factor());
m2.insert(m1.begin(), m1.end());
当您使用 libstdc++ 时不会发生这种情况,因为它的 operator=
实现只是 = default
(参见 libstdc++ 的 unordered_map header)
关于c++ - 分配时 unordered_map 更改的顺序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45620007/