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

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

问题背景与约束

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

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 <iostream>
#include <cassert> // 用于断言测试

// 假设这是我们不能修改的原始顶点类
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 <iostream>
#include <cassert> // 用于断言测试

// 假设这是我们不能修改的原始顶点类
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学习网公众号了解相关技术文章。