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.

Bobbyebobbysocks

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()

Denotative

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?

Bunchy

Thank you for the observation. The design helps my implementation, maybe my choice of using the word "edge" for it wasn't very inspired. It's more like "neighbors", if that makes sense. – Bobbyebobbysocks

@IoanaAlexandru A node is a node. A neighborhood is a neighborhood. Make sure you're going the right path before you get lost in software oblivion. – Bunchy

Do you have any idea of a better name for the member? I'm open to suggestions, I like to keep my code clean and easy to follow and understand. – Bobbyebobbysocks

@IoanaAlexandru Split Node into two classes. Make of SOLID your moto. – Bunchy