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_来自标准库的容器，它们可能会失效 重新散列。引用(和指针)不会失效。