Поиск вхождения векторов в другой вектор без вложенных циклов

Question

У меня есть часть кода, которую я переношу из Fortran в C++, и я хотел бы избежать некоторых из вложенных структур цикла, которые мне пришлось создать в исходный код F77.

Проблема заключается в следующем: у меня есть вектор объектов, называемых узлами, каждый из которых содержит вектор, содержащий (среди других важных сведений) индексы других объектов узла, к которым каждый подключен (граф соединений). Как это

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

EDIT Как говорит Джерри 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 
    } 
} 

ДРУГОЙ EDIT
Об эффективности - это зависит от того, что является доминирующая операция. Количество исполнений части, описанной как «do stuff here», не будет меняться. Разница в момент прохождения вашей коллекции:

1. Ваш исходный код - nodeListA.size()^2 * [средний размер conNode]
2. Мой первый раствор - nodeListA.size() * журнал (nodeListA. размер()) * [средний размер conNode]
3. После Джерри Coffin предложение - nodeListA.size()^2 * [среднее количество интересных элементов conNode]

Таким образом, кажется, что set_intersection использование не помогает в этом случае.

Answer 2

Я предлагаю использовать словарь (O (log n) один, например std::set, или лучше, на основе хэша, например std::unordered_set из C++ 11) для nodeListA. Ниже приведен пример кода C++ 11.

#include <unordered_set> 
#include <vector> 

struct Node { 
    std::vector<int> conNode; 
}; 

int main() 
{ 
    std::vector<Node>  listOfNodes; 
    std::unordered_set<int> nodeListA; 

    for (int node_id : nodeListA) 
    for (int connected_id : listOfNodes[node_id].conNode) 
     if (nodeListA.find(connected_id) != end(nodeListA)) 
     /* Do stuff here.. */ 
      ; 

    return 0; 
} 

Преимущество использования std::unordered_set является то, что взгляд окна (то есть поиск для данного узла-ид) очень быстро. Однако реализация, включенная в стандартную библиотеку, может быть не очень быстрой. Редкий хэш и плотная хеш-версия Google является альтернативой, которая обеспечивает тот же интерфейс и, как известно, очень хороша для большинства целей: http://code.google.com/p/sparsehash/

В зависимости от того, что вы хотите сделать с результирующими узлами, может быть возможно заменить внутренний цикл вышеуказанного кода с алгоритмом STL.Например, если вы хотите поместить все узлы, определенные с помощью алгоритма в векторе, можно закодировать его следующим образом (используйте это в качестве замены для обеих петель вместе):

std::vector<int> results; 
for (int node_id : nodeListA) 
    std::copy_if(begin(listOfNodes[node_id].conNode), 
       end(listOfNodes[node_id].conNode), 
       back_inserter(results), 
       [&nodeListA](int id){return nodeListA.find(id) != end(nodeListA);}); 

Опять же, это C + Синтаксис +11; он использует аргумент лямбда как функцию.