使用一组结构并避免在一组中重复结构

Question

我正在尝试表示无向图。我创建了三个结构，如下所示。我将 operator == 和 operator < 添加到 Edge 结构中，希望集合使用它来比较元素。

struct  Node;   /* Forward references to these two types */
struct Edge;     /* that the compiler can recognize them */

/* Type: Node
 * This type represents an individual node and consists of the data of the 
 *  node and the set of edges from this node */
struct Node{
    int nodeNum;
    string data;
    set<Edge*> edges;
};


/* Type: Edge
 * This type represents an individual edge and consists of pointers to the 
 * endpoints */
struct Edge{
    Node *end1;
    Node *end2;

    // This says that edge from node 1 to node 2 and edge from node 2 to node 1 are considered the same
    bool operator==(const Edge &e) const{
        return ( (this->end1->nodeNum == e.end1->nodeNum && this->end2->nodeNum == e.end2->nodeNum) ||
                 (this->end1->nodeNum == e.end2->nodeNum && this->end2->nodeNum == e.end1->nodeNum));
    }

    // This function is used by set to order elements of edges.
    bool operator<(const Edge *e) const{
        return (this->end1 < e->end1 && this->end2 < e->end2);
    }
};


// This is a struct for graph
struct Graph{
    set<Node*> Nodes;
    set<Edge*> Edges;
    map<int, Node*> nodeMap;
};

问题：如果说，我有一条从节点 1 到 2 的边和一条从 2 到 1 的边，我的结构声明说它们应该被认为是等价的。然而，当我将这两条边插入到一个集合中时，它会将它们作为两个单独的元素插入（即集合不理解边 1-2 和 2-1 是相等的）。我该怎么做才能让集合处理重复项（即只保留这些边之一）。参见例如下面：

 int main(){
    // Let's make 2 nodes, node 1 and node 2
    Node* n1 = new Node;
    Node* n2 = new Node;
    n1->nodeNum=1;
    n2->nodeNum=2;

    // Let's make 2 edges 1-2 and 2-1
    Edge* e1 = new Edge;
    Edge* e2 = new Edge;
    e1->end1=n1; e1->end2=n2;
    e2->end1=n2; e2->end2=n1;

    // Now let's make a graph and put the edges in its internal set
    Graph g;
    g.Edges.insert(e1);  
    g.Edges.insert(e2);  // the set takes in both e1 and e2. If I print all elements in g.Edges, it will print both 1-2 and 2-1
    // How do I tell the set to treat e1 and e2 as equal edges so it took care of duplicates?

    return 0;
   }

Answer 1

std::set<T*> 将创建一组内存位置，而不是一组 T 值。

如果要比较指向对象，需要提供自定义比较器：

struct Ptr_compare {
  template<typename T>
  constexpr bool operator()( const T* lhs, const T* rhs ) const {
    return *lhs < *rhs;
  }
};

// This is a struct for graph
struct Graph {
    set<Node*, Ptr_compare> Nodes;
    set<Edge*, Ptr_compare> Edges;
    map<int, Node*> nodeMap;
};

但是：

请注意，我写的代码回答了你的问题，但仍然不适合你的用例，它只适用于 非拥有指针，它绝对不是你的情况。

这不是我的解决方案本身的问题，而是您要实现的目标的根本问题。需要对去重对象调用 delete。

使用一组结构并避免在一组中重复结构

Use a set of structs and avoid duplicate structs in a set

c++

struct

graph

set

undirected-graph