通常，数组让我们可以随机（以 O(1) 的时间复杂度）访问其内的数据。但是，随机访问不是目的，而是手段。我们究竟需要一个数组解决怎样的问题？面对怎样的问题，需要处理的数据需要以数组方式组织？我这几年始终不敢说自己得到了确切的答案。往往，我们只是直觉上感觉，用一个 vector （使用 C++ ）非常方便，所以就用了。当我在用 C 的时候，我总是随手写上一个 realloc ，来扩展我的数据块。最近一段时间，我觉得有必要归纳一下需求，设计一个通用模块来统一解决问题了。

思考的结果就是：当我们周期性的聚合一堆数据时，我们需要一个数组，且这个数组的长度是不确定的，应该可以动态增长。

数组最重要的特性是可以最高效的遍历，即依次处理数组内部的元素。在 C 语言的层面考虑这个问题时，就应该更细致考虑实现的差别引起的性能差异。比如链表的遍历同样是 O(N) ，但是时间和空间的开销都是大于连续内存空间的数组的。

我们需要快速的清空数组，方便下一个周期聚合新的数据。

我们需要对数据排序，使得按我们的需要的次序去依次处理（遍历）数组中的元素。

有时候，我们需要相对快速的查找。一旦数据是有序的，二分查找可以让时间复杂度减少到 O(log n) 。

其它，我们不再需要。

注：我们往往混淆了另一个需求。很多时候，我们把数组当成了一个高性能却有局限性的 key-value 字典。这个 key 就是数组内数据的数字索引。对于用一个 key （可能是数，也可能不是）快速索引到值的需求，应该放到另一个地方去考虑。

最终，我为 array 这个 ADT 提供了如下的方法：

struct array * array_create(int atom_size);
void array_release(struct array *);
void array_clear(struct array *);
void array_push(struct array *, void *atom);
void array_iterator(struct array *, seqi iter);
void array_sort(struct array *, int (*compar)(void *,void *));

这里，暂时没有提供 binarysearch 方法，因为暂时我还没有用到。我还不确定是不是真的有意义，以及最佳的接口定义应该是怎样。

在实现时，我开辟了一整块连续内存保存数据。当使用者 push 一个元素时，采用值复制的方式，复制到 array 内部。然后用 seq 来管理对内部元素的引用（指针）。

当数据区不够大时，采用 realloc 扩展数据区内存。一旦内存地址发生变化，则修改对应的 seq 里的指针。把索引和数据分开存放，可以提高排序的效率（数据交换量比较小）。

sort 函数提供了一个类似 qsort 接口的比较函数。但是，由于和 qsort 的定义有所不同，所以不能直接去调用 qsort 。在 glibc 中，有另一个 qsort_r 可以满足需求。不过我考虑到性能，自己重新实现了一个快速排序。反正，也没几行代码。

这里，由于数据在内存中的位置并不固定。从 seqi 中拿到的指针是不可以被传递保存到别的数据结构体中的。包括 seqi 这个迭代子，根据上篇关于 sequence 实现的描述，也不允许长期保留。你可以认为，这是这个 ADT 的局限性。不过我个人认为，我们每设计一个东西，只应该解决有限的，定义好的需求。而不应该包罗万象。

只做一件事，并把它做好。