问题背景与约束
在图数据结构的应用中，我们常常需要为已有的顶点对象添加额外的属性，例如在位置列表中记录其位置索引。然而，实际开发中可能面临以下挑战：
- 不可修改原始代码： 现有顶点接口的实现代码是既定的，不允许进行任何修改。
- O(1)最坏情况访问： 新增属性的检索必须在O(1)最坏时间复杂度内完成。这意味着像HashMap这类在最坏情况下可能退化到O(N)的数据结构通常不符合要求。
- 私有嵌套类限制： 原始顶点实现可能是一个私有的嵌套类，这意味着我们无法直接访问其定义，也无法直接对其进行继承或实例化。
针对这些约束，我们将探讨两种在不修改原始代码的前提下，实现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继承。
选择与考量
在实际应用中，选择组合还是继承取决于具体场景和面临的约束。
-
"私有嵌套类"的挑战： 这是最关键的限制。如果GivenVertex确实是一个私有嵌套类，这意味着：
- 无法直接继承： 私有嵌套类通常不能在外部被继承。
- 无法直接实例化： 除非其外部类提供了公共的工厂方法来创建并返回GivenVertex的实例，否则也无法在外部直接new GivenVertex()。
在这种极端情况下，上述的组合和继承方案都无法直接应用，因为它们都假定我们能够获取到GivenVertex的定义或实例。如果无法获取GivenVertex的实例，那么唯一的选择可能就是回到使用外部映射（如HashMap或std::map），即使其最坏情况性能不满足O(1)的要求，也可能是唯一可行的方案。然而，如果原始图的实现提供了一个方法来获取GivenVertex的引用或指针（即使不能直接构造），那么组合模式仍有可能通过包装这些引用/指针来实现。
性能考量： 无论是组合还是继承，一旦对象被创建，对新增属性的访问都将是直接的成员访问，其时间复杂度为O(1)，完全满足了性能要求。
-
设计原则：
- 优先使用组合而非继承： 这是面向对象设计的一个常见建议。组合提供了更大的灵活性，减少了类之间的耦合。
- 继承用于“is-a”关系： 只有当新类确实是旧类的一种特殊类型时，才考虑使用继承。
总结
在不修改原始代码的前提下为图顶点添加新属性，并在O(1)最坏时间复杂度内访问，组合模式和继承模式都是可行的解决方案。
- 组合模式通过将原始顶点对象作为成员包含在新类中，提供了更低的耦合度和更高的灵活性，适用于原始类不易继承或不希望建立强“is-a”关系的场景。
- 继承模式通过创建原始顶点类的子类来扩展功能，适用于新类确实是原始类的一种特殊类型，且原始类允许被继承的情况。
然而，如果原始顶点类是一个私有嵌套类且无法在外部被实例化或继承，那么这两种直接扩展的方法将面临巨大挑战。在这种情况下，可能需要重新评估系统设计，或者在可接受的范围内考虑使用外部映射（如HashMap），并接受其在特定场景下的性能折衷。在大多数情况下，如果能够访问原始顶点的实例或其公共接口，组合模式通常是更稳健且推荐的选择。
