unordered_set 和迭代器的 C++ 设计问题

Question

我有以下片段

template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
  std::hash<T> hasher;
  seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

const size_t INF(numeric_limits<size_t>::max());

class nodehasher;

class node{

public:
  int x,y;
  unordered_set<node, nodehasher>::iterator neighbs[6];  //Issue Here
  node(){}
  node(int x_, int y_):x(x_),y(y_){}
  void set(int x_, int y_){x = x_,y = y_;}
  bool operator == (const node &n)const{
    return x == n.x && y == n.y;
  }
};

class nodehasher{
  std::size_t operator()(node const& n) const{
    std::size_t seed = 0;
    hash_combine(seed, n.x);
    hash_combine(seed, n.y);
    return seed;
  }
};

我似乎在声明迭代器指向节点本身内部的类节点时遇到问题。

这会导致大量过于冗长的错误。

现在我意识到我可以创建我的 neighbs 数组，一个指向节点的指针数组，但出于显而易见的原因，我想避免使用指针

我使用它的典型简化方式是:

unordered_set<node, nodehasher> nodes;
void typical_use(node dest){
  auto src_node = node(0,0);
  int neighbcount = 0;
  auto iter = dest.insert(node).first;
  src_node.neighbs[neighb_count] = iter; 
}

我显然可以将其转换为指针并执行以下操作:

src_node.neighbs[neighb_count] = &(*iter);

但是有没有办法避免指向我想做的事情呢？

编辑:

正如许多评论和答案所指出的那样，指向容器元素的指针和迭代器在重新散列后都会失效所以存储它们是个坏主意。

我在想，如果下面的方法代替节点的 unordered_set 起作用，我将使用指向节点的 unordered_set 指针，就像这样

unordered_set<shared_ptr<node> > nodes;

此外，如果我知道节点数总是少于 500，我可以放弃整个哈希表的想法并使用数组，每次我都必须搜索数组以检查节点是否是已经在那里了。

能否请您指出哪种方法更好？

Answer 1

标准容器需要完整的值类型。 node在您使用它来实例化 unordered_set<node, nodehasher> 时不是完整类型.

你可以使用 Boost.Container ，因为它们允许不完整的类型，但我在那里看不到散列容器(所以你必须使用 set )。

不过，您应该小心存储迭代器，因为至少对于 unordered_来自标准库的容器，它们可能会在重新散列。引用(和指针)不会失效。