c++ - 在没有嵌套 for 循环的情况下查找另一个 vector 中 vector 条目的出现

Question

我有一段代码要从 Fortran 迁移到 C++，我想避免在原始 F77 代码中必须创建的一些嵌套 for 循环结构。

问题是这样的:我有一个称为节点的对象 vector ，每个节点都包含一个 vector ，其中包含一个 vector (除其他重要信息外)每个节点对象所连接的索引(连接图)。像这样

struct Node {
    vector<int> conNode;
};
vector<Node> listOfNodes;
vector<int> nodeListA;    // a subset of nodes of interest stored as their vector indices

我需要查找与 nodeListA 中的节点相连的节点，但前提是这些节点也在 nodeListA 中。现在，我的代码看起来像这样:

// Loop over the subset of node indices
for (int i=0; i<nodeListA.size(); i++) {
    // Loop over the nodes connected to the node i
    for (int j=0; j<listOfNodes[nodeListA[i]].conNode.size(); j++) {
        // Loop over the subset of node indices again
        for (int k=0; k<nodeListA.size(); k++) {
            // and determine if any of node i's connections are in the subset list
            if (nodeListA[k] == listOfNodes[nodeListA[i]].conNode[j]) {
               // do stuff here
            }
        }
    }
}

必须有一种更简单的方法来做到这一点。看来我让这种方式太复杂了。我怎样才能简化这段代码，可能使用标准算法库？

Answer 1

如果您的变量应该表示一组值，请使用 std::set 而不是 std::vector。那么你将拥有

typedef std::set<int> SetOfIndices;
SetOfIndices setOfIndices; // instead of nodeListA
for(SetOfIndices::const_iterator iter = setOfIndices.begin(); iter != setOfIndices.end(); ++iter)
{
    Node const & node = listOfNodes[*iter];
    for (int j = 0; j < node.conNode.size(); ++j)
    {
        if (setOfIndices.find(node.conNode[j]) != setOfIndices.end())
        {
            // do stuff here
        }
    }
}

编辑 正如 Jerry Coffin 所建议的，std::set_intersection 可以在外循环中使用:

struct Node {
    SetOfIndices conNode;
}
typedef std::set<int> SetOfIndices;
SetOfIndices setOfIndices; // instead of nodeListA
for(SetOfIndices::const_iterator iter = setOfIndices.begin(); iter != setOfIndices.end(); ++iter)
{
    Node const & node = listOfNodes[*iter];
    std::vector<int> interestingNodes;

    std::set_intersection(setOfIndices.begin(), setOfIndices.end(),
                      node.conNode.begin(), node.conNode.end(),
                      std::back_inserter(interestingNodes));

    for (int j = 0; j < interestingNodes.size(); ++j)
    {
        // do stuff here
    }
}

另一个编辑
关于效率——这取决于什么是主导操作。被描述为“在这里做事”的部分的执行次数不会改变。区别在于遍历集合的时间:

1. 您的原始代码 - nodeListA.size()^2 * [平均节点大小]
2. 我的第一个解决方案 - nodeListA.size() * log(nodeListA.size()) * [平均节点大小]
3. 根据 Jerry Coffin 建议 - nodeListA.size()^2 * [有趣的 conNode 元素的平均数量]

所以看来 set_intersection 使用在这种情况下没有帮助。