本文是对ADT相关知识点的总结。

ADT是什么

ADT是抽象数据型(Abstract Data Type)的简称。实际上ADT就是类(class)，只是从不同的视角来看。

ADT认为类是一种数据类型。不过跟传统的数据类型不同的是，ADT不关注数据的具体表示，而是强调“作用于数据上的操作”，认为这些操作完全定义了数据类型（即ADT）。

ADT分为两类：

• mutable类型：提供了可以改变内部值的操作。
• immutable类型：任何操作不改变内部值，而是构造新的对象。

ADT的四种操作

ADT的所有操作可以分为四种：

• Creators：构造器，通过其他类型构造出一个本类型的ADT对象。可以实现为构造函数或者静态函数。实现为静态函数时经常被称为工厂方法。
• Producers：生产器，使用ADT对象生成其他的ADT对象。
• Observers：观察器，观察ADT对象的属性。
• Mutators：变值器，改变ADT对象的属性。通常返回void，这时它一定改变了对象的某些内部状态，也可能返回非空类型。immutable类型的ADT一般不能有Mutators

这四种操作形式上的区别如下：

• Creators：t* -> T
• Producers：T+, t* -> T
• Observers：T+, t* -> t
• Mutators：T+, t* ->void | t | T

其中T表示ADT自己，t表示其他类型，+表示出现一次或多次，*表示出现0次或多次，|表示或。

表示独立性、不变量与表示泄露

表示独立性(Representation Independence)就是说客户端(client)在使用ADT的时候无需考虑其内部如何实现，ADT方法的spec（规约）规定了client和ADT之间的契约。也就是说，spec是一道“墙”，墙内外不能相互影响。client不能改变ADT对象内部的值，ADT内部表示的变化不能影响spec和client（即使ADT更换了实现方法，也还是要满足spec）。

不变量(Invariants)是为了保持程序的正确性而存在的，它是一组总是正确的条件。不变量是由ADT负责的，跟client无关。应该为ADT规定一个不变量，然后在每个方法中检查这个不变量。

表示泄露(rep exposure)就是说ADT外部的代码（指client）可以直接改变ADT内部的属性。这不仅影响了不变性，也影响了表示独立性。

如何避免表示泄露：

• 尽量使用immutable的属性（最好的方法）
• 尽量使用private和final修饰属性
• mutable的属性在传入ADT（例如构造方法中）和传出ADT（例如Observer中）时要进行defensive copy（防御性拷贝）

AF和RI

每个ADT都有两个空间，一个叫表示空间R，一个叫抽象空间A。抽象空间是client看到的空间，表示空间是ADT开发者看到的空间。

AF（抽象函数，Abstraction Function）是R到A的映射，即如何将R中的每一个值解释为A中的每一个值，形式地说，就是AF : R -> A。

RI（表示不变性，Rep Invariant）是对表示空间的约束，描述了什么样的表示是“合法的”。可以认为RI是所有表示值的一个自己，包含所有合法的表示值；也可以认为RI是一个条件，描述了什么是“合法”的表示值。

AF和RI跟内部表示有关，当你选择了一种表示抽象值的方式的时候，你就需要指定某个子集是“合法的”（这就是RI），然后你需要为该子集中的每一个值做出“解释”——即如何映射到抽象空间中的值（这就是AF）。