std::multiset比较器前向声明问题：如何解决不完全类型错误？

你遇到的是典型的模板类型依赖与循环定义问题：std::multiset要求它的比较器参数是完整类型，但你的EdgeComparator要访问Node的成员，又需要Node是完整类型。这里有个完美的解决办法，不需要放弃std::multiset的效率：

调整代码结构，分离比较器的声明与实现 #

我们可以先定义EdgeComparator的结构体（让它成为完整类型），但只声明operator()，等Node完全定义后再实现这个比较运算符：

#include <set>
#include <utility>

enum color { white, grey, black };

// 前向声明Node，让EdgeComparator知道这个类型存在
struct Node;

// 定义完整的EdgeComparator结构体，但只声明operator()
struct EdgeComparator {
    bool operator()(const std::pair<Node*, int>& p1, const std::pair<Node*, int>& p2);
};

// 现在可以安全定义Node了，因为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(0) {};
};

// 此时Node已经是完整类型，实现比较器的逻辑
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;
}

为什么这个方案可行？ #

1. 当定义Node时，EdgeComparator已经是完整类型（我们已经定义了结构体本身，只是成员函数没实现），满足std::multiset对模板参数的要求（需要知道比较器的大小和类型信息）。
2. 等到实现EdgeComparator::operator()时，Node已经完全定义，所以可以安全访问Node::n成员。

为什么你原来的代码报错？ #

你之前用struct EdgeComparator;只是前向声明，此时EdgeComparator是不完整类型，std::multiset无法基于不完整类型实例化模板，因此触发invalid use of incomplete type错误。而如果先定义EdgeComparator再定义Node，又会因为Node是不完整类型而无法访问n成员。这个分离声明与实现的方式完美打破了循环依赖。

其他备选方案（不推荐） #

• 用std::vector加std::sort：正如你想到的，每次排序会带来O(n log n)的额外开销，频繁操作时效率远不如std::multiset的O(log n)插入/查找。
• 用std::function作为比较器：虽然能解决依赖问题，但会带来额外的运行时开销，不如自定义比较器高效。

内容的提问来源于stack exchange，提问作者SakoDaemon