图顶点新增属性，不改代码方案

学习文章要努力，但是不要急！今天的这篇文章《图顶点新增属性的不改代码策略》将会介绍到等等知识点，如果你想深入学习文章，可以关注我！我会持续更新相关文章的，希望对大家都能有所帮助！

本文探讨了如何在不修改现有图顶点实现代码的前提下，为其添加额外属性并实现O(1)时间复杂度的访问。文章详细介绍了两种主要策略：通过组合（Composition）和继承（Inheritance）来扩展顶点功能，并提供了C++示例代码。同时，文章也深入分析了在原始顶点类为私有嵌套类等特殊约束下的适用性与局限性，为开发者提供了实用的设计参考。

问题背景与约束

在图数据结构的应用中，我们常常需要为已有的顶点对象添加额外的属性，例如在位置列表中记录其位置索引。然而，实际开发中可能面临以下挑战：

1. 不可修改原始代码： 现有顶点接口的实现代码是既定的，不允许进行任何修改。
2. O(1)最坏情况访问： 新增属性的检索必须在O(1)最坏时间复杂度内完成。这意味着像HashMap这类在最坏情况下可能退化到O(N)的数据结构通常不符合要求。
3. 私有嵌套类限制： 原始顶点实现可能是一个私有的嵌套类，这意味着我们无法直接访问其定义，也无法直接对其进行继承或实例化。

针对这些约束，我们将探讨两种在不修改原始代码的前提下，实现O(1)属性访问的策略：组合（Composition）和继承（Inheritance）。

方法一：使用组合模式添加属性

组合模式（Composition）是一种“has-a”关系，即一个类包含另一个类的实例作为其成员。通过这种方式，我们可以创建一个新的包装类，它持有原始顶点对象，并添加新的属性。

原理

创建一个新的类MyVertex，该类内部包含一个GivenVertex类型的成员变量，以及我们需要添加的新属性（例如position）。所有对原始顶点属性的访问都将通过MyVertex中包含的GivenVertex实例进行。

实现示例

以下C++代码展示了如何使用组合模式为GivenVertex添加一个position属性：

#include 
#include  // 用于断言测试

// 假设这是我们不能修改的原始顶点类
class GivenVertex {
private:
    int color = 3; // 原始顶点的一个属性
    // ... 其他原始属性和方法
public:
    GivenVertex() {}

    int getClr() {
        return color;
    }
    // ... 其他原始公共方法
};

// 我们的新顶点类，使用组合模式
class MyVertex {
public:
    int position;       // 新增的属性
    GivenVertex V;      // 包含原始顶点对象

    // 构造函数，接受原始顶点对象和新属性
    MyVertex(GivenVertex originalVertex, int newPosition) {
        this->V = originalVertex;
        this->position = newPosition;
    }

    // 可以提供包装方法来访问原始顶点的属性，例如：
    int getOriginalColor() {
        return V.getClr();
    }
};

int main() {
    // 实例化一个原始顶点
    GivenVertex gv = GivenVertex();

    // 创建我们的新顶点，并为其赋予新属性
    int pos = 7;
    MyVertex mv = MyVertex(gv, pos);

    // 验证新顶点是否正确包含了原始顶点属性和新属性
    assert(mv.V.getClr() == 3); // 通过mv.V访问原始顶点属性
    assert(pos == mv.position); // 直接访问新属性

    std::cout << "Original Color: " << mv.V.getClr() 
              << ", New Position: " << mv.position << std::endl; // 输出：Original Color: 3, New Position: 7

    return 0; 
}

优点

• 低耦合： MyVertex与GivenVertex之间的耦合度较低。MyVertex不需要知道GivenVertex的内部实现细节（除了其公共接口）。
• 灵活性： 只要能够获取到GivenVertex的实例（无论是通过构造、工厂方法还是其他途径），这种方法就可行。
• 不依赖原始类访问权限： 即使GivenVertex的构造函数是私有的（但有公共工厂方法）或其定义在某个无法继承的类中，只要能获取到其实例，组合模式仍然适用。

缺点

• 间接性： 访问原始顶点的属性时，需要通过MyVertex中的V成员（例如mv.V.getClr()），这增加了一层间接性。如果原始顶点有大量方法，可能需要为MyVertex编写大量包装方法。
• 不是"is-a"关系： MyVertex不是GivenVertex类型，不能在期望GivenVertex的地方直接使用MyVertex。

方法二：使用继承模式添加属性

继承模式（Inheritance）是一种“is-a”关系，即一个类是另一个类的特殊类型。通过继承，子类可以扩展父类的功能，添加新的属性和方法。

原理

创建一个新的类MyVertex，使其继承自GivenVertex。MyVertex将自动拥有GivenVertex的所有非私有成员，并可以在此基础上添加新的属性（例如position）。

实现示例

以下C++代码展示了如何使用继承模式为GivenVertex添加一个position属性：

#include 
#include  // 用于断言测试

// 假设这是我们不能修改的原始顶点类
class GivenVertex {
private:
    int color = 3; // 原始顶点的一个属性
public:
    GivenVertex() {}

    int getGivenClr() { // 注意：这里将getClr改名为getGivenClr以区分
        return color;
    }
    // ... 其他原始公共方法
};

// 我们的新顶点类，使用继承模式
// 采用私有继承，表示MyVertex是基于GivenVertex实现的，但外部不应将其视为GivenVertex
class MyVertex : private GivenVertex { 
public:
    int position; // 新增的属性

    // 构造函数，接受新属性
    MyVertex(int newPosition) : GivenVertex() { // 调用基类构造函数
        this->position = newPosition;
    }

    // 提供一个公共方法来访问基类的属性
    int getMyClr() {
        return getGivenClr(); // 直接访问基类的公共或保护方法
    }
};

int main() {
    // 创建我们的新顶点，并为其赋予新属性
    int pos = 7;
    MyVertex mv = MyVertex(pos);

    // 验证新顶点是否正确包含了原始顶点属性和新属性
    assert(mv.getMyClr() == 3); // 通过MyVertex的方法访问原始顶点属性
    assert(pos == mv.position); // 直接访问新属性

    std::cout << "Original Color: " << mv.getMyClr() 
              << ", New Position: " << mv.position << std::endl; // 输出：Original Color: 3, New Position: 7

    return 0; 
}

优点

• 直观的"is-a"关系： 如果MyVertex确实可以被视为GivenVertex的一种特殊类型，继承是更符合语义的选择。
• 直接访问基类成员： 子类可以直接访问基类的protected和public成员，无需通过额外的包装。
• 代码简洁： 通常不需要为基类方法编写包装器。

缺点

• 强依赖原始类： 继承要求原始类（GivenVertex）必须是可继承的（非final或sealed），且其构造函数必须可访问。如果GivenVertex是私有嵌套类，或者其构造函数是私有的，则无法直接继承。
• 紧耦合： MyVertex与GivenVertex之间存在紧密耦合，MyVertex的实现依赖于GivenVertex的内部结构。
• 私有继承的限制： 示例中使用了私有继承（private GivenVertex），这意味着MyVertex的外部使用者无法将MyVertex对象视为GivenVertex对象。如果需要保持多态性，则需要使用public继承。

选择与考量

在实际应用中，选择组合还是继承取决于具体场景和面临的约束。

1. "私有嵌套类"的挑战： 这是最关键的限制。如果GivenVertex确实是一个私有嵌套类，这意味着：

   • 无法直接继承： 私有嵌套类通常不能在外部被继承。
   • 无法直接实例化： 除非其外部类提供了公共的工厂方法来创建并返回GivenVertex的实例，否则也无法在外部直接new GivenVertex()。

   在这种极端情况下，上述的组合和继承方案都无法直接应用，因为它们都假定我们能够获取到GivenVertex的定义或实例。如果无法获取GivenVertex的实例，那么唯一的选择可能就是回到使用外部映射（如HashMap或std::map），即使其最坏情况性能不满足O(1)的要求，也可能是唯一可行的方案。然而，如果原始图的实现提供了一个方法来获取GivenVertex的引用或指针（即使不能直接构造），那么组合模式仍有可能通过包装这些引用/指针来实现。

2. 性能考量： 无论是组合还是继承，一旦对象被创建，对新增属性的访问都将是直接的成员访问，其时间复杂度为O(1)，完全满足了性能要求。

3. 设计原则：

   • 优先使用组合而非继承： 这是面向对象设计的一个常见建议。组合提供了更大的灵活性，减少了类之间的耦合。
   • 继承用于“is-a”关系： 只有当新类确实是旧类的一种特殊类型时，才考虑使用继承。

总结

在不修改原始代码的前提下为图顶点添加新属性，并在O(1)最坏时间复杂度内访问，组合模式和继承模式都是可行的解决方案。

• 组合模式通过将原始顶点对象作为成员包含在新类中，提供了更低的耦合度和更高的灵活性，适用于原始类不易继承或不希望建立强“is-a”关系的场景。
• 继承模式通过创建原始顶点类的子类来扩展功能，适用于新类确实是原始类的一种特殊类型，且原始类允许被继承的情况。

然而，如果原始顶点类是一个私有嵌套类且无法在外部被实例化或继承，那么这两种直接扩展的方法将面临巨大挑战。在这种情况下，可能需要重新评估系统设计，或者在可接受的范围内考虑使用外部映射（如HashMap），并接受其在特定场景下的性能折衷。在大多数情况下，如果能够访问原始顶点的实例或其公共接口，组合模式通常是更稳健且推荐的选择。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《图顶点新增属性，不改代码方案》文章吧，也可关注golang学习网公众号了解相关技术文章。