集合比较器的前向声明

Question

我有一个使用节点（顶点）的图形结构，它又以 std::pair<Node*, int> 的形式附加了边，其中节点是边的另一端，整数是边重量。我想根据连接的节点索引和边权重将边按 std::multiset 排序。

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，则 n 字段对于 EdgeComparator 不再可见，所以我运行陷入了恶性循环。

我想到的唯一解决方法是使用 std::vector 而不是 std::multiset 然后应用 std::sort，但就效率而言，这会非常昂贵，所以我想知道有没有别的方法。

Answer 1

使 EdgeComparator 成为模板参数。

首先，它解决了你的情况。其次，它很有意义，允许您提供另一种类型的比较器。

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

但请记住，节点包含边的集合是一个危险信号。你确定你的设计吗？

Answer 2

你可以这样做：

#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，声明不需要，它只需要知道具有该名称的结构的存在：

转发将 Node 声明为结构（需要声明 EdgeComparator）
在没有定义 operator() 的情况下声明 EdgeComparator（需要了解成员 Node::n）
声明并定义节点
定义EdgeComparator::operator()

集合比较器的前向声明

Forward declaration of set Comparator

c++

graph

cross-reference

forward-declaration