1、decal sdl 通用数据结构与算法类库
我个人认为是目前类结构建模建得很好的一个数据结构类库。
介绍
decal的前身是 sdl，一套商业的通用数据结构与算法类库。decal删除了其中关于垃圾回收部分的代码，而将其他部分全部开放源代码了，这对大家来说是一个好消息。decal的全称是 delphi container and algorithm library，也就是delphi 数据容器和算法类库。decal是基于 mozilla 开放源程序协议的一个数据结构类库，它的作者是soletta。decal的一些思想是来自stepanov 和 lee 的 c++ stl(standard template library) 和 objectspace’s jgl (java generic library)。
decal 提供许多其它delphi类库中没有的功能:
* 基于已经成熟的stl体系，强有力的底层工艺。
* decal 是基于通用计算机算法和数据结构的类库。
* 提供容易使用的方式存储各种数据类型。(如 integers, strings, extended values)。
* decal 使用了delphi 4的数组常量 array of const 功能，该功能极大的减轻了程序员的负担。
* decal 提供超过 60 种的常用算法。
* decal 集成 superstream 为数据存放到流中提供了解决方案。
* 完整的数据结构类库。decal 包括：数组 arrays, 双向链表 double-linked lists, 映射 maps, 和集合 sets。 映射结构包括二叉树和散列两种形式。
decal 的术语解释：
item （数据项）
在 decal, 数据项 (items) 是如下的基本数据类型：
整数(integer), 字符串(string), 货币(currency), 或字符(char)类型等。 一个对象（object）也是一种数据项。
container（容器）
容器是用来保存数据项的。它是一种数据结构。不同类型的容器（数据结构）拥有不同的能力。据一个例子来说，某种类型的容器也许拥有快速的删除能力，但是添加较慢，而另一种容器支持快速的随机访问，但是删除较慢。当你需要容器保存数据项时，选择适当的容器类型将让你的程序效率倍增，反之亦然。每一种容器的利弊我们将在后面详述。
iterator（数据项指针）
iterator 就是数据项指针，它指向容器中某一特定的数据项。数据项指针可以前后移动，存取数据项都是通过iterator（数据项指针）实现的。使用iterator（数据项指针）访问数据，可以使你在改变容器类型后，对数据项的处理不用作任何的改变。我们经常会看到如下的代码：
iterator := container.start;
iterator := container.finish;
第一行代码是取出容器的第一项数据，而第二行是取出容器的 atend 结束数据项（最后一数据项的后一个位置，标志结束）
comparator （比较函数）
比较函数（comparator）用来比较两个数据乡的大小。如果第一项小于第二项，那么函数应该返回一个小于0的值；如果相等则返回数值0；如果第一项大于第二项，那么函数应该返回一个大于0的值。下面是比较函数的定义：
dcomparator = function (const obj1, obj2 : dobject) : integer of object;
atend
decal 使用数据项指针（iterators）维护容器里的数据项位置。有一个特殊的数据项指针（iterator）叫做： atend。
atend 数据项指针指示已经达到容器中的最末尾，已无数据可取。从该位置取数据是非法的！有时向该位置写是合法的。某种容器会添加一个对象到atend标志（certain containers will add the object being written to the end of the container），但并不是所有的容器都这样做，尤其是映射类容器（mapping containers）。 atend 是非常重要的，当算法无法前进到下一个数据项时它们就会返回 atend。
range （范围）
范围是两个数据项指针，标示数据项的开始位置和结束位置。例如：在 container.start 和 container.finish 之间的数据项就是一个范围。
pair（数据对）
一个数据对是两个数据项(两个 dobjects, 存储在一个 dpair 中)。映射容器（mapping containers）存储的数据就是数据对，存储的数据对由关键字key(第一个字段)和数据值 value (第二个字段) 构成。
sequence （序列类型容器）
序列类型容器里的数据项有一定的顺序。序列类型容器将数据项按照一定的顺序，逐一取出。序列类型容器有：链表，数组等。
vector（向量类型容器）
向量类型容器是由序列类型容器派生而来的。与序列类型容器不同的是，向量类型容器的每一个数据项都是有数字可寻址的。换句话说，你可以想取第一项就取第一项，想取第五项就取第五项。当序列需要返回指定位置的数据项，向量类型容器就是一个有效的实现。向量类型容器的一个有用的实现就是数组。
map （映射类型容器）
映射类型容器用于存储关键字/值（key-value）数据对。你应该特别重视该类，因为 90%的容器应用都是基于的映射类型容器的应用。映射类型容器可以保存关联数据。举个例子，当你希望保存一系列的员工数据，按照员工id查找，你就可以使用映射类型容器，将员工id作为key，员工数据类作为数据值:
map.putpair([1001, jimsmithobject]);
当你想取出员工id为1001的员工数据时候：
employee := getobject(map.locate([1001])) as temployee;
映射类型容器对查找关键字非常有效！
decal 有两种基本的映射类型容器:
排序映射类型容器（an ordered map：基于红-黑二叉树 red-black trees）
混乱映射类型容器（an unordered map： 基于散列 hash structures）.
映射类型容器有种基本变体： multimap 映射类型容器。
他们的不同之处在于 multimaps 可以在同一关键字上存储多个对象。而常规映射类型容器在不能在同一关键字上存储不同对象。
set （集合类型容器）
集合类型容器存储数据项。与 delphi 的集合概念类似，用来让你快速的确认是否该集合包含或不包含特定的数据项。与delphi的集合类型不同的是，你可以使用任何的原子数据类型作为集合的元素，如：数字，字符串，对象等等。
与映射类型容器类似，集合类型容器也有种基本变体： multisets。multiset集合类型容器可以允许有多个同一对象在集合内。
集合类型容器也有两种基本类型：基于红-黑二叉树和基于散列的。
hashing（散列）
散列（hashing）是将某一数据项或对象转换成一个标示该数据项或对象的数字。
