递归unordered_map

Question

我有一个树结构，内部使用无序映射。

#include <unordered_map>

struct Node {
        std::unordered_map<int, Node> children;
};

int main() {
        Node a;
}

它在Apple clang 11.0.3和MSVC v19.24上运行良好，但无法在clang 10.0.0和gcc 10.1上编译。

而常规的std::map在所有编译器上都能正常工作。我没有找到造成这种差异的原因。有什么方法可以使用std::unordered_map作为自己的值吗？还是指针是这里唯一的解决方案？

下面是编译器资源管理器链接https://godbolt.org/z/6eYch9

下面是gcc的一个错误：

#3 with x86-64 gcc 10.1 In file included from /opt/compiler-explorer/gcc-10.1.0/include/c++/10.1.0/unordered\_map:43, from <source>:1: /opt/compiler-explorer/gcc-10.1.0/include/c++/10.1.0/bits/stl\_pair.h: In instantiation of 'struct std::pair<const int, Node>': /opt/compiler-explorer/gcc-10.1.0/include/c++/10.1.0/ext/aligned\_buffer.h:91:28: required from 'struct \_\_gnu\_cxx::\_\_aligned\_buffer<std::pair<const int, Node> >' /opt/compiler-explorer/gcc-10.1.0/include/c++/10.1.0/bits/hashtable\_policy.h:233:43: required from 'struct std::\_\_detail::\_Hash\_node\_value\_base<std::pair<const int, Node> >' /opt/compiler-explorer/gcc-10.1.0/include/c++/10.1.0/bits/hashtable\_policy.h:279:12: required from 'struct std::\_\_detail::\_Hash\_node<std::pair<const int, Node>, false>' /opt/compiler-explorer/gcc-10.1.0/include/c++/10.1.0/bits/hashtable\_policy.h:1973:13: required from 'struct std::\_\_detail::\_Hashtable\_alloc<std::allocator<std::\_\_detail::\_Hash\_node<std::pair<const int, Node>, false> > >' /opt/compiler-explorer/gcc-10.1.0/include/c++/10.1.0/bits/hashtable.h:173:11: required from 'class std::\_Hashtable<int, std::pair<const int, Node>, std::allocator<std::pair<const int, Node> >, std::\_\_detail::\_Select1st, std::equal\_to<int>, std::hash<int>, std::\_\_detail::\_Mod\_range\_hashing, std::\_\_detail::\_Default\_ranged\_hash, std::\_\_detail::\_Prime\_rehash\_policy, std::\_\_detail::\_Hashtable\_traits<false, false, true> >' /opt/compiler-explorer/gcc-10.1.0/include/c++/10.1.0/bits/unordered\_map.h:105:18: required from 'class std::unordered\_map<int, Node>' <source>:4:39: required from here /opt/compiler-explorer/gcc-10.1.0/include/c++/10.1.0/bits/stl\_pair.h:218:11: error: 'std::pair<\_T1, \_T2>::second' has incomplete type 218 | \_T2 second; ///< The second member | ^~~~~~ <source>:3:8: note: forward declaration of 'struct Node' 3 | struct Node { | ^~~~ Compiler returned: 1

Answer 1

STL容器不需要处理不完整的类型。如果你不介意额外的间接，那么解决办法是std::map<int, std::unique_ptr<Node>>

Answer 2

这和做同样的问题。

struct Node
{
    Node child;  // An instance of the full structure
};

在完全定义结构(或类)之前，不能使用它，这是在关闭}时使用的。

但是，您可以定义指向结构的指针，因为编译器不需要完整的结构定义，只知道结构的名称：

struct Node
{
    Node* child;  // Pointer to the structure
};

因此，要解决您的问题，需要一张指针图。

std::unordered_map<int, Node*> children;

Answer 3

在编写Trie数据结构时，我注意到在最新的clang (v14)和GCC (v12)中，我没有得到错误，我的代码按照预期操作，但是在这些版本(在godbolt.com上)下面的任何内容，我都会得到相同的错误。这都是使用-std=c++14的，所以它不应该与标准相关。