c++ - 指针还是索引？

Question

我有一个类似网络的数据结构，由连接在一起的节点组成。 编号会改变的节点将存储在 std::vector<Node> 中。排名不分先后，其中 Node是一个合适的类。

我想跟踪节点之间的链接。同样，这些链接的数量会发生变化，我正在考虑再次使用 std::vector<Link> . Link类必须包含有关它连接的两个节点的信息，以及其他链接功能。

应该Link包含

1. 指向两个节点的两个指针？
2. 两个整数，用作 std::vector<Node> 的索引？
3. 或者我应该采用不同的系统(为什么？)

第一种方法虽然可能更好，但存在问题，因为每次我在网络中添加或删除节点时都必须重新生成指针，但另一方面，这将使我摆脱例如将节点存储在随机访问容器中。

Answer 1

一般来说这很难回答。存在各种性能和易用性权衡。

使用指针可以为一些操作提供更方便的用法。例如

link.first->value

对比

nodes[link.first].value

使用指针可能会提供比索引更好或更差的性能。这取决于各种因素。您需要进行衡量以确定哪种情况更适合您。

如果可以保证只有一定数量的节点，使用索引可以节省空间。然后，您可以为索引使用较小的数据类型，而对于指针，无论您有多少节点，您始终需要使用完整的指针大小。使用较小的数据类型可以在单个缓存行中容纳更多链接，从而提高性能。

使用索引复制网络数据结构会更容易，因为您不必重新创建链接指针。

拥有指向 std::vector 元素的指针可能容易出错，因为 vector 可能会在插入后将元素移动到内存中的另一个位置。

使用索引将允许您进行边界检查，这可能更容易发现一些错误。

使用索引使序列化更加直接。

综上所述，我经常发现指数是总体上最好的选择。索引的许多语法上的不便可以通过使用便捷方法来克服，并且您可以在指针具有更好性能的某些操作期间将索引切换为指针。