我有一个类似网络的数据结构，由连接在一起的节点组成。其编号将发生变化的节点将以无特定顺序存储在std::vector<Node>中，其中Node是合适的类别。指针或索引？

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

应该Link包含

两个指针中的两个节点？
两个整数，用作std::vector<Node>的索引？
或者我应该采用不同的系统（为什么？）

第一种方法，虽然可能会更好，是因为指针将在每次添加或删除网络节点的时间来进行再生问题，但另一方面，这将使我摆脱困境将节点存储在随机存取容器中。

2014-09-02 MarcDuQuesne

请指定所需的性能和相对频率：1.添加节点2.删除节点3.添加链接4.删除链接。还请指定是否需要对节点进行任何操作，例如排序以及为什么您需要在随机访问容器中使用它们。 – 2014-09-02 13:59:49

如果节点没有排序，并且您确定只会推到节点向量的末尾，那么索引将保持有效，我会使用索引。这是少了一件错误的事情。或者，有一个指向节点的指针向量，而不是节点本身。然后，您可以按照您喜欢的方式重新排列矢量，并且节点不会移动。 – 2014-09-02 14:06:02

节点将被删除并添加相同的频率，低于我添加或删除链接的频率。我并不需要随机访问容器中的节点或链接，也不需要对它们进行排序。 – MarcDuQuesne 2014-09-02 14:07:36

我会添加一个（或一些）link指针到您的节点类，然后手维护链接。这将节省您不得不使用额外的容器。

如果你正在寻找一些更结构化的东西，你可以尝试使用Boost Intrusive。这有效地以更普遍的方式做同样的事情。

来源

2014-09-02 14:01:33 doron

谢谢 - 我会看看你建议的图书馆。 – MarcDuQuesne 2014-09-02 14:13:20

指定要使用或创建的类的接口。编写单元测试。做最简单的事情来完成单元测试。

所以它取决于类的接口。例如，如果Link不导出有关节点的信息，那么选择什么方法并不重要。另一方面，如果你去指点，请考虑std::shared_ptr。

来源

2014-09-02 14:02:35 TobiMcNamobi

这一般很难回答。有各种性能和易用性的折衷。

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

link.first->value

与

nodes[link.first].value

使用指针可提供比指数更好或更差的表现。这取决于各种因素。您需要进行测量以确定您的情况哪个更好。

如果您可以保证只有一定数量的节点，则使用索引可以节省空间。然后，您可以为索引使用较小的数据类型，而无论您拥有多少个节点，指针总是需要使用完整的指针大小。通过允许更多链接适合单个缓存行，使用更小的数据类型可以带来性能优势。

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

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

使用索引将允许您执行边界检查，这可能会更容易找到一些错误。

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

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

来源

2014-09-02 14:05:56

可以避开Link类共有如果你使用：

struct Node 
{ 
    std::vector<Node*> parents; 
    std::vector<Node*> children; 
};

通过这种方法，

避免创建另一个类。
您的记忆需求会降低。
您必须减少遍历Node s的网络的指针遍历。

下滑。您必须确保：

创建或移除链接时，您必须更新两个对象。
当您删除Node时，必须从其parents和children中删除指向它的指针。

来源

2014-09-02 14:26:30

我猜这在我的情况下不起作用 - 因为我写了一个链接包含其他信息 - 让我们说一个颜色，一个能源等。所以编写一个类可能是最简单的方法。内存不是问题。而且，我可能必须明确地循环所有链接。 – MarcDuQuesne 2014-09-02 14:30:15

您可以将其设置为std::vector<Node *>而不是std::vector<Node>并使用new分配节点。

然后：

您可以存储指针在Link类的节点，而不必担心他们成为失效
您仍然可以随机地访问他们的节点矢量。

当你从节点列表中删除它们时，你需要记住delete。

来源

2014-09-02 14:56:32

@Alex是否值得这取决于你的'new'和'delete'是如何实现的。 – 2014-09-02 14:59:10

我个人对矢量图像结构的经验提出了这些不变量。

不要在载体中，其中其他类容纳一个指针/参考

你必须像数据结构的图形数据存储。如果代码不是性能关键的（这对性能非常敏感！），您不应该考虑缓存压缩数据结构。

如果你不知道你的图形将有多大，你都在矢量所有迭代器和指针失效了你的Node数据一旦你的矢量调用vector::reallocate()这意味着，你必须以某种具有再生你的整个数据结构，也许你必须创建一个全部的数据结构并使用dfs或类似的来调整指针。如果您想要删除某个矢量中间的数据，也会发生同样的情况。
如果你知道你的数据有多大，你会被设置为保持这种状态，否则一旦你重新考虑，你会头痛。

不要使用共享指针来跟踪需要被释放

如果你有这样的数据结构图和你对性能的关键路径删除它是不明智的调用删除时，您的算法决定什么他不再需要这些数据。一种可能性是在关键性能部分期间（如果您确实需要节省空间，您可以考虑指针标记）将数据保留在堆上（如果性能至关重要，则考虑池分配器）标记不再需要的对象，或者之后使用一些简单的标记和扫描算法来查找不再需要的项目（是的，图形算法是sutter说垃圾收集比智能指针更快的情况之一）。

请注意，延迟销毁对象意味着您将释放Node类中的所有类似RAII的功能。

来源

2014-09-02 21:29:58 Alex

指针或索引？

回答

不要在载体中，其中其他类容纳一个指针/参考

不要使用共享指针来跟踪需要被释放

相关问题