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

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

问题是：我有一个称为节点的对象向量，每个对象都包含一个向量（除其他重要信息外），该向量保存每个节点所连接的其他节点对象的索引（连接图）。像这样

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
            }
        }
    }
}

有一种更简单的方法可以做到这一点。看来我把这种方式变得太复杂了。如何使用标准算法库简化此代码？

最佳答案

如果您的变量应表示一组值，请使用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
    }
}

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


您的原始代码-nodeListA.size（）^ 2 * [平均conNode大小]
我的第一个解决方案-nodeListA.size（）* log（nodeListA.size（））* [平均conNode大小]
在杰里·科芬（Jerry Coffin）建议之后-nodeListA.size（）^ 2 * [有趣的conNode元素的平均数量]


因此，在这种情况下，使用set_intersection似乎无济于事。