我有一个使用节点(顶点)的图形结构,节点又以 std::pair<Node*, int>
的形式附加了边其中Node是边的另一端,整数是边的权重。我想保持边缘在 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
, 但就效率而言,这将是相当昂贵的,所以我想知道是否有另一种方法。
最佳答案
你可以这样做:
#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,声明不需要,它只需要知 Prop 有该名称的结构的存在:
- 转发将 Node 声明为结构(需要声明 EdgeComparator)
- 在没有定义 operator() 的情况下声明 EdgeComparator(需要了解成员 Node::n)
- 声明和定义节点
- 定义 EdgeComparator::operator()
关于c++ - 集合比较器的前向声明,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50294506/