对于类图结构最好的迭代器想法是什么？

Question

我正在实现一个图形结构。

struct Node {
  std::vector<size_t> neighbours;  // returns the index of node in Graph::nodes
  // ... node info
};

class Graph {
  std::vector<Node> nodes;  // adjacency list
};

我想创建一个结构体，用户可以用它迭代

Graph

。第一种方法是显而易见的（我不使用

std::vector<Node>::iterator

，因为可以重新分配）。

class Iterator {
  size_t id;
  Graph* ptr;  // access via ptr->nodes[id]
};

但是，用户可以进行

std::move(graph)

操作（例如

std::vector<Graph>

重新分配），然后所有

Iterators

都将失效。此外，使用原始指针对我来说被认为是一种不好的做法。

问题：拥有某种稳定的

Iterators

到

graph

的解决方案是什么？

我不希望用户拥有

size_t

变量

id

而不是

Iterator

，他会将其传递给某些

Graph

方法（例如

graph.neighbours(node_id)

）。

我唯一的想法是在

Graph

之外的某个地方创建一个内存盒，在

Graph

中存储指向该盒的指针，并在盒中存储指向

graph

的指针。然后，每当有人

std::moves

graph

时，我们都会更新盒子的指针。而无论谁获得了指向盒子的指针，总能获得

graph

的当前地址。所以，它看起来像this：

class Graph {
  std::vector<Node> nodes;  // adjacency list
  my::Stalker<Graph> self;
};

class Iterator {
  size_t id;
  my::Stalker<Graph>::stalker ptr;  // access via ptr.ref().nodes[id]
};

但是，有些事情告诉我，我做了一些过度设计或错过了更好的解决方案。我想要一个专业的解决方案（如果存在）或者只是一些批评者。

Answer 1

通常的解决方案是

graph

将其

Node

存储在不会使迭代器无效的数据结构中，例如

unordered_set

或

list

。由于迭代器永远不会失效，所以所有这些问题都会消失。

如果你真的不想这样，那么下一个解决方案是给每个

Node

某种

NodeId

（可以是

size_t

，或其他任何东西，然后图表必须提供某种方式通过

Node

快速获取

NodeId

。然后您还可以自定义

iterator

，它可以迭代

NodeId

，并获取当前

Node

的

NodeId

。