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

Question

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

Я пытаюсь представить ненаправленный граф. Я создал три структуры, как показано ниже. Я добавил оператор == и оператор < к структуре 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;
}

0

c++graph set struct undirected-graph

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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 на дедуплицированных объектах.

1