基类DiGraph与派生类UnGraph的函数复用实现方案问询

问题背景 #

现有基类DiGraph（有向图）和派生类UnGraph（无向图）的定义：

class DiGraph
{
protected:
    long V;    // 顶点数量，顶点编号为0, 1, ..., V-1
    vector<list<long>> adj;      // 邻接表
public:
    DiGraph(long V);  // 构造函数，初始化顶点数并调整邻接表大小
    virtual void addEdge(long v, long w); // 添加有向边(v,w)
    vector<list<long>> getadjL (); // 返回邻接表
    vector<vector<long>> getadjM (); // 计算并返回邻接矩阵
};

class UnGraph: public DiGraph {
public:
    void addEdge(long v, long w);   // 添加无向边，即同时添加(v,w)和(w,v)
};

已实现针对DiGraph的完全图生成函数：

DiGraph Kn (long n) {  // 返回n个顶点的完全有向图
    DiGraph G(n);
    for (long i = 0; i < n ; i++) {
        for (long j = 0; j < n; j++)
            G.addEdge(i, j);
    }
    return G;
}

需要解决的问题：

• 是否必须复制所有函数才能适配UnGraph？
• 能否用单个函数同时适配两类图？
• 尝试的模板函数是否合法，能否调用T的addEdge成员？

解答 #

1. 不需要复制所有函数 #

完全可以通过函数模板实现通用的生成逻辑，彻底避免代码冗余。

2. 你的模板函数是合法的 #

你写的模板函数完全可以调用T的addEdge成员，原因很简单：
C++模板采用实例化时检查的机制——当你用DiGraph或UnGraph作为模板参数实例化Kn时，编译器会自动检查该类型是否具备所需成员（接受long参数的构造函数、带两个long参数的addEdge方法），只要满足条件就能正常编译。
而DiGraph本身有这些成员，UnGraph继承自DiGraph且重写了addEdge，两类都能满足模板的要求。

3. 优化建议 #

当前模板生成无向完全图时会做冗余操作：比如循环里会调用addEdge(i,j)和addEdge(j,i)，但UnGraph的addEdge本身已经会添加双向边，所以可以优化循环减少不必要的函数调用：

template <typename T> 
T Kn(long n) {
    T G(n);
    for (long i = 0; i < n; i++) {
        // 无向图只处理i<=j的情况，避免重复添加边
        long start_j = std::is_same_v<T, UnGraph> ? i : 0;
        for (long j = start_j; j < n; j++) {
            G.addEdge(i, j);
        }
    }
    return G;
}

如果不想依赖类型判断，也可以保持原循环逻辑，把去重的责任交给addEdge的实现，只是会多几次无效的函数调用。

4. 可选：添加模板约束 #

如果想明确限制模板只能用于DiGraph及其派生类，可以加静态断言，让错误提示更友好：

#include <type_traits>

template <typename T> 
T Kn(long n) {
    static_assert(std::is_base_of_v<DiGraph, T>, "T必须是DiGraph的派生类");
    T G(n);
    for (long i = 0; i < n ; i++) {
        for (long j = 0; j < n; j++)
            G.addEdge(i, j);
    }
    return G;
}

使用示例 #

// 生成5个顶点的完全有向图
DiGraph directed_kn = Kn<DiGraph>(5);
// 生成5个顶点的完全无向图
UnGraph undirected_kn = Kn<UnGraph>(5);

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