unordered_map 的相互依赖类型

Question

假设我想在条目之间保持一定的顺序 unordered_map 的。一种节省内存的方法似乎是在地图的条目之间保留一个链表。也就是说，我将使用 unordered_map 而不是 unordered_map，其中 Node 定义为

struct Node {
  int val;
  typename std::unordered_map<int, Node>::iterator up;
};

这是有效的 C++ 吗？ Clang 和 gcc 不允许这种说法 Node is an incomplete type。请参阅下面的完整错误消息。双方都接受以下内容：

template<typename Key, typename Value>
struct Map {
  struct MapEntry {
    Key key;
    Value val;
    MapEntry *prev, *next;
  };

  using Iterator = MapEntry*;
};

struct Node {
  int val;
  Map<int, Node>::Iterator up;
};

这里的规则是什么？为什么第一个不被接受，而第二个可以？在相关的中，出现了类似的问题，但是，要在此处应用相同的解释，必须是 unordered_map 包含一个没有任何间接寻址的 Value 对象。即 unordered_map 的定义应该是这样的：

template<typename Key, typename Value>
class unordered_map {
  Value val;
  using value_type = std::pair<const Key, Value>;
  using entry = std::tuple<value_type, entry*, entry*>;
  using iterator = entry*;
};

我不明白为什么 unordered_map 应该直接存储值。除此以外，就像我上面给出的玩具示例 struct Map 一样，没有依赖循环。

In file included from /usr/include/c++/8/unordered_map:43,
                 from test.cpp:1:
/usr/include/c++/8/bits/stl_pair.h: In instantiation of ‘struct std::pair<const int, Node>’:
/usr/include/c++/8/ext/aligned_buffer.h:91:28:   required from ‘struct __gnu_cxx::__aligned_buffer<std::pair<const int, Node> >’
/usr/include/c++/8/bits/hashtable_policy.h:234:43:   required from ‘struct std::__detail::_Hash_node_value_base<std::pair<const int, Node> >’
/usr/include/c++/8/bits/hashtable_policy.h:280:12:   required from ‘struct std::__detail::_Hash_node<std::pair<const int, Node>, false>’
/usr/include/c++/8/bits/hashtable_policy.h:2027:49:   required from ‘struct std::__detail::_Hashtable_alloc<std::allocator<std::__detail::_Hash_node<std::pair<const int, Node>, false> > >’
/usr/include/c++/8/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> >’
/usr/include/c++/8/bits/unordered_map.h:105:18:   required from ‘class std::unordered_map<int, Node>’
test.cpp:5:32:   required from here
/usr/include/c++/8/bits/stl_pair.h:215:11: error: ‘std::pair<_T1, _T2>::second’ has incomplete type
       _T2 second;                /// @c second is a copy of the second object
           ^~~~~~
test.cpp:3:8: note: forward declaration of ‘struct Node’
 struct Node {

Answer 1

唉，

struct Node {
  int val;
  typename std::unordered_map<int, Node>::iterator up;
};

根据 C++17 标准，

不是有效的 C++。向 std::vector、std::list 和 std::forward_list 提供不完整类型 Node 根据最近接受 incomplete types proposal 进入 C++17 是有效的，但是 unordered_map仍需提供完整类型

MSVC 和 libc++ 可以在不完整的值下正常工作，但这是因为它们超出了标准的要求。

unordered_map 的相互依赖类型

Codependent types with unordered_map

c++

stl

circular-dependency

libstdc++