如何为Boost图包装类的顶点描述符集合定义带自定义比较器的typedef

问题背景 #

你实现了Boost有向图的包装类GraphWrapper，顶点数据结构VertexData包含int类型的id字段。需要定义std::set<GraphVd>的别名VdSet，让集合按顶点的id值排序，但自定义比较器依赖GraphWrapper实例，且不想在头文件中创建类实例，原代码存在比较器设计问题。

原代码片段：

struct VertexData {
  int id;
};
typedef adjacency_list<vecS, vecS, bidirectionalS, VertexData> DirGraph;

typedef graph_traits<DirGraph>::vertex_descriptor GraphVd;

class GraphWrapper {
public:
  DirGraph g;
};

// 尝试的比较器
struct VdCmp {
  VdCmp(GraphWrapper &g) : g(g){};
  bool operator()(const GraphVd &vd1, const GraphVd&vd2) { return g[vd1].id > g[vd2].id; }
private:
DirGraph g;
};

问题分析 #

原比较器VdCmp存在两个核心问题：

1. 私有成员存储DirGraph的副本，而非引用，导致比较时使用的图数据与GraphWrapper中的g不同步；
2. 未正确处理std::set的模板参数逻辑：typedef仅需定义集合类型，实例化集合时才需要传入绑定了图实例的比较器对象，头文件中无需创建类实例。

解决方案 #

1. 修正比较器设计 #

调整比较器，存储DirGraph的引用，确保与GraphWrapper中的图数据同步，同时保证比较操作的常量性：

struct VdCmp {
    DirGraph& g;
    // 显式构造函数，接收DirGraph引用（可直接从GraphWrapper的g成员获取）
    explicit VdCmp(DirGraph& graph) : g(graph) {}
    // 标记为const，符合std::set对比较器的要求
    bool operator()(const GraphVd& vd1, const GraphVd& vd2) const {
        // 按id降序排序，若需升序改为<即可
        return g[vd1].id > g[vd2].id;
    }
};

2. 定义VdSet类型别名 #

在头文件中直接完成typedef，无需实例化任何对象：

typedef std::set<GraphVd, VdCmp> VdSet;

3. 在GraphWrapper中使用VdSet #

在GraphWrapper内部实例化VdSet时，传入当前对象的g成员引用即可：

class GraphWrapper {
public:
    DirGraph g;
    VdSet vertexSet;

    // 构造函数中初始化vertexSet，传入g的引用
    GraphWrapper() : vertexSet(VdCmp(g)) {}

    // 或者提供创建VdSet的方法
    VdSet createVertexSet() {
        return VdSet(VdCmp(g));
    }
};

注意事项 #

• 确保GraphWrapper对象的生命周期长于VdSet对象，避免比较器中的引用悬空；
• 若需要升序排序，将比较器中的>改为<即可；
• 比较器的operator()必须标记为const，否则无法通过std::set的编译检查。

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