unordered_map更改的顺序

我很好奇这种行为。我发现，分配一个unordered_map改变无序地图的内部顺序，而没有任何插入/缺失：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正在利用副本将新地图重新散列为更优化的安排。但是，我尝试在m2上重新分配新地图（m3），m2的顺序不保留为m3。

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

我的编译器是苹果LLVM版本8.1.0（铛-802.0.42）

来源

2017-08-10 Gonzalo Solera

我喜欢你认识到没有内部o的部分一个*无序*地图....然后仍然奇怪为什么订单不一致 – CoryKramer

@CoryKramer这是一个很好的问题，但。问题是为什么后备存储未被复制*原样*;为什么重新安排？ – Justin

@Justin如果答案只是“支持存储是实现定义的，因此没有人能给你一个比随机猜测或实现具体细节更好的答案”我们应该如何处理这些信息？ – CoryKramer

这是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的元素插入此向量中。

这意味着，当你这样做：

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）

来源

2017-08-10 18:23:22 Justin

在wandbox上试用它，我的“等效代码”并不完全等效：https：//wandbox.org/permlink/byubQ9VEU9UPCcsf。这可能只是* libC++ *的不同版本，或者完全不同的标准库 – Justin

因为这显然是实现特定的（它是一个无序地图毕竟）我要做出一个受过教育的投机。

如果mark和john具有相同的哈希值并且相关的桶数相互冲突，并且实现使用链接，我们可能可以解释这一点。如果链接实现在前面插入新项目（即使对于单链表也是恒定的时间），那么每次分配容器时，链接项目顺序都将被交换。

来源

2017-08-10 17:38:55

我觉得'mark'和'john'会有相同的散列，而且如果是这样，这个问题应该通过使用不同的字符串消失，这似乎并不是这种情况（例如https://wandbox.org/permlink/hFVcM6fuLAG72rzx）。当然，不同的字符串可能会发生碰撞，但不应该很难找到不会碰撞的字符串。 – Justin

unordered_map更改的顺序

回答

相关问题