c++ - 在 vector 的 vector 中搜索和计数对象对的最佳数据结构是什么

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
}

类模型 由整个节点 和元素 对象组成。 类元素对象由四个节点对象组成。一对两个连续(相邻)的 node 对象称为面。

示例:
elem1 : { 1,2,3,4 }
elem2 : { 3,5,6,4 }
elem1和elem2是两个element对象，数组中的整数表示四个节点对象的id。
1-2、2-3、3-4 和 4-1 是 elem1 的面。 3-5、5-6、6-4 和 4-3 是 elem2 的面。 面 3-4 和面 4-3 相同，因此由两个元素共享。

边界元素是由至少一个面组成的元素，该面不与其他元素共享。在上面的例子中，elem1 和 elem2 都是边界元素。模型类中还定义了边界元素 vector 。

类模型

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

    public:
    void set_boundary_elements();
}

问题:如何初始化边界元素的 vector
这是 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

重新考虑您的设计。目前，元素并不真正共享节点。两个元素应该共享一个节点，每个元素都存储一组恰好具有相同 ID 的不同数据。这意味着如果某事改变了一个节点，系统可能会不一致。

这是我的建议(没有构造函数、getter、setter 等，假设您可以轻松填写​​这些):

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

请注意，Node 和 Element 都存储事件项，它们使用 integers 来存储事件项，这些 integers 在 Model 的 vector 中引用它们的 id。 Model 负责创建和修改 Nodes 和 Elements，此类方法将负责保持数据一致。 Element 或 Node 上的所有公共(public)方法都是常量。

这为您提供了一个在两个方向上都有引用的稳定系统。如果想知道一个Element是否在边界上，代码是

//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 可以转换为结构或类，也许使用方法 Face::incident_elements{return intersection(...);}，特别是如果你想做更多的东西在脸上，但可能 Face 对象是临时的，因为它们可以很容易地提取)

这种方式允许您进行干净的操作，当然每个节点都需要存储事件元素 vector ，这需要更多内存。但我怀疑如果没有类似的东西你是否能够高效地工作，特别是因为我假设你会想要做更多这样的操作。

可以用静态大小的东西替换 Node 和 Element 中的 vector ，但我认为这没什么大不了的，尤其是因为它们只能在模型中访问。

架构的缺点是删除效率低下(更改所有 id 存储)或在内存中留下漏洞(尽管如果存储了未使用的 id 列表，这还不算太糟糕)