集合比较器的前向声明

Question

我有一个使用节点(顶点)的图形结构,而节点又以std::pair<Node*, int>节点是边缘另一端的形式附加边缘,整数是边缘权重.我想std::multiset根据连接的节点索引和边缘权重将边缘排序为a .

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;
  }
};

这种前向声明方法导致错误:invalid use of incomplete type struct EdgeComparator.如果我尝试切换它们并向前声明Node而不是EdgeComparator,则EdgeComparator n不再显示该字段,因此我遇到了恶性循环.

我想到的唯一解决方法是使用a std::vector而不是a std::multiset然后应用std::sort,但这在效率方面会非常昂贵,所以我想知道是否还有其他方法.

Answer 1

你可以这样做:

#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;
}

这对我来说很好.原因是,你拆分了声明和定义.EdgeComparator :: operator()的定义需要具体结构Node,声明不需要,它只需要知道具有该名称的结构的存在:

1. 转发将Node声明为结构(声明EdgeComparator所需)
2. 声明EdgeComparator而不定义operator()(需要知道成员Node :: n)
3. 声明并定义Node
4. 定义EdgeComparator :: operator()