65.9K
CodeProject 正在变化。 阅读更多。
Home

面向对象编程中的数据结构

Paulo Zemek
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.89/5 (42投票s)

2014年8月2日

CPOL

11分钟阅读

viewsIcon

114319

downloadIcon

689

有一本流行的书籍，它将数据结构与过程式代码联系起来。而这篇文章将完全围绕着在面向对象编程中使用数据结构展开。

引言

我目前正在编写一本关于工作场所最佳 C# 实践的指南，在写完我认为最重要的几点后，我决定寻求帮助，看看是否还有我可能忽略的重要方面。我的一位同事递给了我这本书 《代码整洁之道 - 敏捷软件开发手工技艺》。

我以前多次听说过这本书，但从未读过。于是，我便翻阅了一下。有很多观点我赞同，也有一些我不同意（尽管我认为更多的是观点问题），但有一点真的引起了我的注意，因为我完全不同意——当谈到“对象与数据结构”时，得出了这样的结论：

“过程式代码使得添加新数据结构变得困难，因为所有的函数都必须修改。面向对象代码使得添加新函数变得困难，因为所有的类都必须修改。”

而整个观点被呈现得好像数据结构只与过程式代码相关，而面向对象（OO）代码无法处理数据结构，只能一直使用“完整对象”。好了，本文将探讨如何在面向对象编程中使用“数据结构”，并实现无需修改所有函数即可添加新数据结构，以及无需修改所有数据结构即可添加新函数。

（糟糕的）示例

书中的示例或多或少与下面的示例类似。需要注意的是，我这是根据我的记忆写的，并且我使用了 C# 而不是 Java，所以看起来自然会有些不同，但我保留了“过程式”和“面向对象”含义的理念。

过程式

public class Square
{
  public double Left { get; set; }
  public double Top { get; set; }
  public double Side { get; set; }
}

public class Rectangle
{
  public double Left { get; set; }
  public double Top { get; set; }
  public double Width { get; set; }
  public double Height { get; set; }
}

public class Circle
{
  public double CenterX { get; set; }
  public double CenterY { get; set; }
  public double Radius { get; set; }
}

public static class Geometry
{
  public static double GetArea(object shape)
  {
    if (shape is Rectangle)
    {
      Rectangle rectangle = (Rectangle)shape;
      return rectangle.Width * rectangle.Height;
    }

    if (shape is Square)
    {
      Square square = (Square)shape;
      return square.Side * square.Side;
    }

    if (shape is Circle)
    {
      Circle circle = (Circle)shape;
      return Math.PI * circle.Radius * circle.Radius;
    }

    throw new ArgumentException("Unknown shape type.", "shape");
  }
}

面向对象

public interface IShape
{
  double Area { get; }
}

public class Square:
  IShape
{
  public double Left { get; set; }
  public double Top { get; set; }
  public double Side { get; set; }

  public double Area
  {
    get
    {
      return Side * Side;
    }
  }
}

public class Rectangle:
  IShape
{
  public double Left { get; set; }
  public double Top { get; set; }
  public double Width { get; set; }
  public double Height { get; set; }

  public double Area
  {
    get
    {
      return Width * Height;
    }
  }
}

public class Circle:
  IShape
{
  public double CenterX { get; set; }
  public double CenterY { get; set; }
  public double Radius { get; set; }

  public double Area
  {
    get
    {
      return Math.PI * Radius * Radius;
    }
  }
}

这些代码块试图说明的是，在“过程式”版本中，形状不需要实现任何接口，也没有任何方法，因此我们可以在单独的类中创建任意多的函数，而无需修改现有的三个形状。不幸的是，如果我们添加一个新的形状，我们就需要修改所有现有的函数。

“面向对象”版本则以相反的方式工作，它强制所有形状在 `IShape` 中添加新方法或属性时都必须进行更改，但允许在不更改任何现有代码的情况下添加新形状。

共同的问题 - 违反开闭原则

想象一下我们创建了两个 DLL。一个是以过程式方式创建的，另一个是以（糟糕的）面向对象方式创建的。我们的目的是创建一个应用程序，该应用程序使用其中一个库，并在应用程序中（不改变库代码）添加以下特征：

  • 一个能够绘制现有形状的 `Draw()` 方法（或函数，如果你愿意的话）。
  • 一个 `Triangle` 形状（我们必须记住它也应该被绘制）。

哪个库能让你在不破坏现有类/函数的情况下做到这一点？

答案是：**都不是**。这是对开闭原则的违反，该原则指出软件实体应该对扩展开放，对修改关闭。

如果我们使用过程式库，我们就无法添加 `Triangle` 类并使用 `Geometry.GetArea()` “函数”。如果我们使用面向对象库，我们就无法向 `IShape` 添加 `Draw()` 方法，因为要做到这一点，我们就必须修改库本身。

那么，是否有可能编写一个库，允许应用程序添加新的形状和“函数”，而不会破坏库中已有的形状和函数（从而遵守开闭原则）？

答案：嗯，我将在本文的末尾附近给出。现在我将继续讨论“伪解决方案”。

变通方法和伪解决方案

我可以说是存在很多“伪解决方案”。例如，我们可以采用面向对象库，添加 `Triangle` 形状，然后创建另一个类中的过程式 `Draw()` 函数。最终会得到一个可用的结果，但并不优雅，因为 `Area` 将成为形状的一部分，而 `Draw` 将存在于别处。然后，如果我们想添加更多形状，我们就需要记住有些方法是形状的一部分，而有些方法是“在别处”的。

我们也可以采用过程式库，添加新形状，然后创建一个 `AppGeometry` 类，其中包含一个支持所有形状的 `Draw()` 方法，以及一个支持 `Triangle` 并将其他形状重定向到 `Geometry.GetArea()` 的 `GetArea()` 方法。如果所有对 `GetArea()` 的调用都来自应用程序，那么这个解决方案将运行得很好，但如果存在其他方法已依赖于 `Geometry.GetArea()`，那么对于 `Triangle` 就会出现问题。

但是，让我们把问题推进一步。如果我们想拥有一个包含基本形状和函数的库，然后是另一个包含复杂形状和更多函数的库，同时我们还想允许应用程序添加自己的形状和函数，那么会发生什么？请注意，对面向对象库的解决方案使用了过程式的 `Draw()`，而过程式库本身就存在限制。

可扩展的过程式代码

我们可以通过使其可扩展来解决过程式代码的问题。但请记住，这并非最终解决方案，因为我的目的是提出一个面向对象的解决方案。

想象一下，在过程式库中，`Geometry` 类的代码如下，而不是前面提供的代码：

public static class Geometry
{
  public static double GetArea(object shape)
  {
    if (shape is Rectangle)
    {
      Rectangle rectangle = (Rectangle)shape;
      return rectangle.Width * rectangle.Height;
    }

    if (shape is Square)
    {
      Square square = (Square)shape;
      return square.Side * square.Side;
    }

    if (shape is Circle)
    {
      Circle circle = (Circle)shape;
      return Math.PI * circle.Radius * circle.Radius;
    }
	
    var gettingArea = GettingArea;
    if (gettingArea != null)
    {
      foreach(Func<object, double> func in gettingArea.GetInvocationList())
      {
        double possibleResult = func(shape);
        if (possibleResult >= 0)
          return possibleResult;
      }
    }

    throw new ArgumentException("Unknown shape type.", "shape");
  }
  
  public static event Func<object, double> GettingArea;
}

通过像这样编写库，我们就能在应用程序中添加新形状，并仍然可以调用 `Geometry.GetArea()` 方法来获取新形状的面积。我们不需要调用不同的方法，因此，库本身（或其他库）中对 `Geometry.GetArea()` 的任何调用都可以支持新形状。只需在 `GettingArea` 事件中注册新处理程序即可。

这种方法的缺点在于，如果我们有很多很多不同的形状，它可能会导致“坏模式”。如果每个形状都添加一个处理程序，那么对于“位于调用末尾”的形状来说，速度会变慢。使用一个具有类型测试的单个委托会稍微快一些，但仍然存在问题，即使能够为处理程序编写一个巧妙的算法，那个巧妙的算法也应该从一开始就具备……所以，我们来寻找解决方案。

数据结构 + 函数作为“委托容器”

现在让我们打破数据结构就是过程式，而面向对象要求“函数”成为对象一部分的观念。我们可以使用数据结构并将函数“附加”到它们上面。看看下面的代码：

public static class ShapeAreaGetter
{
  private static readonly ConcurrentDictionary<Type, Func<object, double>> _dictionary = 
    new ConcurrentDictionary<Type, Func<object, double>>();
  
  public static void Register<T>(Func<T, double> func)
  {
    if (func == null)
      throw new ArgumentNullException("func");
	  
    if (!_dictionary.TryAdd(typeof(T), (shape) => func((T)shape)))
      throw new InvalidOperationException(
        "An area getter function was already registered for the given data-type.");
  }
  
  public static double GetArea(object shape)
  {
    if (shape == null)
      throw new ArgumentNullException("shape");
	  
    Type type = shape.GetType();
    Func<object, double> func;
    _dictionary.TryGetValue(type, out func);
	
    if (func == null)
      throw new InvalidOperationException(
        "There's no area getter registered for the given shape's type.");
	  
    return func(shape);
  }
}

通过这个解决方案，我们可以添加任意多的形状，只要注册了“`AreaGetters`”，我们就能获取这些形状的面积。这可以在任何应用程序中完成，而无需更改 `ShapeAreaGetter` 类的代码。我故意不称之为 `Geometry`，因为我们可以将许多“`Geometry`”函数放在它们各自的类中，所以最好使用更具体的名称。我们还可以添加任何函数，即使与几何无关，例如 `Draw()`，通过使用非常相似的代码来实现。也就是说，我们可能有一个添加函数的“模式”。`Draw()` 的代码可能如下：

public static class ShapeDrawer
{
  private static readonly ConcurrentDictionary<Type, Action<object, DrawingContext>> _dictionary = 
    new ConcurrentDictionary<Type, Action<object, DrawingContext>>();
  
  public static void Register<T>(Action<T, DrawingContext> action)
  {
    if (action == null)
      throw new ArgumentNullException("action");
	  
    if (!_dictionary.TryAdd(typeof(T), (shape, drawingContext) => action((T)shape, drawingContext)))
      throw new InvalidOperationException(
        "A drawer action was already registered for the given data-type.");
  }
  
  public static void Draw(object shape, DrawingContext drawingContext)
  {
    if (shape == null)
      throw new ArgumentNullException("shape");
	  
    if (drawingContext == null)
      throw new ArgumentNullException("drawingContext");
	  
    Type type = shape.GetType();
    Action<object, DrawingContext> action;
    _dictionary.TryGetValue(type, out action);
	
    if (action == null)
      throw new InvalidOperationException(
        "There's no shape drawer registered for the given shape's type.");
	  
    action(shape, drawingContext);
  }
}

需要注意的是，这些类可以存在于库中，也可以不存在，但应用程序可以在运行时扩展它们。因此，为了保持 `Draw` 方法只存在于应用程序中，而 `GetArea` 是库的一部分这个想法，请考虑只有 `AreaGetter` 类是库的一部分。我们肯定需要库中包含基本形状，它们与过程式示例中使用的完全相同，并且我们需要在初始化时为它们注册面积获取器，但这仅此而已。

新解决方案存在的问题？

新解决方案功能齐全。即使添加了大量的形状，它也能快速运行，因为 `ConcurrentDictionary` 的插入和查找在大多数情况下都是 **O(1)**（常数时间）。形状和函数可以独立添加，而无需更改库，因为该解决方案可在运行时扩展。然而，有些地方还不完美。

  1. 我们不能执行 `shape.Draw()` 或 `shape.GetArea()`。我们需要执行 `ShapeAreaGetter.GetArea(shape)` 或 `ShapeDrawer.Draw(shape)`。
  2. 没有任何东西告诉我们形状“可用的函数”是什么，也没有任何东西阻止我们给 `ShapeAreaGetter.GetArea()` 方法传递随机对象（例如 `string` 或 `int`）。
  3. 添加一个新函数是一个相对漫长的模式，每次都需要一个新类。
  4. 我们仍然需要为所有形状/函数组合编写委托，否则就会出现运行时异常。
  5. 最后，我们应该何时注册库附带的默认函数？

前两个问题可以通过使用 `IShape` 接口和扩展方法来解决。这样的接口不需要包含任何方法，但可以为该类型创建 `Draw()`、`GetArea()` 或任何其他扩展方法，而不是使用 `object`。实际上，可以将扩展方法添加到 `object` 类，但我认为如此通用的做法不太好，因为这些方法会出现在绝对任何地方。

第三项几乎不可能解决。我们可以创建一个带有大部分逻辑的辅助类，但它将变成一个充斥着通用参数的辅助类，最终，我们仍然需要一个使用该类的模式，创建新类并进行重定向。然而，我们必须记住，带有值协调的依赖属性也有一个很大的模式，尽管人们已经习惯了它。

第四项是任何解决方案中的一个问题。如果所有函数都要被所有形状支持，那么我们无论如何都需要实现它们。至少这个解决方案允许在最终应用程序中添加新函数和形状，而无需修改库。

最后一个问题实际上是 C# 中的一个问题。C# 不允许我们创建模块初始化函数，而这将是注册库提供的默认函数最理想的地方。这是一个 C# 的限制，因为 .NET 本身允许这样做，而且没有一个变通方法真正优雅。或者我们创建必须在库使用前调用的“初始化方法”，或者我们在形状或“函数类”（`ShapeAreaGetter` 和 `ShapeDrawer`）的静态构造函数中注册操作（或者我们甚至可以在它们中添加额外的逻辑来查找特定命名空间中的“默认实现”等等）。

示例

new Circle { CenterX = 20, CenterY = 20, Radius=9 },
new Square { Left = 200, Top = 10, Side=50 },
new Rectangle { Left = 200, Top = 200, Width=35, Height=77 },
new Triangle { X1=100, Y1=100, X2=120, Y2=157, X3=10, Y3=150 },
new TextInfo { FontName="Arial", FontSize=14, Left=120, Top=100, Text="Hello world!" }

我制作了示例应用程序来展示基本代码存在于一个库中，它被另一个库扩展，然后被应用程序进一步扩展，并且对第一个库的调用仍然能够处理在第二个库和应用程序中创建的对象。

我使用了扩展方法 + `IShape` 接口的解决方案，因此可以看到所有“函数”，就好像它们是实例方法一样。每个 `Drawer` 和 `AreaGetter` 都位于一个单独的类中，但实际上可以将许多类放在同一个类中。在初始化库时，所有这些方法都使用反射进行注册。这很好，因为可以添加新的 `AreaGetters` 和 `Drawers`，而无需修改注册它们的代码。

我没有为 `TextInfo`（显示“`Hello world!`”）实现 `AreaGetter`，以表明即使不是所有方法都实现，应用程序仍然可以编译，因此你可以真正独立地实现事物（形状、面积获取器和绘制器）。

应用程序显示形状并有一个列表显示它们的面积。它不是动画或其他什么，仅仅是因为这并不是应用程序的目的。

何时应该使用此模式？

在我看来，在我们编写的任何代码中，当想到要使用 `switch` 时。然而，正如许多与可维护性相关的模式一样，我们可能不需要在最终应用程序中使用它，因为应用程序的扩展通常需要应用程序进行更改，而要找到现有应用程序中的所有 `switch` 并用所提出的模式替换它们可能过于复杂。

因此，在新代码中，养成使用此模式的习惯是很好的。在旧代码中，如果我们已经面临可维护性问题，我们应该尝试使用该模式。如果我们没有面临问题，我们就应该让现有的 `switch` 存在，并优先处理更重要的问题。

© . All rights reserved.