LISP - 数组中的填充指针

现代 Lisp：带有填充指针的动态数组

在 Common Lisp 中，数组通常是固定大小的。然而，许多应用程序需要一个可以动态增长的集合，例如 C++ 的 std::vector 或 Python 的 list。Lisp 为此提供了一种高效的机制：带有填充指针的可调整大小数组。

填充指针（fill pointer）充当数组的逻辑“结束”标记，允许你在较大的预分配内存块中管理一个较小、活跃的部分。这是解析、I/O 缓冲和构建数据集合等性能关键任务中的一项关键技术，同时避免了列表操作带来的开销。

核心概念：什么是填充指针？

想象你有一个可以容纳 100 本书的书架。这就是数组的总大小（total size）或容量（capacity）。如果你目前只放了 5 本书，你可能会在第 5 本书后放一个书签。这个书签就是填充指针。

• 填充指针是一个整数，指示数组中有多少元素当前是“活跃”或正在使用的。
• 数组的活跃长度（active length），由 length 函数返回，等于其填充指针，而不是其总分配大小。
• 填充指针必须始终小于或等于数组的总大小。

创建和使用动态数组

1. 创建带有填充指针的数组

要创建动态数组，你需要使用 make-array 并传入两个关键参数：:adjustable t 和 :fill-pointer。将 :fill-pointer 设置为一个整数会将其活跃长度初始化为该值。将其设置为 t 则会将填充指针初始化为数组的总大小。

;; 创建一个可容纳 10 个元素的向量，但初始为空。
(defvar *dynamic-vector*
  (make-array 10 :adjustable t :fill-pointer 0))

;; 检查其属性
(print (array-total-size *dynamic-vector*)) ;=> 10
(print (length *dynamic-vector*))           ;=> 0 (因为填充指针为 0)

2. 惯用用法：vector-push 和 vector-push-extend

虽然你可以手动设置填充指针，但向动态数组添加元素的惯用方式是使用 vector-push 和 vector-push-extend。这些函数会自动为你管理填充指针。

• vector-push：如果有空间，则将元素添加到向量的末尾。它会增加填充指针并返回新索引。
• vector-push-extend：执行相同的操作，但如果数组已满，它会自动调整大小以腾出更多空间，然后才添加元素。这使得数组真正具有动态性。

;; 让我们创建一个小型、可扩展的向量
(defvar *buffer* (make-array 3 :adjustable t :fill-pointer 0))

;; 添加一些元素
(vector-push-extend 'a *buffer*) ;=> 0
(vector-push-extend 'b *buffer*) ;=> 1
(vector-push-extend 'c *buffer*) ;=> 2

(print *buffer*) ;=> #(A B C)
(print (length *buffer*)) ;=> 3

;; 现在，再添加一个元素。数组将自动增长。
(vector-push-extend 'd *buffer*) ;=> 3

(print *buffer*) ;=> #(A B C D)
(print (length *buffer*)) ;=> 4
(print (array-total-size *buffer*)) ;=> (依赖于具体实现，但 > 3, 例如 6)

3. 手动管理填充指针

你也可以直接读写填充指针。这对于清空缓冲区而无需重新分配内存等任务非常有用。

;; 让我们使用上一个示例中的缓冲区：#(A B C D)
(print (fill-pointer *buffer*)) ;=> 4

;; 通过将填充指针设置为 0 来重置缓冲区。
;; 数据仍然存在，但逻辑上数组已空。
(setf (fill-pointer *buffer*) 0)

(print (length *buffer*)) ;=> 0
(print *buffer*) ;=> #()

;; 你可以添加新元素，它们将覆盖旧元素。
(vector-push-extend 'x *buffer*)
(print *buffer*) ;=> #(X)

实际应用：一个小型项目

让我们构建一个简单的函数，它将从字符串流中读取所有行并放入一个动态向量中。这模拟了逐行读取文件。

(defun read-lines-to-vector (text-stream)
  "从流中读取所有行到一个动态向量中。"
  (let ((lines (make-array 10 :adjustable t :fill-pointer 0)))
    (loop for line = (read-line text-stream nil nil) ; 读取一行
          while line ; 只要读取到行就继续
          do (vector-push-extend line lines))
    lines))

;; --- 测试它 ---
(let* ((sample-text "Hello Lisp\nModern Development\nEnd of File")
       (text-stream (make-string-input-stream sample-text))
       (result-vector (read-lines-to-vector text-stream)))

  (print result-vector))

;; --- 输出 ---
; #("Hello Lisp" "Modern Development" "End of File")

最佳实践和常见陷阱

• 优先使用 vector-push-extend：对于大多数动态增长场景，vector-push-extend 是最安全、最方便的选择。
• 何时使用填充指针：当你需要随机访问 (aref)，或者处理大量元素并希望避免列表内存分配开销（consing）时，优先于列表使用填充指针。
• 常见错误：尝试将填充指针设置为大于 array-total-size 的值。这将引发错误。
• 性能提示：当你大致知道需要多少元素时，用一个更大的尺寸初始化数组，以减少 vector-push-extend 需要调整大小的次数。