Кодозависимые типы с unordered_map - PullRequest
Новая
       43

Кодозависимые типы с unordered_map

1 голос
/ 20 июня 2019

Предположим, что я хочу сохранить определенный порядок между записями unordered_map,Эффективный для памяти способ сделать это - сохранить связанный список между записями на карте.А именно вместо того, чтобы иметь unordered_map, Я буду использовать unordered_mapгде Node определяется как 

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

Это допустимый C ++?Clang и gcc не допускают этого, говоря, что Node является неполным типом.Смотрите ниже полное сообщение об ошибке.Следующее принимается обоими: 

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 должен хранить значение напрямую.В противном случае, как в приведенном выше примере структуры игрушки 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 {

1 Ответ

1 голос
/ 20 июня 2019

Увы, 

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

является не действительным C ++ по стандарту C ++ 17. Предоставление неполного типа Node для std::vector, std::list и std::forward_list допустимо в соответствии с недавним принятием предложения неполных типов в C ++ 17, но unordered_map еще предстоит предоставляется с полными типами.

MSVC и libc ++ отлично работают с неполным значением, но это связано с тем, что они выходят за рамки требований стандарта.

...