Используйте набор структур и избегайте дублирующих структур в наборе

Question

Я пытаюсь представить ненаправленный граф.Я создал три структуры, как показано ниже.Я добавил operator == и operator <в структуру Edge, надеясь, что набор будет использовать ее для сравнения элементов. </p>

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 и ребро от 21, мое объявление структуры говорит, что они должны считаться эквивалентными.Тем не менее, когда я вставляю эти два ребра в набор, он вставляет оба из них как два отдельных элемента (то есть набор не понимает, что ребра 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 для дедуплицированных объектов.