Vectors

Vectors are Common Lisp’s basic integer-indexed collection, and they come in two flavors. Fixed-size vectors are a lot like arrays in a language such as Java: a thin veneer over a chunk of contiguous memory that holds the vector’s elements.2 Resizable vectors, on the other hand, are more like arrays in Perl or Ruby, lists in Python, or the ArrayList class in Java: they abstract the actual storage, allowing the vector to grow and shrink as elements are added and removed.

You can make fixed-size vectors containing specific values with the function **VECTOR**, which takes any number of arguments and returns a freshly allocated fixed-size vector containing those arguments.

  1. (vector)     ==> #()
  2. (vector 1)   ==> #(1)
  3. (vector 1 2) ==> #(1 2)

The #(...) syntax is the literal notation for vectors used by the Lisp printer and reader. This syntax allows you to save and restore vectors by **PRINT**ing them out and **READ**ing them back in. You can use the #(...) syntax to include literal vectors in your code, but as the effects of modifying literal objects aren’t defined, you should always use **VECTOR** or the more general function **MAKE-ARRAY** to create vectors you plan to modify.

**MAKE-ARRAY** is more general than **VECTOR** since you can use it to create arrays of any dimensionality as well as both fixed-size and resizable vectors. The one required argument to **MAKE-ARRAY** is a list containing the dimensions of the array. Since a vector is a one-dimensional array, this list will contain one number, the size of the vector. As a convenience, **MAKE-ARRAY** will also accept a plain number in the place of a one-item list. With no other arguments, **MAKE-ARRAY** will create a vector with uninitialized elements that must be set before they can be accessed.3 To create a vector with the elements all set to a particular value, you can pass an :initial-element argument. Thus, to make a five-element vector with its elements initialized to **NIL**, you can write the following:

  1. (make-array 5 :initial-element nil) ==> #(NIL NIL NIL NIL NIL)

**MAKE-ARRAY** is also the function to use to make a resizable vector. A resizable vector is a slightly more complicated object than a fixed-size vector; in addition to keeping track of the memory used to hold the elements and the number of slots available, a resizable vector also keeps track of the number of elements actually stored in the vector. This number is stored in the vector’s fill pointer, so called because it’s the index of the next position to be filled when you add an element to the vector.

To make a vector with a fill pointer, you pass **MAKE-ARRAY** a :fill-pointer argument. For instance, the following call to **MAKE-ARRAY** makes a vector with room for five elements; but it looks empty because the fill pointer is zero:

  1. (make-array 5 :fill-pointer 0) ==> #()

To add an element to the end of a resizable vector, you can use the function **VECTOR-PUSH**. It adds the element at the current value of the fill pointer and then increments the fill pointer by one, returning the index where the new element was added. The function **VECTOR-POP** returns the most recently pushed item, decrementing the fill pointer in the process.

  1. (defparameter *x* (make-array 5 :fill-pointer 0))
  3. (vector-push 'a *x*) ==> 0
  4. *x*                  ==> #(A)
  5. (vector-push 'b *x*) ==> 1
  6. *x*                  ==> #(A B)
  7. (vector-push 'c *x*) ==> 2
  8. *x*                  ==> #(A B C)
  9. (vector-pop *x*)     ==> C
  10. *x*                  ==> #(A B)
  11. (vector-pop *x*)     ==> B
  12. *x*                  ==> #(A)
  13. (vector-pop *x*)     ==> A
  14. *x*                  ==> #()

However, even a vector with a fill pointer isn’t completely resizable. The vector *x* can hold at most five elements. To make an arbitrarily resizable vector, you need to pass **MAKE-ARRAY** another keyword argument: :adjustable.

  1. (make-array 5 :fill-pointer 0 :adjustable t) ==> #()

This call makes an adjustable vector whose underlying memory can be resized as needed. To add elements to an adjustable vector, you use **VECTOR-PUSH-EXTEND**, which works just like **VECTOR-PUSH** except it will automatically expand the array if you try to push an element onto a full vector—one whose fill pointer is equal to the size of the underlying storage.4