c++ - 双向链表指针的双向链表 vector

Question

我有一个包含双向链表的 vector (即 std::vector )，然后每个双向链表将包含指向 vector 中另一个双向链表的指针。

这是我正在谈论的例子:

假设我们有以下双向链表 vector ，{ {1,2,0} ,{0,2,1,5}, {2,1,0,4,5} ,{4, 5,1,0}, {5,4} }。

让我们看一下 vector {1,2,0} 中的第一个双向链表。我想要的是 1 指向列表 {1,2,0} 和 2 指向列表 {2,1,0,4,5} 和 0 指向 {0,2,1,5} vector 中的其他列表也是如此。

除了拥有这种结构之外，如果我们排列 vector 的元素，我还需要指向正确列表的指针。

所以，比如说，如果在上面的例子中我交换 vector 中的前两个列表，它给出:

{ {0,2,1,5},{1,2,0},{2,1,0,4,5},{4,5,1,0},{5,4} }

我仍然希望在列表 {1,2,0} 中，1 指向 {1,2,0}，2 指向 {2,1,0,4,5}，0 指向 {0,2 ,1,5}。

所以我能够实现每个部分，直到最后一部分。

到目前为止，我在这部分所做的是，在排列之前，我可以让每个列表中的所有 0 都指向 &vector[1]，然后在排列之后，我必须遍历每个列表中的每个元素找到 0 并将它们指向 0 的新位置，因此它们会指向 &vector[k]。

问题是我必须在每个列表中搜索 0，但我不想进行搜索。那么有没有办法不用搜索就可以实现呢？ (代码为C++)

Answer 1

除了您描述的问题之外，将结构直接存储在 vector 中的另一个问题是 vector 上的某些操作会使指向该 vector 的部分或所有现有指针无效。即从 vector 中删除或插入元素。

通常，在这种情况下，vector 最好存储指向对象的指针，而不是对象本身。在您的示例中，一个 std::vector< DoublyLinkedList *>会更好地工作。您的 DoubleLinkedList 的各种实例可以直接存储指向彼此的指针，并且在 vector 中四处移动指针不会对其有效性产生任何影响。

当然，这个解决方案还有一些其他的问题需要解决，比如堆管理，这些都需要解决。但那将是一个不同的问题。