为什么我不能用std::unordered_map替换std::map？

Question

这个问题可能有点含混不清，因为我在家里没有代码可用，但我知道如果不解决它，整个周末都会困扰着我。

当我尝试将一些代码更新到C++11时，我开始用std::unordered_map替换一些std::map。该代码仅使用std::map::find()来访问映射中的特定元素，因此我认为替换应该很容易。返回的迭代器存储在一个auto类型的变量(auto res = map.find( x ))中，因此类型检查应该良好。然而，当我使用res->second.do_stuff()访问存储的元素时，我得到了一个编译器错误，告诉我struct std::pair<char, B>没有成员second。现在这真的让我困惑了，但不幸的是，我没有时间进一步调查。

也许这已经足够提供信息，以便有人可以给我一些关于这个奇怪的编译器错误的提示了。或者我的理解std::map 和 std::unordered_map应该具有相同的接口，除了需要排序的部分不正确吗？

编辑:

正如我承诺的那样，在这里对问题进行了更多分析。现在很可能有人可以更好地帮助我解决了。从评论中的提示，我猜测这不是由我访问映射中的元素引起的，而是由代码的其他部分引起的。我发现的原因是，我在Class X内使用map来存储指向Class X的其他元素的指针(一种类似树形结构)。然而，这似乎适用于std::map，但不适用于std::unordered_map。这里有一些非常简单的代码，展示了这个问题:

#include <stdint.h>
#include <unordered_map>
#include <map>

class Test {
  std::map<uint32_t, Test> m_map1; // Works
  std::unordered_map<uint32_t, Test> m_map; // gives error: ‘std::pair<_T1, _T2>::second’ has incomplete type
};

int main() {
  return 1;
}

std::map可以工作，但std::unordered_map不能工作。 有什么想法是为什么会这种情况，或者如何使其与std::unordered_map一起工作？

- LiKao

---

界面大致相同，但您需要确保您的键类型具有可哈希性，而不仅仅是可比较的。 - ildjarn

您能否提供一个最小化的示例来展示问题？ - Karl Knechtel

你的意思是它不工作吗？std::unordered_map：http://ideone.com/P2XUa std::map：http://ideone.com/etuCH - Gene Bushuyev

@GeneBushuyev：实际上，我试图重新构建的代码更加复杂，其中有几个在模板中具有依赖性的typedef。所以可能是其中一个地方出错了，导致编译器混淆并输出愚蠢的错误消息之类的...不幸的是，我现在无法从我的头脑中重现一个例子。我尝试稍微修改你的代码以符合我正在做的事情，但我没有得到相同的错误。我猜我必须等到星期一了 :(。 - LiKao

你的代码在我的MSVC 2010上编译正常。 - Werner Henze

Answer 1

我猜测是因为std::unordered_map需要重新哈希，因此需要复制元素，所以类型必须完整，而map只使用指向元素的指针，所以不会出现这个问题。

解决方案是将unordered map映射到指针：

std::unordered_map<uint32_t, std::shared_ptr<Test> >. 

- small_duck

---

是的，完全正确。不幸的是，我还没有时间写一个更详细的解释，所以我会让你来得到这个功劳 ;-）。此时需要注意的另一件事是，这两行代码都是无效的。正如在http://drdobbs.com/184403814中解释的那样，STL集合永远不允许不完整的类型，所以代码在之前就是无效的，但编译器从未捕获到这一点。这可能是那些未定义行为通常不会伤害你的情况之一，但你不能确定。至少现在我们是安全的。 - LiKao

Answer 2

同时使用 map 和 unordered_map 与不完全类型存在未定义行为：

特别地，在以下情况下效果是未定义的：

[...]

— 如果在实例化模板组件时将不完全类型（3.9）用作模板参数，除非该组件明确允许这样做。

- Yakov Galka

---

那个引用出自哪里？ - Ralph Tandetzky

@RalphTandetzky：从C++标准库的要求部分来看，我认为它自C++98以来就一直存在。 - Yakov Galka

如果编译器能够生成良好的错误消息并在这种情况下不生成工作代码（不完整类型的容器），那将是很好的。我们无法确保我们的代码明天在另一个编译器/版本上能够正常工作。 - Renaud

@Renaud：这是关于未定义行为是好还是坏的更广泛讨论的一部分。有时候，您不在意将代码移植到其他平台，但利用您的实现知识进行一些操作是有用的。例如，有用的struct Tree { std::list<Tree> children; };在我的工具链上可以正常工作，但按照您所说的方式执行会失败。另一个例子是将指针强制转换为非POD类型，其内存布局我知道是相同的，但从技术上讲这是未定义行为。 - Yakov Galka