LISP - Adjustable Vectors

Lisp - Adjustable Vectors

An adjustable vector is a dynamic array that can change its size at runtime. This data structure is incredibly useful when working with a collection whose size is not known in advance or is expected to change during program execution.

Key Concepts

• Adjustability: A vector must be explicitly created with the :adjustable flag set to true to allow its capacity to be changed after creation.
• Fill Pointer: A vector can have a fill-pointer, which is an index that tracks the number of active elements. This allows you to add elements to a vector without immediately resizing its underlying storage, making it a logical “end” of the vector. Operations like vector-push automatically manage the fill pointer.

Creating an Adjustable Vector

You create an adjustable vector using the make-array function with the :adjustable and :fill-pointer arguments.

Syntax

(make-array <initial-size>
            :adjustable t
            :fill-pointer <initial-fill-pointer>
            :initial-element <value>)

• <initial-size>: The initial allocated capacity of the vector.
• :adjustable t: This flag is required to allow the vector to be resized.
• :fill-pointer: Setting this to an integer (e.g., 0 for an empty vector) enables fill-pointer-based operations.

Example: Create an Empty Adjustable Vector

;; Define a global variable to hold our dynamic vector.
;; It has an initial capacity of 5, but is logically empty (fill-pointer is 0).
(defvar *my-vector* (make-array 5 :adjustable t :fill-pointer 0))

;; Print the vector (shows only active elements).
(print *my-vector*)

;; Print the fill-pointer.
(print (fill-pointer *my-vector*))

Output

#()
0

Manipulating the Vector

Adding Elements with vector-push

The vector-push function adds an element to the end of the vector (at the fill-pointer’s position) and increments the fill-pointer. It returns the new index, or nil if the vector is full.

;; Create a fresh vector
(defvar *my-vector* (make-array 5 :adjustable t :fill-pointer 0))

;; Add some elements
(vector-push 'a *my-vector*)
(vector-push 'b *my-vector*)
(vector-push 'c *my-vector*)

(print *my-vector*)
(print (fill-pointer *my-vector*))

Output

#(A B C)
3

Removing Elements with vector-pop

The vector-pop function removes and returns the last active element from the vector by decrementing the fill-pointer. It’s a non-destructive operation on the underlying data.

;; Continuing from the previous example where *my-vector* is #(A B C)
(print (vector-pop *my-vector*))  ; Removes and returns 'C

(print *my-vector*)
(print (fill-pointer *my-vector*))

Output

C
#(A B)
2

Automatic Resizing with vector-push-extend

vector-push-extend is the key to dynamic growth. It works like vector-push, but if the vector is full (i.e., fill-pointer equals array capacity), it automatically resizes the vector to make more room before adding the new element.

Example

;; Create a small vector with an initial size of 3.
(defvar *my-vector* (make-array 3 :adjustable t :fill-pointer 0))

;; Fill the vector to its capacity.
(dotimes (i 3)
  (vector-push-extend (* i 10) *my-vector*))

(format t "Vector before extending: ~s, Length: ~d, Fill Pointer: ~d~%"
        *my-vector* (length *my-vector*) (fill-pointer *my-vector*))

;; This next call will force a resize.
(vector-push-extend 40 *my-vector*)

(format t "Vector after extending:  ~s, Length: ~d, Fill Pointer: ~d~%"
        *my-vector* (length *my-vector*) (fill-pointer *my-vector*))

Output

Vector before extending: #(0 10 20), Length: 3, Fill Pointer: 3
Vector after extending:  #(0 10 20 40), Length: 5, Fill Pointer: 4

Performance Consideration

Resizing an array can be an expensive operation. To reduce the number of reallocations, vector-push-extend takes an optional second argument, extension, which specifies by how much to increase the array’s size if a resize is needed. Providing a larger extension factor can lead to better performance through amortization.