1. 问题背景与挑战
在图算法或数据结构实现中，我们有时会遇到需要为现有类（如 Vertex）添加额外信息（如在位置列表中的索引）的需求。然而，原始代码可能不允许修改，或者 Vertex 类本身是一个私有嵌套类，无法直接访问或继承。同时，对这些新属性的访问效率要求很高，通常需要达到O(1)的最差时间复杂度。
传统的解决方案，如使用 HashMap（在C++中对应 std::unordered_map），虽然在平均情况下能提供O(1)的访问速度，但在最坏情况下其时间复杂度可能退化到O(N)，这不符合严格的O(1)最差情况要求。因此，我们需要寻找一种更可靠的、基于类结构的设计模式来解决这个问题。
2. 解决方案一：组合（Composition）模式
组合模式是一种“拥有”（has-a）关系，即一个类包含另一个类的实例作为其成员。通过这种方式，我们可以在不触及原始 GivenVertex 代码的情况下，创建一个新的 MyVertex 类来封装原始顶点并添加新属性。
2.1 原理
我们创建一个新的 MyVertex 类。这个 MyVertex 类将包含一个 GivenVertex 类型的成员变量，以及我们想要添加的新属性（例如 position）。当需要使用原始 GivenVertex 的功能时，可以通过 MyVertex 内部的 GivenVertex 成员来访问。
2.2 示例代码
#include <iostream> // 用于cout
#include <cassert> // 用于assert
// 假设这是原始的、不可修改的顶点类
// 在实际场景中，这可能是一个私有嵌套类，我们只能实例化它，不能修改其定义
class GivenVertex {
private:
int color = 3; // 原始顶点的一个属性
// 其他私有成员...
public:
GivenVertex() {} // 构造函数
int getClr() const { // 获取颜色属性的方法
return color;
}
// 其他原始顶点的方法...
};
// 我们创建的新顶点类，采用组合模式
class MyVertex {
public:
int position; // 新增的属性
GivenVertex V; // 包含一个原始的GivenVertex实例
// 构造函数，需要传入一个GivenVertex实例和新属性的值
MyVertex(GivenVertex originalVertex, int newPosition)
: V(originalVertex), position(newPosition) {
// 构造时将原始顶点实例和新属性值赋给成员
}
// 可以添加方法来转发对原始顶点属性的访问
int getOriginalColor() const {
return V.getClr();
}
};
int main() {
// 实例化一个原始的GivenVertex对象
GivenVertex originalGV = GivenVertex();
// 创建我们的新顶点，并为其添加一个位置属性
int pos = 7;
MyVertex myExtendedVertex(originalGV, pos);
// 验证新顶点是否正确地包含了原始顶点的信息和新属性
assert(myExtendedVertex.V.getClr() == 3); // 验证原始顶点属性
assert(myExtendedVertex.getOriginalColor() == 3); // 通过MyVertex的转发方法验证
assert(myExtendedVertex.position == pos); // 验证新属性
std::cout << "Original Vertex Color: " << myExtendedVertex.V.getClr()
<< ", New Position: " << myExtendedVertex.position << std::endl;
return 0;
}
2.3 优点与注意事项
-
优点：
- 不修改原始代码： 这是最核心的优点，完全符合要求。
- 处理私有嵌套类： 即使 GivenVertex 是一个私有嵌套类，只要我们能实例化它，就可以将其作为 MyVertex 的成员。
- O(1)访问： 新属性 position 作为 MyVertex 的直接成员，其访问时间复杂度为O(1)最差情况。
- 灵活性： MyVertex 可以完全控制对 GivenVertex 的访问，可以根据需要封装或限制某些操作。
-
注意事项：
- 如果需要频繁调用 GivenVertex 的方法，MyVertex 可能需要编写大量的转发方法，这会增加代码量。
- MyVertex 的生命周期需要管理其内部 GivenVertex 实例的生命周期。
3. 解决方案二：继承（Inheritance）模式
继承模式是一种“是”（is-a）关系，即一个类（子类）从另一个类（父类）派生，并继承其属性和方法。通过继承，我们可以在子类中直接添加新属性。
3.1 原理
我们创建一个新的 MyVertex 类，使其继承自 GivenVertex。这样，MyVertex 将自动拥有 GivenVertex 的所有公共和保护成员，然后我们可以在 MyVertex 中直接声明新的属性。
3.2 示例代码
#include <iostream> // 用于cout
#include <cassert> // 用于assert
// 假设这是原始的、不可修改的顶点类
// 注意：为了演示继承，这里假设GivenVertex是可访问的，
// 但原始问题指出它可能是一个“私有嵌套类”，在这种情况下直接继承可能不可行。
class GivenVertex {
private:
int color = 3; // 原始顶点的一个属性
public:
GivenVertex() {} // 构造函数
int getGivenClr() const { // 获取颜色属性的方法
return color;
}
// 其他原始顶点的方法...
};
// 我们创建的新顶点类，采用继承模式
// 使用 private 继承，表示MyVertex的“实现”基于GivenVertex，
// 但不向外部暴露GivenVertex的公共接口，除非MyVertex明确地转发它们。
class MyVertex : private GivenVertex {
public:
int position; // 新增的属性
// 构造函数，只接收新属性的值
MyVertex(int newPosition)
: position(newPosition) {
// 父类GivenVertex的默认构造函数会被自动调用
}
// 为了访问父类的getGivenClr方法，我们需要在子类中提供一个公共接口
int getMyClr() const {
return getGivenClr(); // 调用父类的protected或public方法
}
};
int main() {
// 创建我们的新顶点，并为其添加一个位置属性
int pos = 7;
MyVertex myExtendedVertex(pos);
// 验证新顶点是否正确地包含了原始顶点的信息和新属性
assert(myExtendedVertex.getMyClr() == 3); // 验证原始顶点属性（通过子类方法转发）
assert(myExtendedVertex.position == pos); // 验证新属性
std::cout << "Original Vertex Color (via MyVertex): " << myExtendedVertex.getMyClr()
<< ", New Position: " << myExtendedVertex.position << std::endl;
return 0;
}3.3 优点与注意事项
-
优点：
- 不修改原始代码： 同样符合要求。
- O(1)访问： 新属性 position 作为 MyVertex 的直接成员，其访问时间复杂度为O(1)最差情况。
- 代码简洁： 如果 GivenVertex 的方法是 public 或 protected，子类可以直接访问，无需大量转发。
-
注意事项：
- 私有嵌套类限制： 这是最关键的限制。如果 GivenVertex 确实是一个私有嵌套类，意味着它在外部作用域中是不可见的，因此无法直接从它继承。在这种情况下，继承模式是不可行的。上述示例代码为了演示继承而假设 GivenVertex 是可访问的。
- 访问权限： 如果 GivenVertex 的重要方法是 private，即使继承也无法直接访问，仍需通过公共或保护方法间接访问。
- 多态性： 如果需要将 MyVertex 视为 GivenVertex 的一种类型（即需要多态行为），则需要使用 public 继承，并且 GivenVertex 应该有虚函数。然而，在不修改 GivenVertex 的前提下，通常无法添加虚函数。
- 构造函数： 子类构造函数需要确保父类部分正确初始化。
4. 总结与选择建议
在不修改原始顶点代码且要求O(1)最差时间复杂度访问新属性的场景下：
- 组合（Composition）模式是更通用、更稳健的选择，尤其适用于原始类是私有嵌套类或其内部实现细节不应被外部知晓（即“黑盒”使用）的情况。它通过封装原始对象，提供了最大的灵活性和最小的耦合度。
- 继承（Inheritance）模式在原始类可以被访问并设计为可扩展时（例如，不是私有嵌套类，且具有合适的访问修饰符），可以提供更紧密的集成和更简洁的代码。然而，如果原始类是私有嵌套的，或者其构造函数复杂，继承可能变得困难或不可能。
考虑到原始问题中明确指出 GivenVertex 是一个“私有嵌套类”，组合模式是更符合该约束的解决方案。它允许我们创建一个新的包装类来“拥有”原始顶点实例，并附加额外属性，完美满足了不修改原始代码和O(1)访问的要求。
对于 HashMap（或 std::unordered_map）的O(1)最差情况限制，上述两种类设计模式通过将新属性直接作为类成员，天然地提供了O(1)的最差访问性能，从而避免了哈希冲突可能带来的性能退化问题。
