c++ - 如何将结构属性转换为 C++ 中的指针引用？

Question

我有一个 JSON 格式的 DAG，其中每个节点都是一个条目：它有一个名称和两个数组。一个数组用于其他带有箭头的节点，另一个数组用于该节点指向的节点（传出箭头）。

因此，例如：

{ 
  'id': 'A',   
  'connected_from' : ['B','C'],  
  'connects_to' : ['D','E']
}

我有这些节点的集合，它们一起形成了一个 DAG。

我想将节点映射到一个结构来保存这些节点，其中 id 只是一个字符串，我希望数组成为这个结构的指针向量：

struct node { 
    string id;  
    vector<node*> connected_from;
    vector<node*> connected_to;
}

如何将 JSON 数组中的节点条目作为“id”转换为指向包含该节点的正确结构的指针？

一种明显的方法是构建一个键值对映射，其中 key = id，value = 指向具有该 id 的结构的指针，然后进行查找 - 但有更好的方法吗？

score 2 · Accepted Answer

不，仅考虑您提供的信息没有更好的方法：您需要构建地图。

但是，对于单个字母 id，映射可能采用简单数组的形式，例如 26 个英文字母条目。

score 1 · Accepted Answer

将有一些容器对象保存所有节点（否则您将泄漏它们。）您始终可以扫描容器以找到节点。但这将是低效的 - O(N^2) 而地图查找将是 O(N log N )。

虽然如果您将对象按排序顺序存储在容器中（或使用排序容器），您可以将这两种情况减少到 O(N log N)。

但是常数会有所不同，因此对于小图，扫描可能会更快。

score 1 · Accepted Answer

我认为您的建议很好...从 ID 映射到节点。它简单、直观且足够快，足以满足实际用途。考虑到数据是从 JSON 解析的，您的存储和查找不会显着影响性能。如果您真的很担心，请实施字典来替换您的地图。

一般来说，我总是提倡完成工作的最简单、最干净的方法。太多人沉迷于算法中的内存或性能损失，而他们代码中的实际瓶颈在其他地方。

3 回答 3