Какая наилучшая структура данных для поиска и подсчета пар объектов в векторе векторов

Question

Я определил class element и class node.

класс элемент

class element 
{ 
    int id; 
    std::vector<node> m_nodes; // An element consist of 4 nodes. 
    public: 
    getnode(int) // return n-th node;  
} 

класс узла

class node 
{ 
    int id; 
    // other members 
} 

class model состоят из целых node и element объектов. class element объект состоит из вектора из четырех node объектов. Пара двух последовательных (смежных) объектов node называется лицом.

Пример:
elem1: {1,2,3,4}
elem2: {3,5,6,4}
elem1 и elem2 два element объекты и целые числа в массиве представляют собой идентификаторы четыре узла.
1-2, 2-3, 3-4 и 4-1 являются гранями elem1. и 3-5, 5-6, 6-4 и 4-3 являются гранями elem2. лицо 3-4 и лицо 4-3 идентичны и, следовательно, разделяются обоими элементами.

Элемент границы - это элемент, состоящий из по меньшей мере одной грани, которая не разделяется другими элементами. В приведенном выше примере оба элемента elem1 и elem2 являются граничными элементами. В классе модели также определен вектор граничных элементов.

модель класса

class model  
{  
    std::vector<node> m_nodes; 
    std::vector<element>m_elements; 
    std::vector<element>m_boundary; 

    public: 
    void set_boundary_elements(); 
} 

ПРОБЛЕМА: Как инициализирует вектор граничных элементов
Это псевдокод из set_boundary_elements (функции).

void model::set_boundary_elements() 
{ 
    std::vector <std::pair<std::set<int> , int >> faces; 
    std::set<int> s; 
    for(auto iter::m_elements) 
    { 
     //initialise face. 
     for(int i=1; i<5; ++i) 
     { 
      if(i != 4) 
       { 
        s.insert(iter.getnode(i)); 
        s.insert(iter.getnode(i+1)); 
       } 
       else 
       { 
        s.insert(iter.getnode(4));s.insert(iter.getnode(1)); 
       } 
       for(auto it: faces) 
       { 
        if(s== it.first) 
         (it.second)++; break; 
       } 
       faces.push_back(s,1); 
     } 
     //then push_back the elements which have nonshared faces, into m_boundary. 
    } 
}    

Я считаю, что мой алгоритм неэффективен, поскольку для добавления лица каждый раз, когда мне приходится проходить через все грани. Есть ли какой-либо полезный метод в stl/algorithm для эффективного решения моей проблемы?

Answer 1

Пересмотрите свой дизайн. В настоящее время элементы на самом деле не разделяют узлы.Два элемента, которые должны совместно использовать узел, просто хранят разные данные, имеющие один и тот же идентификатор. Это означает, что если что-то изменит один узел, система может быть непоследовательной.

Вот мое предложение (без конструкторов, геттеров, сеттеров и так далее, при условии, что вы можете заполнить те легко):

class Model { 

    class Node; 
    class Element; 

private: 

    vector<Node> nodes; 
    vector<Element> elements; 

} 

class Model::Element { 
private: 
    Element(); //only to be created by Model 
    vector<unsigned int> incident_nodes; 
} 

class Model::Node { 
private: 
    Node(); //only to be created by Model 
    vector<unsigned int> incident_elements; 
} 

Обратите внимание, что оба узла и элементные детали магазин инцидента, и они делают это с целые числа, которые ссылаются на их идентификатор внутри векторов в модели. Модель отвечает за создание и изменение узлов и элементов, и такие методы будут нести ответственность за постоянное сохранение данных. Все общедоступные методы на элементе или узле являются постоянными.

Это дает вам стабильную систему, имеющую ссылки в обоих направлениях. Если вы хотите знать, если элемент находится на границе, код

//returns all entries that are in both vectors 
inline vector<unsigned int> intersection(const vector<unsigned int>& vector_a, 
    const vector<unsigned int>& vector_b); 

typedef vector<unsigned int> Face; //defined in model, a pair of node ids 

//number = 0..3, returns the corresponding face 
Model::Face Model::get_face(const unsigned int element_id, 
    const unsigned int number); 

vector<unsigned int> Model::incident_elements(const Face& face){ 
    return intersection(nodes[face[0]].incident_elements, 
     nodes[face[1]].incident_elements); 
} 

bool Model::is_boundary(const unsigned int element_id){ 

    //check if it has a face that is boundary 
    for (unsigned int i=0; i<4;i++){ 
     Face face = get_face(element_id, i); 
     if(incident_elements(face).size() == 1){ 
      return true; 
     } 
    } 
    return false; 
} 

(все упомянутые методы и функции должны быть понятны, лица могут быть преобразованы в структуры или класса, может быть, с методом Face :: event_elements {return intersection (...);}, особенно если вы хотите делать больше вещей на лицах, но, вероятно, с объектами Face, которые будут временными, поскольку они могут быть легко извлечены)

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

Можно заменить векторы в узле и элементе каким-то статическим размером, но я не считаю это большой сделкой, тем более что к ним можно получить доступ только в пределах модели.

Даунсайд архитектуры является то, что удаление либо неэффективно (изменить все хранилища идентификаторов) или оставляет дыры в памяти (хотя это не так уж плохо, если список неиспользуемых идентификаторов хранится)

Answer 2

Как говорится в комментарии к вашему сообщению, используйте зЬй :: массив для размерных векторов статических и использовать константные ссылки в вашем для петель, что позволит избежать копий и оптимизацию справки:

for (const auto &iter: m_elements) 

и

for(auto &it: faces) 

Если у вас есть много элементов (> 50) Я думаю, что вы должны также изменить контейнер, используемый для лиц из станда :: вектор к станду :: карта, так что это:

  for(auto it: faces) 
      { 
       if(s== it.first) 
        (it.second)++; break; 
      } 
      faces.push_back(s,1); 

станут:

  auto &it = faces.find(s); 
     if (it != faces.end()) 
      it.second++; 
     else 
      faces.insert(std::make_pair(s, 1));