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

Question

I am trying to represent a non-directional graph. I created three structs as shown below. I added operator == and operator < to the Edge struct hoping the set would use it to compare elements.

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

Question: If say, I have an edge from node 1 to 2 and an edge from 2 to 1, my struct declaration says they should be considered equivalent. Yet when I insert those two edges in a set, it inserts both of them as two separate elements (i.e. set does not understand that edge 1-2 and 2-1 are equal). What do I do so that the set took care of duplicates (i.e. only keeps one of these edges). See e.g. below:

 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*> will create a set of memory locations, not a set of T values.

If you want to compare the pointed objects, you need to provide a custom comparator:

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

However:

Be aware that the code I wrote answers your question, but is still not correct for your use-case, it's only ok to use this for non-owning pointers, which is most definitely not your case.

This is not a problem with my solution per-se, but a fundamental issue in what you are trying to accomplish. Something needs to call delete on the dedupped objects.