C ++您可以设计一个数据结构，将指针保存在连续内存中并且不会使它们无效吗？

Question

我正在尝试为网格表示实现半边数据结构。我目前的障碍是，

对于此DS，您需要多个指针，可能的实现示例如下：

class HalfEdge {
        Edge * next;
        Edge * prev;
        Edge * pair;
        Vertex * vertex;
        Face * face;
}

这没什么错。但是，如果您使用指针（例如，我们使用智能指针而不是原始指针以避免指针出现已知问题），则数据现在稀疏地存在于内存中，并且由于缓存而导致性能下降。更糟糕的是，如果要将网格物体发送到GPU，现在必须序列化顶点，并想象必须在每一帧中都这样做！

因此，另一种选择是拥有数组，然后执行此操作：

// Somewhere else we have vectors of edges, faces and vertices
// we store their indices in the array rather than pointers.
class HalfEdge {
        uint next_index;
        uint prev_index;
        uint pair_index;
        uint vertex_index;
        uint face_index;
}

这与数组结合在一起，将使您可以将内容连续地保留在内存中，现在您可以将网格发送到gpu，而无需花费线性缓冲区的开销。但是，这存在语法问题。

在您可以执行face->field之前，您必须先执行face_array[face_index].field，这非常笨重。

天真地认为，将分配顶点和用于访问的指针结合起来是可行的，类似于Face* face = &face_array[index]，但是，任何有C ++经验的人都知道，指针在第二次调整数组大小时将变得无效。

不知道网格的潜在大小，无法预先分配数组，因此无法做到这一点。

基于以上所有，如果您想让内存变长，可以做得比face_array[index].field好吗？

Answer 1

假设您将成员存储在列表中，则可以执行以下操作：

class HalfEdge {
public:
  Edge& next() { return (*edge_list)[next_index]; }
  Edge& prev() { return (*edge_list)[prev_index]; }
  // ...
  // probably also const-qualified versions is a good idea

private:
  // or global if needed, or whatever
  std::vector<Edge>* edge_list;
  // ...

  std::size_t next_index;
  std::size_t prev_index;
  // ...
};

这将允许您访问本地范围内的值，例如

HalfEdge he = /* ... */;
auto& edge = he.next();  // which is otherwise equivalent to
auto& edge = edge_list[he.next_index];

本质上，这类似于您存储引用的想法，但是与其存储对可能失效的数据成员的引用，我们而是存储对实际数组的引用，并根据需要重新计算偏移量。