Comparison of two class instances not having members as unique identifiers

Question

Consider two classes, Node and Edge, representing the nodes and the edges of a multigraph, respectively (see my MWE code below). My intention is to to use three unordered_maps:

(a) from Node variables to Edge data,

(b) from Edge variables to Node data, and

(c) from Node pairs to double variables.

I tried to write bool operator==() functions for Node* and Edge* and hash functions for Node*, Edge*, and pair<Node*,Node*>.

My first problem is related to the bool operator==() function of Edge. Although the labels of the Nodes are certainly unique, this bool operator==() function is not correct for multiple edges having the same starts and ends (). Is there any chance to construct correct bool operator==() function using, e.g., the memory address of the Edges?

The second question is whether these functions result in saving only the different Node/Edge/pair<Node,Node> objects if only simple edges are assumed.

So, my MWE is as follows:

#include<string>
#include<vector>
#include<utility>
#include<unordered_map>
#include<iostream>
#include <bits/stdc++.h> 

using namespace std;


class Node
{
   public:
      Node(){};
      string label;
      bool operator==(const Node* other) const
      {return label == other->label;};
};

class Edge
{
   public:
      Edge(){};
      Node *start, *end;
      double weight;
      bool operator==(const Edge* other) const
      {return start->label == other->start->label && 
       end->label == other->end->label;};
      //{return this == *other;}
};

namespace std
{
   template <>
   struct hash<Node*>
   {
      size_t operator()(const Node* node) const
      {return hash<string>()(node->label);}
   };

   template <>
   struct hash<Edge*>
   {
      size_t operator()(const Edge* edge) const
      {
         auto hash1 = hash<Node*>()(edge->start);
         auto hash2 = hash<Node*>()(edge->end);
         return hash1 ^ hash2; 
      }
   };

   template <>
   struct hash<pair<Node*,Node*>>
   {
      size_t operator()(const pair<Node*, Node*>& p) const
      { 
          auto hash1 = hash<Node*>()(p.first); 
          auto hash2 = hash<Node*>()(p.second);
          return hash1 ^ hash2; 
      } 
   };
}; 

int main()
{
   Edge* edge;
   Node* node;

   unordered_map<Node*,Edge> n2e;
   unordered_map<Edge*,Node> e2n;
   unordered_map<pair<Node*,Node*>,double> np2w;

   edge = new Edge();
   edge->weight = 1.0;
   edge->start = new Node();
   edge->start->label = "A";
   edge->end = new Node();
   edge->end->label = "B";

   n2e[edge->start] = *edge;
   e2n[edge] = *(edge->start);
   np2w[make_pair(edge->start, edge->end)] = edge->weight;

   edge = &n2e[edge->start];
   node = &e2n[edge];

   return 0;
}

"The second question is ..." - *One* question per question, please. — Jesper Juhl, Apr 07 '19 at 13:03
Unrelated to your problem, but please read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) — Some programmer dude, Apr 07 '19 at 13:11
As for your problems with comparison, the compiler should tell you what it tried to do in the error messages. The messages should contain the exact types of the arguments it uses when invoking `operator==`. From that information it should not be hard to create the overloaded operator needed. — Some programmer dude, Apr 07 '19 at 13:14

Jarod42 · Accepted Answer · 2019-04-07T13:11:30.957

You mostly define operator==(const Edge&, const Edge*),
whereas you would need operator==(const Edge*, const Edge*), but the latter cannot be defined.

You have to write class which define operator()(const Edge*, const Edge*) const and provide it in std::unordered_map.

struct MyEdgeComp
{
    bool operator()(const Edge* lhs, const Edge* rhs) const {
        return *lhs == *rhs; // Assuming you implement it
    }
};

std::unordered_map<Edge*, Node, std::hash<Edge*>, MyEdgeComp> e2n;

Comparison of two class instances not having members as unique identifiers

1 Answers1