Forward declaration of set Comparator

Question

I have a Graph structure that uses Nodes (Vertices), which in turn have Edges attached under the form of a std::pair<Node*, int> where the Node is the other end of the edge, and the integer is the edge weight. I'd like to keep the edges sorted in a std::multiset, based on connected node index and edge weight.

enum color { white, grey, black };

struct EdgeComparator;

struct Node {
  int n;
  std::multiset<std::pair<Node *, int>, EdgeComparator> edges;
  enum color col;
  int d;  // distance to source node

  explicit Node(int n) : n(n), edges(), col(white), d() {};
};

struct EdgeComparator {
  bool operator()(const std::pair<Node *, int> &p1,
                  const std::pair<Node *, int> &p2) {
    if (p1.second == p2.second)
      return p1.first->n < p2.first->n;
    return p1.second < p2.second;
  }
};

This forward declaration approach causes the error: invalid use of incomplete type struct EdgeComparator. If I try to switch them around and forward-declare Node instead of EdgeComparator, the n field is not visible anymore for the EdgeComparator, so I've run into a vicious circle.

The only workaround I thought of is to use a std::vector instead of a std::multiset and then apply std::sort, but that would be quite costly in terms of efficiency, so I was wondering if there is another way.

Answer 1

You could do it like that:

#include <set>

enum color { white, grey, black };

struct Node;

struct EdgeComparator {
  bool operator()(const std::pair<Node *, int> &p1,
              const std::pair<Node *, int> &p2);
};

struct Node {
  int n;
  std::multiset<std::pair<Node *, int>, EdgeComparator> edges;
  enum color col;
  int d;  // distance to source node

  explicit Node(int n) : n(n), edges(), col(white), d() {};
};

bool EdgeComparator::operator()(const std::pair<Node *, int> &p1,
              const std::pair<Node *, int> &p2) {
  if (p1.second == p2.second)
    return p1.first->n < p2.first->n;
  return p1.second < p2.second;
}

That compiles fine on my side. The reason is, that you split declaration and definition. The definition of EdgeComparator::operator() needs the concrete structure Node, the declaration does not, it only needs to know about the existence of a structure with that name:

1. Forward declare Node as a struct (needed for the declaration of EdgeComparator)
2. Declare EdgeComparator without definition of the operator() (which needs to know about the member Node::n)
3. Declare and define Node
4. Define EdgeComparator::operator()

Answer 2

Make EdgeComparator a template argument.

First, it solves your situation. Second, it makes sense and allow you to provide another type of comparator.

template<class TEdgeComparator>
struct Node {
  int n;
  std::multiset<std::pair<Node *, int>, TEdgeComparator> edges;
  // ...
};

struct EdgeComparator {
  bool operator()(const std::pair<Node *, int> &p1,
                  const std::pair<Node *, int> &p2) {
    if (p1.second == p2.second)
      return p1.first->n < p2.first->n;
    return p1.second < p2.second;
  }
};

Node<EdgeComparator> myNode(42);

But keep in mind having a node containing a collection of edges is a red flag. Are you sure of your design?